Better "hash_packet6"

[David Malone]

On Tue, Dec 05, 2006 at 04:17:45PM -0800, Luigi Rizzo wrote:
> I wonder if you have considered alternatives such as the one at
> 
>         http://www.azillionmonkeys.com/qed/hash.html
> 
> which seems reasonable in terms of theoretical background, performance
> and also in terms of license (see the reference about being used
> in Apple products).

I'm not familiar with this one, but it doesn't look like has been
designed to be resistant to deliberate collision attacks. I'll try
and read the description more carefully and understand it though.

> Second, and related to this specific hash function: if we end up
> using it, i think it would be good to add a bit of documentation
> on algorithm used and on constraints that there are (e.g. wrt operand
> sizes and values of the hash keys) so that people don't break it
> in the future trying to optimze things that they should not touch.

Yes - this is a very good idea. I'll try to answer your questions
below, and maybe the answers can form part of the documentation.

> In particular, i have the following questions:
> - is the algorithm defined on a byte-by-byte basis, or it is just
>   your decision to implement it this way ? (having it work on 16-bit
>   entries would e.g. halve the number of multiplies).

We can do it in larger chunks, but this would mean doing the
accumulation on a larger variable. At the moment we multiply 8 bits
by 16 bits and then sum 36 of these, resulting in at less than 30
bits, which we can keep in a 32 bit number without fear of wrapping.

(Alternatively we could do the modulo more frequently, but adding
a mod after each multiply would eliminate the value of doing things
16 bits at a time.)

> - i guess that you use addr6_cmp() to sort the components of the
>   address insuring the algorithm hashes forward and reverse traffic
>   to the same value. symmetric. But for this, one of the suggestions
>   was to xor SRC and DST to achieve the same thing, and i don't
>   understand why you use this different approach (which doubles the
>   input size and the number of multiplications).

As Max says, we sort rather than XOR, because it means that no data
is merged before going into the random hash. If we merge data in a
deterministic way, particularly in a way that lets you merge data
to the same value easily, then we end up with an easy way to attack
the hash.

> - what are the requirements on ipfw_hash_key[] values ?
>   E.g. it seems that 0 should not be allowed or the corresponding
>   byte would have no contribution in the hash. Any other invalid
>   value, recommended range etc ?

Because multiplication by a non-zero number mod a prime is invertible,
basically any non-zero number % 65537 is OK. In practice, people
don't seem to exclude zero, because it is usually hard for the
attacker to realise that zero is part of the key. I don't believe
it would hurt to exclude zero though.

We did consider the possibility of changing the:

	static u_int32_t ipfw_hash_key[HASHKEYLEN];

to

	static u_int16_t ipfw_hash_key[HASHKEYLEN];

and then changing the accumulation stages to do:

	a += blah * (u_int32_t)ipfw_hash_key[j++]

This would result in a marginal reduction in memory pressure (halving
the size of the key) and we would trade it off against an unsigned
extension and a marginal loss of security (reducing 65537^n keys
to 65536^n keys). Unsigned extension is free on a lot of processors
and probably very cheap on others, so this may still be worth doing.

	David.