[Python-Dev] Algoritmic Complexity Attack on Python (original) (raw)

Raymond Hettinger python@rcn.com
Sat, 31 May 2003 14:34:13 -0400

> On Fri, May 30, 2003 at 08:41:54PM -0400, Guido van Rossum wrote: > > Of course, such programs are already vulnerable to changes in the hash > > implementation between Python versions (which has happened before). > > Is there at least a guarantee that the hashing algorithm won't change in a > bugfix release? For instance, can I depend that > python222 -c 'print hash(1), hash("a")' > python223 -c 'print hash(1), hash("a")' > will both output the same thing, even if > python23 -c 'print hash(1), hash("a")' > and > python3000 -c 'print hash(1), hash("a")' > may print something different?

That's a reasonable assumption, yes. We realize that changing the hash algorithm is a feature change, even if it is a very subtle one.

For Scott's proposal to work, it would have to change the hash value on every invocation of Python. If not, colliding keys can be found with a Monte Carlo method.

Raymond Hettinger