Hi, with a lot of help from David Malone and JINMEI Tatuya we came up with the following hash function for IPv6 connections using universal hashing. Note that while it looks a lot more complicated, it is unlikely to consume (much) more time. The most expensive operation is still the memory access - which has to happen either way. Since this is a firewall and as such a security feature, we should rather do it right. Note that in IPv6 an attacker can easily choose 96 Byte of input, so it's trivial to construct collisions with the current hash function. A degenerated hash is certainly more expensive than this changes.
Objections, Comments, anything else? BTW, don't suggest that we use memcmp in addr6_cmp. As it turns out, the kernel version of memcmp() does not provide POSIX compliant return values. -- /"\ Best regards, | [EMAIL PROTECTED] \ / Max Laier | ICQ #67774661 X http://pf4freebsd.love2party.net/ | [EMAIL PROTECTED] / \ ASCII Ribbon Campaign | Against HTML Mail and News
Index: ip_fw2.c
===================================================================
RCS file: /usr/store/mlaier/fcvs/src/sys/netinet/ip_fw2.c,v
retrieving revision 1.154
diff -u -r1.154 ip_fw2.c
--- ip_fw2.c 13 Nov 2006 19:07:32 -0000 1.154
+++ ip_fw2.c 1 Dec 2006 18:00:04 -0000
@@ -50,6 +50,7 @@
#include <sys/malloc.h>
#include <sys/mbuf.h>
#include <sys/kernel.h>
+#include <sys/libkern.h>
#include <sys/lock.h>
#include <sys/jail.h>
#include <sys/module.h>
@@ -231,6 +232,9 @@
static ipfw_dyn_rule **ipfw_dyn_v = NULL;
static u_int32_t dyn_buckets = 256; /* must be power of 2 */
static u_int32_t curr_dyn_buckets = 256; /* must be power of 2 */
+#define HASHKEYLEN 36 /* sizeof(in6_addr) * 2 + sizeof(in_port_t) * 2 */
+#define HASHPRIME 65537
+static u_int32_t ipfw_hash_key[HASHKEYLEN];
static struct mtx ipfw_dyn_mtx; /* mutex guarding dynamic rules */
#define IPFW_DYN_LOCK_INIT() \
@@ -640,16 +644,56 @@
return 1;
}
+
+static __inline int
+addr6_cmp(struct ipfw_flow_id *id)
+{
+ int i;
+
+ if (id->src_port < id->dst_port)
+ return 1;
+ if (id->src_port > id->dst_port)
+ return -1;
+ for (i = 7; i >= 0; i--)
+ if (id->dst_ip6.s6_addr16[i] != id->src_ip6.s6_addr16[i])
+ return ((int)id->dst_ip6.s6_addr16[i] -
+ id->src_ip6.s6_addr16[i]);
+
+ return (0);
+}
+
static __inline int
hash_packet6(struct ipfw_flow_id *id)
{
- u_int32_t i;
- i = (id->dst_ip6.__u6_addr.__u6_addr32[2]) ^
- (id->dst_ip6.__u6_addr.__u6_addr32[3]) ^
- (id->src_ip6.__u6_addr.__u6_addr32[2]) ^
- (id->src_ip6.__u6_addr.__u6_addr32[3]) ^
- (id->dst_port) ^ (id->src_port);
- return i;
+ u_int32_t a;
+ int i, j;
+ struct in6_addr *a1, *a2;
+ u_int8_t *p1, *p2;
+
+ if (addr6_cmp(id) >= 0) {
+ a1 = &id->dst_ip6;
+ a2 = &id->src_ip6;
+ p1 = (u_int8_t *)&id->dst_port;
+ p2 = (u_int8_t *)&id->src_port;
+ } else {
+ a1 = &id->src_ip6;
+ a2 = &id->dst_ip6;
+ p1 = (u_int8_t *)&id->src_port;
+ p2 = (u_int8_t *)&id->dst_port;
+ }
+
+ a = 0;
+ j = 0;
+ for (i = 0; i < sizeof(a1->s6_addr); i++)
+ a += a1->s6_addr[i] * ipfw_hash_key[j++];
+ for (i = 0; i < sizeof(a2->s6_addr); i++)
+ a += a2->s6_addr[i] * ipfw_hash_key[j++];
+ a += p1[0] * ipfw_hash_key[j++];
+ a += p1[1] * ipfw_hash_key[j++];
+ a += p2[0] * ipfw_hash_key[j++];
+ a += p2[1] * ipfw_hash_key[j++];
+
+ return (a % HASHPRIME);
}
static int
@@ -1290,6 +1334,7 @@
static void
realloc_dynamic_table(void)
{
+ int j;
IPFW_DYN_LOCK_ASSERT();
/*
@@ -1297,7 +1342,7 @@
* not allow more than 64k entries. In case of overflow,
* default to 1024.
*/
-
+ CTASSERT(HASHPRIME >= 65536);
if (dyn_buckets > 65536)
dyn_buckets = 1024;
if ((dyn_buckets & (dyn_buckets-1)) != 0) { /* not a power of 2 */
@@ -1314,6 +1359,8 @@
break;
curr_dyn_buckets /= 2;
}
+ for (j = 0; j < HASHKEYLEN; j++)
+ ipfw_hash_key[j] = arc4random() % HASHPRIME;
}
/**
pgpNtbJBbGaTe.pgp
Description: PGP signature
