[Python-Dev] Status of the fix for the hash collision vulnerability (original) (raw)

Mark Dickinson dickinsm at gmail.com
Fri Jan 13 19:13:08 CET 2012

On Fri, Jan 13, 2012 at 5:43 PM, Guido van Rossum <guido at python.org> wrote:

How pathological do you consider the set

{1 << n for n in range(2000)}_ _to be?  What about the set:_ _ieee754powersoftwo = {2.0**n for n in range(-1074, 1024)}_ _?  The > 2000 elements of the latter set have only 61 distinct hash values on 64-bit machine, so there will be over 2000 total collisions involved in creating this set (though admittedly only around 30 collisions per hash value). Hm... So how does the collision counting work for this case?

Ah, my bad. It looks like the ieee754_powers_of_two is safe---IIUC, it's the number of collisions involved in a single key-set operation that's limited. So a dictionary with keys {1<<n for n in range(2000)} is fine, but a dictionary with keys {1<<(61*n) for n in range(2000)} is not:

_{1<<(n*61):True for n in range(2000)}_ Traceback (most recent call last): File "", line 1, in File "", line 1, in KeyError: 'too many hash collisions' [67961 refs]

I'd still not consider this particularly pathological, though.

-- Mark

More information about the Python-Dev mailing list