[Python-Dev] Algoritmic Complexity Attack on Python

Guido van Rossum guido@python.org
Fri, 30 May 2003 07:39:18 -0400

[Tim Peters]
> > I'm uninterested in trying to "do something" about these.  If
> > resource-hogging is a serious potential problem in some context, then
> > resource limitation is an operating system's job, and any use of Python (or
> > Perl, etc) in such a context should be under the watchful eyes of OS
> > subsystems that track actual resource usage.

[Scott Crosby]
> I disagree. Changing the hash function eliminates these attacks on
> hash tables.

At what cost for Python?  99.99% of all Python programs are not
vulnerable to this kind of attack, because they don't take huge
amounts of arbitrary input from an untrusted source.  If the hash
function you propose is even a *teensy* bit slower than the one we've
got now (and from your description I'm sure it has to be), everybody
would be paying for the solution to a problem they don't have.  You
keep insisting that you don't know Python.  Hashing is used an awful
lot in Python -- as an interpreted language, most variable lookups and
all method and instance variable lookups use hashing.  So this would
affect every Python program.

Scott, we thank you for pointing out the issue, but I think you'll be
wearing out your welcome here quickly if you keep insisting that we do
things your way based on the evidence you've produced so far.

--Guido van Rossum (home page: http://www.python.org/~guido/)