[Python-Dev] Hash collision security issue (now public)

Antoine Pitrou solipsis at pitrou.net
Sun Jan 1 17:54:04 CET 2012


Le dimanche 01 janvier 2012 à 17:34 +0100, Christian Heimes a écrit :
> Am 01.01.2012 17:09, schrieb Antoine Pitrou:
> > On Sun, 01 Jan 2012 16:48:32 +0100
> > Christian Heimes <lists at cheimes.de> wrote:
> >> The talkers claim and have shown that it's too easy to pre-calculate
> >> collisions with hashing algorithms similar to DJBX33X / DJBX33A. It
> >> might be a good idea to change the hashing algorithm, too. Paul as
> >> listed some new algorithms. Ruby 1.9 is using FNV
> >> http://isthe.com/chongo/tech/comp/fnv/ which promises to be fast with a
> >> good dispersion pattern.
> > 
> > We already seem to be using a FNV-alike, is it just a matter of
> > changing the parameters?
> 
> No, we are using something similar to DJBX33X. FNV is a completely
> different type of hash algorithm.

I don't understand. FNV-1 multiplies the current running result with a
prime and then xors it with the following byte. This is also what we do.
(I'm assuming 1000003 is prime)

I see two differences:
- FNV starts with a non-zero constant offset basis
- FNV uses a different prime than ours

(as a side note, FNV operates on bytes, but for unicode we must operate
on code points in [0, 1114111]: although arguably the common case is
hashing ASCII substrings (protocol tokens etc.))

Regards

Antoine.




More information about the Python-Dev mailing list