Re: ipv4: Simplify ARP hash function.

[Roland Dreier <roland@purestorage.com>]

>> Doesn't seem to matter much -- this is now equivalent to
>>
>>       a = key ^ dev->ifindex
>>        return (a ^ (a >> 8) ^ (a >> 16) ^ (a >> 24))           // (1)
>>             ^ (rnd ^ (rnd >> 8) ^ (rnd >> 16) ^ (rnd >> 24))   // (2)
>>
>> where again the attacker controls (1), and (2) is a constant.

> Right, but how can you attack it?  Show me how you can grow
> a hash chain of arbitrary length by modulating the key in
> a deterministic way.

Well, if two things hash to different buckets with the full hash
function, then they already hashed to different buckets without
the extra randomness.  So why bother with hash_rnd?

The answer is that you have to mix hash_rnd into the hash
in a nonlinear way, so that an attacker can't know if two values
end up in the same bucket or not.

With your hash function, the attacker can just compute the
hash (without hash_rnd) for all the values of key ^ ifindex
and then use all the values that end up in the same bucket.

 - R.