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

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/)