On Thu, 29 May 2003 21:54:20 -0400, Tim Peters <tim.one@comcast.net> writes:
I've got one meta-comment here:
[Scott A Crosby]
Hello. We have analyzed this software to determine its vulnerability to a new class of DoS attacks that related to a recent paper. ''Denial of Service via Algorithmic Complexity Attacks.''
I don't think this is new. For example, a much simpler kind of attack is to exploit the way backtracking regexp engines work -- it's easy to find regexp + target_string combos that take time exponential in the sum of the lengths of the input strings. It's not so easy to recognize such a pair when it's handed to you. In Python, exploiting unbounded-int arithmetic is another way to soak up eons of CPU with few characters, e.g.
10**10**10
These ways require me having the ability to feed a program, an expression, or a regular expression into the victim's python interpreter. The attack I discuss only require that it hash some arbitrary input by the attacker, so these attacks apply in many more cases.
will suck up all your CPU *and* all your RAM. Another easy way is to study a system's C qsort() implementation, and provoke it into quadratic-time behavior (BTW, McIlroy wrote a cool paper on this in '98:
This is a very cool paper in exactly the same vein as ours. Thanks.
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.
I disagree. Changing the hash function eliminates these attacks on hash tables. Scott