[Python-Dev] Hashing proposal: 64-bit hash

[Serhiy Storchaka]

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.