From owner-freebsd-hackers@FreeBSD.ORG Wed Nov 15 12:53:21 2006 Return-Path: X-Original-To: freebsd-hackers@freebsd.org Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 5739916A403 for ; Wed, 15 Nov 2006 12:53:21 +0000 (UTC) (envelope-from max@love2party.net) Received: from moutng.kundenserver.de (moutng.kundenserver.de [212.227.126.186]) by mx1.FreeBSD.org (Postfix) with ESMTP id 6B8FB43D55 for ; Wed, 15 Nov 2006 12:53:19 +0000 (GMT) (envelope-from max@love2party.net) Received: from [88.64.187.200] (helo=amd64.laiers.local) by mrelayeu.kundenserver.de (node=mrelayeu3) with ESMTP (Nemesis), id 0MKxQS-1GkKGU0RZA-0004Zb; Wed, 15 Nov 2006 13:53:18 +0100 From: Max Laier Organization: FreeBSD To: freebsd-hackers@freebsd.org Date: Wed, 15 Nov 2006 13:53:12 +0100 User-Agent: KMail/1.9.4 References: <200611151126.kAFBQSQr090632@lurza.secnetix.de> In-Reply-To: <200611151126.kAFBQSQr090632@lurza.secnetix.de> X-Face: ,,8R(x[kmU]tKN@>gtH1yQE4aslGdu+2]; R]*pL,U>^H?)gW@49@wdJ`H<=?utf-8?q?=25=7D*=5FBD=0A=09U=5For=3D=5CmOZf764=26nYj=3DJYbR1PW0ud?=>|!~,,CPC.1-D$FG@0h3#'5"k{V]a~.<=?utf-8?q?mZ=7D44=23Se=7Em=0A=09Fe=7E=5C=5DX5B=5D=5Fxj?=(ykz9QKMw_l0C2AQ]}Ym8)fU MIME-Version: 1.0 Content-Type: multipart/signed; boundary="nextPart2097590.e4QkgR1fiN"; protocol="application/pgp-signature"; micalg=pgp-sha1 Content-Transfer-Encoding: 7bit Message-Id: <200611151353.17417.max@love2party.net> X-Provags-ID: kundenserver.de abuse@kundenserver.de login:61c499deaeeba3ba5be80f48ecc83056 Subject: Re: ipv6 connection hash function wanted ... X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 Nov 2006 12:53:21 -0000 --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--