‘Denial of Service via Algorithmic Complexity Attacks’


We present a new class of low-bandwidth denial of service attacks that exploit algorithmic deficiencies in many common applications’ data structures. Frequently used data structures have “average-case” expected running time that is far more efficient than the worst case. For example, both binary trees and hash tables can degenerate to linked lists with carefully chosen input.

We show how an attacker can effectively compute such input, and we demonstrate attacks against the hash table implementations in two versions of Perl, the Squid web proxy, and the Bro intrusion detection system. 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.’


‘The complete article in HTML is available for download from:
The complete article in PDF is available for download from:
The information has been provided by Scott A Crosby and Dan S Wallach.’


When analyzing the running time of algorithms, a common technique is to differentiate best-case, common-case, and worst-cast performance. For example, an unbalanced binary tree will be expected to consume O(nlogn) time to insert n elements, but if the elements happen to be sorted beforehand, then the tree would degenerate to a linked list, and it would take O(n^2) time to insert all n elements. Similarly, a hash table would be expected to consume O(n) time to insert n elements. However, if each element hashes to the same bucket, the hash table will also degenerate to a linked list, and it will take O(n^2) time to insert n elements.

While balanced tree algorithms, such as red-black trees, AVL trees, and traps can avoid predictable input that causes worst-case behavior, and universal hash functions can be used to make hash functions that are not predictable by an attacker, many common applications use simpler algorithms. If an attacker can control and predict the inputs being used by these algorithms, then the attacker may be able to induce the worst-case execution time, effectively causing a denial-of-service (DoS) attack.

Such algorithmic DoS attacks have much in common with other low-bandwidth DoS attacks, such as stack smashing or the ping-of-death, wherein a relatively short message causes an Internet server to crash or misbehave. While a variety of techniques can be used to address these DoS attacks, common industrial practice still allows bugs like these to appear in commercial products. However, unlike stack smashing, attacks that target poorly chosen algorithms can function even against code written in safe languages. One early example was discovered by Garfinkel, who described nested HTML tables that induced the browser to perform super-linear work to derive the tables’ on-screen layout. More recently, Stubblefield and Dean described attacks against SSL servers, where a malicious web client can coerce a web server into performing expensive RSA decryption operations. They suggested the use of crypto puzzles to force clients to perform more work before the server does its work. Provably requiring the client to consume CPU time may make sense for fundamentally expensive operations like RSA decryption, but it seems out of place when the expensive operation (e.g., HTML table layout) is only expensive because a poor algorithm was used in the system. Another recent paper is a toolkit that allows programmers to inject sensors and actuators into a program. When a resource abuse is detected, an appropriate action is taken.

This paper focuses on DoS attacks that may be mounted from across a network, targeting servers with the data that they might observe and store in a hash table as part of their normal operation. Section 2 details how hash tables work and how they can be vulnerable to malicious attacks. Section 3 describes vulnerabilities in the Squid web cache, the DJB DNS server, and Perl’s built-in hash tables. Section 4 describes vulnerabilities in the Bro intrusion detection system. Section 5 presents some possible solutions to our attack. Finally, Section 6 gives our conclusions and discusses future work.

Vulnerable products (found so far):
 * Bro 0.8a20
Confirmed vulnerable. Please see the paper. A patch exists and a fixed release will be out soon. Bro does not crash, but drop rates of 70% are experienced with an attack traffic as low as 16kbits/sec.

These are scripting languages or infrastructure libraries that are vulnerable, but the impact of attack depends on how they are used. In some cases, they may be important vulnerabilities, in other cases, irrelevant. Please see our analysis of Perl in the paper, the same applies to all of these.
 * Python 2.3b1
 * TCL 8.4.3
 * Perl 5.6.1 and 5.8.0
 * glib 2.2.1
 * Mozilla 1.3.1

These are appear to be subject to a weak attack.
 * DJBDNS 1.05
The DNS cache has an explicit limit to stop degradation from being more severe than 100x on the hash table.

 * Linux 2.4.20 dcache
Confirmed – the degradation requires the ability to construct files and is about 200x, but appears small in absolute terms.

 * Perl 5.6.1
Confirmed Insert all 10,000 strings into an associative array. See victim program

 * Perl 5.8.0
Confirmed Insert all 10,000 strings into an associative array. See victim program

 * Linux dcache 2.4.20
Confirmed Make a directory with filenames equal to those in this file. I recommend using a cut-down subset, quadratic behavior seems to cease at only a few thousand entries.

 * Bro IDS 0.8a20
Confirmed forthcoming As the attack is rather severe, it will take some time to manufacture an appropriately cut down file.

 * Python 2.3b1
This corrected file is from ‘Alexis S. L. Carvalho’ , and demonstrates the attack.

 * GLIB 2.2.1
A test program, also by ‘Alexis S. L. Carvalho’ shows a degradation on this file. ‘

Categories: Reviews