Re: [Caml-list] Hardening [Perl's] hash function further

[Gerd Stolpmann <info@gerd-stolpmann.de>]

[-- Attachment #1: Type: text/plain, Size: 2221 bytes --]

Am Mittwoch, den 20.11.2013, 19:56 +0100 schrieb Florian Weimer:
> * Dario Teixeira:
> 
> >  - Any hashtable implementation that uses a non-cryptographic hash function
> >    and relies on an association list of buckets is vulnerable to attacks
> >    that force the worst-case O(n) behaviour.  Though you can buy some time
> >    by tweaking the hash function, you are still stuck in an arms race with
> >    attackers.
> 
> You just need a keyed hash with a secret key, not a general-purpose
> cryptographic hash function.  So far, Jenkins' lookup3 function still
> stands.

The problem is this: You think you add n bits of randomness with the
secret key. But because the hash function isn't cryptographic, there
will be symmetries, and the n bits are actually not worth n bits. And
because there is no cryptanalysis we don't know how safe we are.

You don't need a giant compute centre for finding pairs (secret, keys)
where the keys collide. I'd guess a normal GPU can compute more than
1E11 hashes of that complexity per second. That way you can watch out
for keys that increase the likeliness of a collision. And that's only
the brute force method.

Also, you can test easily 100 or more different series of keys in a
single HTTP request. If you find an attack method where the original n
bits of randomness are, say, only worth 20 bits, you can shoot off the
server process within a couple of minutes. And within an hour the whole
computer. Of course, this is only speculation, but the point is that we
cannot be sure that this isn't possible.

Generally, I think it is better to change the hash table algorithm in
situations where data from untrusted sources is processed. That means
using balanced trees for the buckets. Consumes more RAM, but is provably
safe. (Or, at minimum, limit the length of the buckets.)

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 490 bytes --]