Re: Extensible hashing and RCU

[David Miller <davem@davemloft.net>]

From: Evgeniy Polyakov <johnpol@2ka.mipt.ru>
Date: Wed, 21 Feb 2007 11:56:08 +0300

> On Tue, Feb 20, 2007 at 12:09:59PM -0800, Michael K. Edwards (medwards.linux@gmail.com) wrote:
> > On 2/20/07, Michael K. Edwards <medwards.linux@gmail.com> wrote:
> > >Correct.  That's called a "weak hash", and Jenkins is known to be a
> > >thoroughly weak hash.  That's why you never, ever use it without a
> > >salt, and you don't let an attacker inspect the hash output either.
> > 
> > Weak in a cryptographic sense, of course.  Excellent avalanche
> > behavior, though, which is what you care about in a salted hash.
> > http://en.wikipedia.org/wiki/Hash_table
> 
> I repeat again - add your salt into jenkins hash and I will show you
> that it has the same problems.
> So, I'm waiting for your patch for jhash_*_words().

The problem is that whilst XOR, with arbitrary random input
seed, can be forced to use choosen hash chains easily, with
jenkins this is not the case.

The reason is that, due to jenkin's sophisticated mixing, each
random input produces unique "pattern" of hash chains even for
the most carefully crafted inputs.

It is not trivial to target matching hash chains even with known
input seed, and it is impossible with unknown seed such as that
which we use in routing cache.

I do not talk about distribution characteristics here, only about
attackability.