Re: ipv4: Simplify ARP hash function.

W dniu 8 lipca 2011 22:10 użytkownik Michał Mirosław [off-list ref] napisał:

2011/7/8 David Miller [off-list ref]:

quoted

From: David Miller <davem@davemloft.net>
Date: Fri, 08 Jul 2011 12:51:18 -0700 (PDT)

quoted

From: Michał Mirosław <redacted>
Date: Fri, 8 Jul 2011 21:39:18 +0200

quoted

With b[3] = b[0] ^ b[1] ^ b[2] you get 2^24 keys that hash to the same bucket.

Ok, I'm convinced, thanks :-)

Although, actually it's not this simple.  The attack doesn't work.

As they "attack" us, the ARP hash table grows and thus the hash mask
changes to match.  Then his old collisions won't collide any more.

We could even adjust the fold shifts as the table grows to make this
effect even more pronounced.

There will still be 2^32/n_buckets known values that hash to the same
bucket for every n_buckets. So if the attacker knows when and how the
hash size changes, he can adapt accordingly. It should be easier to
see when you get rid of the XOR [random, but] constant part.

BTW, am I correct, that neighbour hash tables never shrink? Looking at
net/core/neighbour.c it seems that after the table reaches gc_thresh3
capacity, it is never reallocated again.

Best Regards,
Michał Mirosław