netdev - Re: Extensible hashing and RCU

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 21 Feb 2007 12:51:09 +0300
From:	Evgeniy Polyakov <johnpol@....mipt.ru>
To:	David Miller <davem@...emloft.net>
Cc:	medwards.linux@...il.com, dada1@...mosbay.com, akepner@....com,
	linux@...izon.com, netdev@...r.kernel.org, bcrl@...ck.org
Subject: Re: Extensible hashing and RCU

On Wed, Feb 21, 2007 at 01:34:40AM -0800, David Miller (davem@...emloft.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
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html