[Python-Dev] Status of the fix for the hash collision vulnerability

["Martin v. Löwis"]

Am 13.01.2012 18:08, schrieb Mark Dickinson:
> On Fri, Jan 13, 2012 at 2:57 AM, Guido van Rossum <guido at python.org> wrote:
>> How
>> pathological the data needs to be before the collision counter triggers? I'd
>> expect *very* pathological.
> 
> How pathological do you consider the set
> 
>    {1 << n for n in range(2000)}
> 
> to be?  

I think this is not a counter-example for the proposed algorithm (at
least not in the way I think it should be implemented).

Those values may collide on the slot in the set, but they don't collide
on the actual hash value.

So in order to determine whether the collision limit is exceeded, we
shouldn't count colliding slots, but colliding hash values (which we
will all encounter during an insert).

> though admittedly only around 30 collisions per hash value.

I do consider the case of hashing integers with only one bit set
pathological. However, this can be overcome by factoring the magnitude
of the number into the hash as well.

Regards,
Martin