[Python-Dev] Hashing proposal: 64-bit hash (original) (raw)

Serhiy Storchaka storchaka at gmail.com
Sat Jan 28 11🔞34 CET 2012

27.01.12 23:08, Frank Sievertsen написав(ла):

As already mentioned, the vulnerability of 64-bit Python rather theoretical and not practical. The size of the hash makes the attack is extremely unlikely. Unfortunately this assumption is not correct. It works very good with 64bit-hashing. It's much harder to create (efficiently) 64-bit hash-collisions. But I managed to do so and created strings with a length of 16 (6-bit)-characters (a-z, A-Z, 0-9, , .). Even 14 characters would have been enough. You need less than twice as many characters for the same effect as in the 32bit-world.

The point is not the length of the string, but the size of string space for inspection. To search for a string with a specified 64-bit hash to iterate over 2 ** 64 strings. Spending on a single string scan 1 nanosecond (a very optimistic estimate), it would take 2 ** 64 / 1e9 / (3600 * 24 * 365.25) = 585 years. For the attack we need to find 1000 such strings -- more than half a million years. For 32-bit hash would need only an hour.

Of course, to calculate the hash function to use secure, not allowing "cut corners" and reduce computation time.

More information about the Python-Dev mailing list