[Python-Dev] Hash collision security issue (now public) (original) (raw)
Antoine Pitrou solipsis at pitrou.net
Sun Jan 1 17:54:04 CET 2012
- Previous message: [Python-Dev] Hash collision security issue (now public)
- Next message: [Python-Dev] Hash collision security issue (now public)
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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.
- Previous message: [Python-Dev] Hash collision security issue (now public)
- Next message: [Python-Dev] Hash collision security issue (now public)
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]