Date: Wed, 15 Nov 2006 13:53:12 +0100 From: Max Laier <max@love2party.net> To: freebsd-hackers@freebsd.org Subject: Re: ipv6 connection hash function wanted ... Message-ID: <200611151353.17417.max@love2party.net> In-Reply-To: <200611151126.kAFBQSQr090632@lurza.secnetix.de> References: <200611151126.kAFBQSQr090632@lurza.secnetix.de>
next in thread | previous in thread | raw e-mail | index | archive | help
--nextPart2097590.e4QkgR1fiN Content-Type: multipart/mixed; boundary="Boundary-01=_52wWFS911yltzsZ" Content-Transfer-Encoding: 7bit Content-Disposition: inline --Boundary-01=_52wWFS911yltzsZ Content-Type: text/plain; charset="iso-8859-6" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline On Wednesday 15 November 2006 12:26, Oliver Fromme wrote: > Max Laier wrote: > > David Malone wrote: > > > Assuming you don't want to use one of the standard cryptographic > > > ones (which I can imagine being a bit slow for something done > > > per-packet), then one option might be to use a simpler hash that > > > is keyed. Choose the key at boot/module load time and make it hard > > > to produce collisions unless you know the key. > > > > That's exactly what I am looking for ... now I need someone[tm] - > > with better Math-Knowledge than mine - to write such a thing down in > > a simple formula :-) i.e. take those bits from there and there and > > XOR them with your canary yada-yada-yada ... > > In that case, simply use crc32 (available from libkern.h) > and xor with a random key generated at boot time. crc32 > is fast to calculate and has the properties that you need. Oops, I missed one requirement: /* * IMPORTANT: the hash function for dynamic rules must be commutative * in source and destination (ip,port), because rules are bidirectional * and we want to find both in the same bucket. */ AFAICT, the attached has this property, but I have no idea if it adds=20 sufficient entropy to the result - it looks like it, though. =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=_52wWFS911yltzsZ Content-Type: text/x-diff; charset="iso-8859-6"; name="ipfw.crchash.diff" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="ipfw.crchash.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.153 diff -u -r1.153 ip_fw2.c =2D-- ip_fw2.c 6 Nov 2006 13:42:04 -0000 1.153 +++ ip_fw2.c 15 Nov 2006 12:36:34 -0000 @@ -230,6 +230,7 @@ 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 */ +static u_int32_t hash_nonce =3D 0; =20 static struct mtx ipfw_dyn_mtx; /* mutex guarding dynamic rules */ #define IPFW_DYN_LOCK_INIT() \ @@ -642,12 +643,19 @@ hash_packet6(struct ipfw_flow_id *id) { u_int32_t i; =2D i =3D (id->dst_ip6.__u6_addr.__u6_addr32[2]) ^ + + i =3D (id->dst_ip6.__u6_addr.__u6_addr32[0]) ^ + (id->dst_ip6.__u6_addr.__u6_addr32[1]) ^ + (id->dst_ip6.__u6_addr.__u6_addr32[2]) ^ (id->dst_ip6.__u6_addr.__u6_addr32[3]) ^ + (id->src_ip6.__u6_addr.__u6_addr32[0]) ^ + (id->src_ip6.__u6_addr.__u6_addr32[1]) ^ (id->src_ip6.__u6_addr.__u6_addr32[2]) ^ (id->src_ip6.__u6_addr.__u6_addr32[3]) ^ (id->dst_port) ^ (id->src_port); =2D return i; + i =3D crc32_raw(&i, sizeof(i), hash_nonce); + + return (i); } =20 static int @@ -4360,6 +4368,7 @@ uma_zdestroy(ipfw_dyn_rule_zone); return (error); } + hash_nonce =3D arc4random(); ip_fw_ctl_ptr =3D ipfw_ctl; ip_fw_chk_ptr =3D ipfw_chk; callout_reset(&ipfw_timeout, hz, ipfw_tick, NULL); --Boundary-01=_52wWFS911yltzsZ-- --nextPart2097590.e4QkgR1fiN Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.5 (FreeBSD) iD8DBQBFWw29XyyEoT62BG0RAgw7AJ9Qpvif6ztViclOL197hWYCF4GTowCcDQdN zemXAd+9ypxtz04+UUFXKtY= =3+wU -----END PGP SIGNATURE----- --nextPart2097590.e4QkgR1fiN--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200611151353.17417.max>