[Python-Dev] Hash collision security issue (now public)

[Christian Heimes]

Am 31.12.2011 13:03, schrieb Stephen J. Turnbull:
> I don't know the implementation issues well enough to claim it is a
> solution, but this hasn't been mentioned before AFAICS:
> 
> While the dictionary probe has to start with a hash for backward
> compatibility reasons, is there a reason the overflow strategy for
> insertion has to be buckets containing lists?  How about
> double-hashing, etc?

Python's dict implementation doesn't use bucket but open addressing (aka
closed hashed table). The algorithm for conflict resolution doesn't use
double hashing. Instead it takes the original and (in most cases) cached
hash and perturbs the hash with a series of add, multiply and bit shift ops.