ipv6 connection hash function wanted ...

[Paul Twohey]

On Tue, 14 Nov 2006, Max Laier wrote:

> this one is something for people who know their math.
>
> 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.
>
> Any ideas?  Any papers that deal with this problem?
>
> ref: sys/netinet/ip_fw2.c::hash_packet6

If you are worried about users controlling which values their packets hash
to you might want to look at universal hashing. People who are worried
about algorithmic denial of service attacks face similar problems. A good
place to start would probably be: http://www.cs.rice.edu/~scrosby/hash

Paul Twohey
twohey at cs