Denial of Service via Algorithmic Complexity

dss902 writes "We (Department of Computer Science, Rice University) present a new class of low-bandwidth denial of service attacks that exploit algorithmic deficiencies in many common applications' data structures... Using bandwidth less than a typical dialup modem, we can bring a dedicated Bro server to its knees; after six minutes of carefully chosen packets, our Bro server was dropping as much as 71% of its traffic and consuming all of its CPU. We show how modern universal hashing techniques can yield performance comparable to commonplace hash functions while being provably secure against these attacks."

Comments

I've seen this before

[jeffy124]

Several years ago Apache had a function that ran in O(n^2) time, and a HTTP GET request was capable of throwing that function into taking a very long time to process, making it easy to DoS an Apache httpd. The interesting part is that the same function could have been done in O(n) time, but wasnt. The Apache team fixed this by substituting the O(n) algorithm.

Re:I've seen this before

[kazad]

For those too lazy to click:

Problem: remove excess slashes from a URL, so /d1///d2////d3/test.html becomes /d1/d2/d3/test.html

Original Algorithm:

If an additional slash is found, copy the remainder of the string over. So

a///b => a//b => a/b

This copying, an inner loop, makes the algorithm O(n^2).

New algorithm:

Have 2 pointers, and copy from one to the other. One pointer skips additional slashes. At the end, throw on a "\0" to terminate the string.

a///b => a/b

The second pointer has a loop to skip over additional slashes, and each slash is only visited once. Thus, the algorithm is O(n).

Cool stuff ... imagine an input like

a///...{500 slashes later}...///b

It could really do some damage to the first algorithm.

Re:I hope this isn't news to anyone...

[KrispyKringle]

It's obvious that there is already plenty of incentive to use a good hash function simply to improve performance, even if people didn't worry about intentional DOS attacks. And of course, using a better hash function is not a solution to the attack per se, any more than getting a fatter pipe is a solution to a traditional DDOS.

The issue is that even the best hash functions perform worse under very specific circumstances, i.e. high numbers of hash collisions. An earlier poster mentioned quicksort; the quicksort algorithm, while being the most (or one of the most) efficient sorting algorithms, is extremely inefficient if given an ordered set already. Obviously, a check can be added to make sure you are not sorting an already sorted algorithm.

Presumably, the same could be done for hash functions, in which, by having a bunch of different hash functions available, the software could revert to an alternate if the primary function appeared to be generating way too many collisions. Just because people hadn't thought about this much or designed software to cope doesn't mean it would be very hard to prevent against.