Date: Tue, 14 Nov 2006 18:24:28 +0100 (CET) From: Oliver Fromme <olli@lurza.secnetix.de> To: freebsd-net@FreeBSD.ORG, max@love2party.net Subject: Re: ipv6 connection hash function wanted ... Message-ID: <200611141724.kAEHOST9044973@lurza.secnetix.de> In-Reply-To: <freebsd-net.200611141709.26644.max@love2party.net>
next in thread | previous in thread | raw e-mail | index | archive | help
Max Laier wrote: > Input: 2x128bit of address (lower ~80bit selectable by user) and 2x16bit > of ports (more or less selectable by user). Note that the "flow_id" is > not useable as several broken stack implementations do not set it > consistently - and it is user settable as well. > Output: "int" hash value - by default we use the lower 8bit of it. > > Problems: Most of the input can be selected by a user meaning it is easy > to produce collisions. For legal connections, the lower 64bit are the > one with the highest entropy - in fact the upper 64bit might be the same > for many connections coming from/going to the same subnet. This function > will be used for every packet that is passed to a dynamic IPFW rule, so > efficiency is a concern. If you want to prevent users from intentionally producing collisions, then you need to use a cryptographically strong hash function, such as SHA1/SHA256 which give 160 and 256 bits, respectively. If you only need a 32bit int, then simply pick the low 32bit of the SHA1/SHA256 and forget the rest. For normal uses I think MD5 might be sufficient, which is already implemented in the kernel (see MD5(9)). While MD5 hasn't actually been broken, some weaknesses haven been discovered that could be used to construct collisions under certain circumstances, but it's still far from easy and hasn't been proven for the generic case. If your hash doesn't have to be cryptographically secure, then a simple crc32 should be sufficient. This is much easier and faster to calculate. If even a single bit (any one) in the input changes, you will get a completely different crc32 value, so it should be suitable as a hash function. However, since it's not cryptographically strong, it _is_ possible to construct inputs that will produce collisions. Just my 2 cents. YMMV. Best regards Oliver -- Oliver Fromme, secnetix GmbH & Co. KG, Marktplatz 29, 85567 Grafing Dienstleistungen mit Schwerpunkt FreeBSD: http://www.secnetix.de/bsd Any opinions expressed in this message may be personal to the author and may not necessarily reflect the opinions of secnetix in any way. "C is quirky, flawed, and an enormous success." -- Dennis M. Ritchie.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200611141724.kAEHOST9044973>