Date: Tue, 5 Dec 2006 20:10:30 +0100 From: Max Laier <max@love2party.net> To: freebsd-ipfw@freebsd.org Subject: Better "hash_packet6" Message-ID: <200612052010.36789.max@love2party.net>
next in thread | raw e-mail | index | archive | help
--nextPart15756221.C6omajAhyg Content-Type: multipart/mixed; boundary="Boundary-01=_oQcdFPftAjRnopP" Content-Transfer-Encoding: 7bit Content-Disposition: inline --Boundary-01=_oQcdFPftAjRnopP Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Hi, with a lot of help from David Malone and JINMEI Tatuya we came up with the= =20 following hash function for IPv6 connections using universal hashing. =20 Note that while it looks a lot more complicated, it is unlikely to=20 consume (much) more time. The most expensive operation is still the=20 memory access - which has to happen either way. Since this is a firewall=20 and as such a security feature, we should rather do it right. Note that=20 in IPv6 an attacker can easily choose 96 Byte of input, so it's trivial=20 to construct collisions with the current hash function. A degenerated=20 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=20 kernel version of memcmp() does not provide POSIX compliant return=20 values. =2D-=20 /"\ Best regards, | mlaier@freebsd.org \ / Max Laier | ICQ #67774661 X http://pf4freebsd.love2party.net/ | mlaier@EFnet / \ ASCII Ribbon Campaign | Against HTML Mail and News --Boundary-01=_oQcdFPftAjRnopP Content-Type: text/x-diff; charset="us-ascii"; name="v6hash.diff" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="v6hash.diff" Index: ip_fw2.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /usr/store/mlaier/fcvs/src/sys/netinet/ip_fw2.c,v retrieving revision 1.154 diff -u -r1.154 ip_fw2.c =2D-- 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 =3D NULL; static u_int32_t dyn_buckets =3D 256; /* must be power of 2 */ static u_int32_t curr_dyn_buckets =3D 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]; =20 static struct mtx ipfw_dyn_mtx; /* mutex guarding dynamic rules */ #define IPFW_DYN_LOCK_INIT() \ @@ -640,16 +644,56 @@ return 1; =20 } + +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 =3D 7; i >=3D 0; i--) + if (id->dst_ip6.s6_addr16[i] !=3D 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) { =2D u_int32_t i; =2D i =3D (id->dst_ip6.__u6_addr.__u6_addr32[2]) ^ =2D (id->dst_ip6.__u6_addr.__u6_addr32[3]) ^ =2D (id->src_ip6.__u6_addr.__u6_addr32[2]) ^ =2D (id->src_ip6.__u6_addr.__u6_addr32[3]) ^ =2D (id->dst_port) ^ (id->src_port); =2D return i; + u_int32_t a; + int i, j; + struct in6_addr *a1, *a2; + u_int8_t *p1, *p2; + + if (addr6_cmp(id) >=3D 0) { + a1 =3D &id->dst_ip6; + a2 =3D &id->src_ip6; + p1 =3D (u_int8_t *)&id->dst_port; + p2 =3D (u_int8_t *)&id->src_port; + } else { + a1 =3D &id->src_ip6; + a2 =3D &id->dst_ip6; + p1 =3D (u_int8_t *)&id->src_port; + p2 =3D (u_int8_t *)&id->dst_port; + } + + a =3D 0; + j =3D 0; + for (i =3D 0; i < sizeof(a1->s6_addr); i++) + a +=3D a1->s6_addr[i] * ipfw_hash_key[j++]; + for (i =3D 0; i < sizeof(a2->s6_addr); i++) + a +=3D a2->s6_addr[i] * ipfw_hash_key[j++]; + a +=3D p1[0] * ipfw_hash_key[j++]; + a +=3D p1[1] * ipfw_hash_key[j++]; + a +=3D p2[0] * ipfw_hash_key[j++]; + a +=3D p2[1] * ipfw_hash_key[j++]; + + return (a % HASHPRIME); } =20 static int @@ -1290,6 +1334,7 @@ static void realloc_dynamic_table(void) { + int j; IPFW_DYN_LOCK_ASSERT(); =20 /* @@ -1297,7 +1342,7 @@ * not allow more than 64k entries. In case of overflow, * default to 1024. */ =2D + CTASSERT(HASHPRIME >=3D 65536); if (dyn_buckets > 65536) dyn_buckets =3D 1024; if ((dyn_buckets & (dyn_buckets-1)) !=3D 0) { /* not a power of 2 */ @@ -1314,6 +1359,8 @@ break; curr_dyn_buckets /=3D 2; } + for (j =3D 0; j < HASHKEYLEN; j++) + ipfw_hash_key[j] =3D arc4random() % HASHPRIME; } =20 /** --Boundary-01=_oQcdFPftAjRnopP-- --nextPart15756221.C6omajAhyg Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.5 (FreeBSD) iD8DBQBFdcQsXyyEoT62BG0RAnFNAJ9QTNFvA+UQIlfwb1bH5j0z0ujfwACggM6J nc5OP+aSC5fVrwszG+Yx4T4= =RdTi -----END PGP SIGNATURE----- --nextPart15756221.C6omajAhyg--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200612052010.36789.max>