Re: Extensible hashing and RCU

[Evgeniy Polyakov <johnpol@2ka.mipt.ru>]

On Wed, Feb 21, 2007 at 10:15:11AM +0100, Eric Dumazet (dada1@cosmosbay.com) wrote:
> On Wednesday 21 February 2007 09:54, Evgeniy Polyakov wrote:
> > I shown that numbers 4 times already, do you read mails and links?
> > Did you see an artifact Eric showed with his data?
> >
> 
> I showed all your thinking is wrong.

You mix all the time distribution fairness and complexity of searching
for collisions. Jenkins hash is unfair - having Linux random generator
as attacker's tool we end up in the case, when jenkins hash has some
chains with 5 times longer length.

Short history:
I showed that jenkins is unfair, you confirmed that with your data.
Another question is about complexity of searching for collisions - you
showed that with xor it is quite easy and with jenkins it is complex, 
then I showed that it is not that complex to find collisions in jenkins
too.

> Some guys think MD5 checksum is full of artifacts, since its certainly 
> possible to construct two differents files having the same md5sum.
> Yet, lot of people use md5 checksums. In 10 years, we probably switch to 
> another stronger hash. Its only a question of current state of the art.

It is _NOT_ about having two imputs with the same output.
It is about its distribution.

I say that having random input output will not be fairly distributed -
and it was confirmed by you - having 2^16 random values ended up with
some chains of length 4, while hash table size perfectly allowed them
all to have length 1 as was in case of xor hash.

> Jenkins hash is far better than XOR, at least in the tcp ehash context.

How it can be better than xor when its distribution is unfair?
You get hash chain longer with it compared to xor one - _you_ showed
that data too if you do not believe my data.

> Some hackers already exploited the XOR hash weak, more than two years ago.
> They never succeeded since I changed to Jenkins hash.

It is _different_ problem. It has _absolutely_ nothing in common with
distribution fairness problem found in jenkins hash, do not mix both.

XOR has only one problem - it is quite easy to find a collision, but it
has perfect distribution fairness.

Fix XOR, add random permutation, use sha/md5/whatever which has 
1. fair distribution
2. strong against searching for collisions

Jenkins hash does not have at least first, and as I showed, it is not
that complex to break second (for example case of hash(const, const,
random)).

-- 
	Evgeniy Polyakov