Re: Extensible hashing and RCU

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

On Wed, Feb 21, 2007 at 01:34:40AM -0800, David Miller (davem@davemloft.net) wrote:
> > 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.

Routing cache is safe in that regard, that found problem seems to only
affect the case, when $c parameter is specially crafted - at least I
can not reproduce distribution problem with first two parameters
changed.

But having different initial value, i.e. 
hash(const, const, random_from_attacker, random_per_boot) instead of 
hash(const, const, random_from_attacker, 0) ends up in the same problem.
Attacker will not know which chain is selected, but changing that
parameter will only change chain position, but distribution will be 
still broken.

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

It _seems_ (no full analysis) that problem is in the nature of jenkins 
hash - no matter how $initval is selected, its third parameter should 
_not_ be changed to data controlled by attacker, otherwise result is 
reproduced pretty easy.

Linux route cache does not change $c (third parameter), and it _seems_
that distribution for the random $a and $b is fair, while when $c is
formed over attacker's data, random per-boot $initval does not help.

In that regard jhash_2/1words() are only safe - they have $c as zero,
jhash_3words() with attackers $c and random per-boot $initval is
trivially attackable.

-- 
	Evgeniy Polyakov