Slashdot Mirror
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."
I hate to ruin it for everyone, but the second link has the same content as the first, only in PDF format.
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.
The One Rule Of Chess You'll Ever Need: Don't play someone who carries a kit in their bookbag.
you can use a modem to post a slashdot article with a link to the target computer...
The project page is http://www.cs.rice.edu/~scrosby/hash/ and actually has details about individual vulnerable applications and test files for several systems. (And is kinder on the server for those who don't want to download the whole paper.)
Basically, the paper says this: If you have a hash table into which attackers can insert arbitrary keys, you'd better be using a hash function for which they cannot easily generate collisions.
I don't know if anyone has *published* this before, but it's certainly not new.
Tarsnap: Online backups for the truly paranoid
I agree that DoS attacks are really lame, but at least this is fairly complex and has some interesting technological implications. Most DoS attacks are just floods of packets, and can't really be defended against. This attack can be prevented, and maybe will help improve security in other ways. I'd rather see 10 people who can pull off a preventable algorithmic complexity attack than 10,000 who just packet a server to death. People will write tools, but they'll still remain too hard for moron DDoSer script kiddies to pull off.
Since you asked nicely..
This is the HTML version (with lots of images not mirrored, sorry) and this is the PDF version.
If the PDF starts hogging the pipe, don't be surprised if it gets symlinked to the HTML version.
well, maybe they're figuring out how to fix them. Would you rather a University figuring out how to do it, or some random black hat/chinese hacker?
With this information it shouldn't be too big of a deal to redesign the software to not be vulnerable anymore.
What they did is little more than algorithm analysis. They looked at all the different links in the chain then merely decided which algorithms were the weakest links and exploited them.
This is good because we can now fix those. Robustness abound.
Reading the paper which begins with "We present a new class of ..." it sounds like these students discovered a new concept from nowhere.
Maybe their genius has been triggered by the recent advisory about a DOS exploiting hash collisions in netfilter.
They analyzed some softwares but no word about this known vulnerability. Still a good summary but not a discovery.
They exploit the difference between 'typical case' behavior versus worst-case behavior. For instance, in a hash table, the performance is usually O(1) for all operations. However in an adversarial environment, the attacker constructs carefully chosen input such that large number of 'hash collisions' occur. Suitable collisions can be computed even when the attacker is limited to as little as 48 or 32 bits.
These attacks can occur over a very wide gamut of software, with impacts ranging from devestating to innocious.
We have studied and found the following applications possibly vulnerable to a greater or lesser degree:
For the last two, we have a tentative attack file, but have not constructed a test program to confirm the attack.
We have constructed attacks and confirmed the degradation on these:
Also related is the recent linux 2.4.20 route cache attack by Florian Weimer. David Miller is working on a patch that fixes other similar issues in other places of the networking stack.
Our paper discusses a new class of denial of service attacks that work by exploiting the difference between average case performance and worst-case performance. In an adversarial environment, the data structures used by an application may be forced to experience their worst case performance. For instance, hash tables are usually thought of as being constant time operations, but with large numbers of collisions will degrade to a linked list and may lead to a 100-10,000 times performance degradation. Because of the widespread use of hash tables, the potential for attack is extremely widespread. Fortunately, in many cases, other limits on the system limit the impact of these attacks.
To be attackable, an application must have a deterministic or predictable hash function and accept untrusted input. In general, for the attack to be signifigant, the applications must be willing and able to accept hundreds to tens of thousands of 'attack inputs'. Because of that requirement, it is difficult to judge the impact of these attack without knowing the source code extremely well, and knowing all ways in which a program is used.
The solution for these attacks on hash tables is to make the hash function unpredictable via a technique known as universal hashing. Universal hashing is a keyed hash function where, based on the key, one of a large set hash functions is chosen. When benchmarking, we observe that for short or medium length inputs, it is comparable in performance to simple predictable hash functions such as the ones in Python or Perl.
I highly advise using a universal hashing library, either our own or someone elses. As is historically seen, it is very easy to make silly mistakes when attempting to implement your own 'secure' algorithm.
The abstract, paper, and a library implementing universal hashing is available at http://www.cs.rice.edu/~scrosby/hash/.
Scott
** Affected Products: Extremely widespread. Confirmed vulnerable applications include Perl, the Linux kernel, the Bro IDS, and the Squid HTTP proxy cache. Although unconfirmed, vulnerablities appear to be in the GLIB utility library, the OpenBSD kernel, DJBDNS cache, TCL, Python, and Mozilla.
We conjecture that many implementations of hash tables in both closed source and open source software, unless specifically designed to be immune, may be subject to attack. It is likely
I skimmed the Project Page and aren't a couple of the examples awefully obvious?
The following one line of code brings every UNIX system I've run it on TO ITS KNEES WITHIN MINUTES!! This is a major vulnerability in EVERY UNIX system! Something must be done!
I think he means with the slashdotting.
My brain is resistant to attacks using algorithmic complexity