ipv6 connection hash function wanted ...

[Oliver Fromme]

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.