Victor Stinner writes: > Let's try to summarize this "vulnerability". > > The creation of a Python dictionary has a complexity of O(n) in most > cases, but O(n^2) in the *worst* case. The attack tries to go into the > worst case. It requires to compute a set of N keys having the same hash > value (hash(key1) == hash(key2) == ... hash(keyN)). It only has to > compute these keys once. It looks like it is now cheap enough in > practice to compute this dataset for Python (and other languages).
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-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
