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:27:17 +0300
From:	Evgeniy Polyakov <johnpol@....mipt.ru>
To:	Eric Dumazet <dada1@...mosbay.com>
Cc:	"Michael K. Edwards" <medwards.linux@...il.com>,
	David Miller <davem@...emloft.net>, akepner@....com,
	linux@...izon.com, netdev@...r.kernel.org, bcrl@...ck.org
Subject: Re: Extensible hashing and RCU

On Wed, Feb 21, 2007 at 10:15:11AM +0100, Eric Dumazet (dada1@...mosbay.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
-
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