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've seen this before

[Henry Stern]

In fact, you can do it with even less memory. All that you need to do is keep an offset stored in a variable.

The algorithm looks something like:

offset = 0
for i = 2 to n do
if a[i-1] = '/' and a[i] = '/' then
offset = offset + 1
else
a[i-offset] = a[i]
end if
end for

It saves you the trouble of having to manage the memory containing the cleaned-up string.

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.

Re:DOS attack

[Alomex]

I have often wondered if the /. effect is not magnified by inefficiencies in the TCP/IP stack. I mean, a lot of people read /. but say, a server should have enough bandwidth to serve twenty users per second, 1200 per minute, 72,000 per hour... I doubt there is more than that many /. actives at any given time...

HTML tables rendering bugs...

[reflective recursion]

should not be considered a Denial of Service. If anything, call it what it truely is: shoddy programming. There is nothing being denied when it is the client that has the problem.

Another thing.. this is nothing new. A number of DoS attacks require the server to do more than the client requests. The attacker's complexity would be O(n) whereas the server would be O(n^2) or some such, where n is any given method of communication. The only "new" thing would perhaps be looking at individual programs and algorithms, which is probably applying a very liberal definition of "new." They even admit it themselves by claiming ping-of-death and stack smashing have much in common with what they describe in the article.

Re:glib example

[JCMay]

because in most C implmentations the for keyword is actually done as a macro:

#define for(a;b;c){d} {a;while(b){d;c;}}

or

#define for(a;b;c){d} {a;do{d;c}while(b);}

or some such... :)

I suppose that some people would think that a while() or do{} loop is "purer"
than for() in C.

And this is new?

[thesupraman]

Well, back in 1990 when I started in university computer science, this *was* one of the main things that a denial of service attack was considered to be.

DoS attacks were mainly either removal of a service (by crashing it and/or stoping it's reload) or resource starvation, being any of CPU, disk, memory, network, etc.

Good to see these people have bothered to flick through a bit of history probably over 15 years old by now and call it something new, yawn.

Having had enough background in large computer systems, it can become quite depressing watching the constant flow of 'new innovations' that have been done may many years before on big iron, but are seen as new by people who just don't have the experience to realise.

Of course it is easier to DoS a machine by using it's own functionality against it rather than just brute force, welcome to computer science 101.

Just wait six months and someone will be releasing a fantastic new defense against this by limiting the CPU resources of given tasks to defined amounts so they cannot stop the system and only that particular service.

I mean come on, this was a common undergrad trick on the vaxes we used to get to play with way back then.

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