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]

Message-ID: <20070220165907.GB24930@2ka.mipt.ru>
Date:	Tue, 20 Feb 2007 19:59:07 +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 Tue, Feb 20, 2007 at 05:38:19PM +0100, Eric Dumazet (dada1@...mosbay.com) wrote:
> > It is secrecy, not security - attacker will check the source and find
> > where constant per-boot value is added and recalculate attack vector -
> > we all were college students, it would be even more fun to crack.
> >
> > In that regard Jenkins ahsh and XOR one have _exactly_ the same attack
> > vector, only Jenkins is a bit more sophisticated. I even think that
> > example in rt_hash_code() will endup with heavy problems when one of the
> > addresses is constant - my tests show problem exactly in the case of
> > jhash_2words() with random third parameter and constant one of the first
> > like in rt_hash_code().
> 
> Please define heavy problem.
> 
> On most hosts, with one NIC, one IP address, most entries in cache have the 
> same address (IP address of eth0 or localhost). It just works.
> 
> Last time I checked, the 2^21 route cache I am using was correctly filled, 
> thanks to jhash.
> 
> Again, the random value is 32bits. If jhash happens to be cracked by your 
> students, we just put md5 or whatever in...
>
> You can call it secrecy or whatever, fact is : it's just working, far better 
> than XOR previous hash function.

Hmm, I've just ran following test:
1. created 2^20 hash table.
2. ran in loop (100*(2^20) iterations) following hashes:
 a. xor hash (const_ip, const_ip, random_word)
 b. jhash_3words(const_ip, const_ip, random_word, 123123) - it is
	 exactly as jhash_2words(const_ip, const_ip, wandom_word)
3. hash &= hash_size - 1;
4. table[hash].counter++;
5. 	for (i=0; i<hash_size; ++i)
		results[table[i].counter]++;

And got pretty artefact for jenkins hash attached in the picture
artefact.png. Distribution.png file contains distribution of the 2^10
hash table for 100*(2^10) for the above scenario.

I've attached source code and running script.
$ ./run.sh

will produce gnuplot window with shown artefact.

If one change comments at the end of the file, run.sh will produce
distribution graphs.

P.S. jenkins hash is about two times slower.

-- 
	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