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: > > http://www.cs.dartmouth.edu/~doug/mdmspe.pdf 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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4