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.

Excellent paper

[smiff]

Hi,

I found your paper very interesting. I'd like to address a couple things.

1. You point out that MD5 is vulnerable to a brute-force search for bucket collisions. Isn't any deterministic hash-function vulnerable to the same attack? I know you solved the problem using a keyed version of MD5. With Carter and Wegman, you alluded to a randomly chosen constant and vector. I didn't notice you addressing this issue with UMAC.

2. The abstract says, "We show how modern universal hashing techniques can yield performance comparable to commonplace hash functions while being provably secure against these attacks." The abstract is ambiguous, but it insinuates that you'll provide a proof. I didn't see one. Perhaps it was in the references? Even if it was, certainly your 20 bit Carter-Wegman construction merits a new proof.

3. You said, "When analyzing algorithmic complexity attacks, we must assume the attacker has access to the source code of the application," I disagree. The attacker doesn't need the source code. They can reverse engineer the compiled binary.

Also, I wonder if an attacker even needs the program. An attacker could reasonably guess that a Perl script will store a certain string in an associative array. Many websites automatically process their Apache logs with Perl. Instead of requesting real pages, a blackhat could request strings that will hash to the same bucket (assuming the site uses Perl). When cron starts processing the logs, the website could slow to a crawl. Granted, the attacker knows the hash function from Perl, but they don't have access to the website's custom-made script.

4. You have a spelling error. Your paper should read, "due to the ten times larger queues of unprocessed events".

Re:Excellent paper

[Anonymous Coward]

Yes, deterministic hash functions are subject to guess&check attacks.

Second, the universalness of that is from the origional carter&wegman paper. Our only real trick is to try to encode a useful construction without requiring 64-bit multpilication or modulation. There are aspects of the abstract I'm not entirely happy with. The section on solutions with unversal hashing was sorta grafted on later.(And I didn't write that sentence)

Third, yes, good guessing works too, even without source code.

Fourth. Damn. Don't you have something better to do? :)

Scott