Hello. This is to announce a new class of attack which we have named 'Algorithmic Complexity Attack'. These attacks can perform denial of service and/or cause the victim to consume more CPU time than expected. We have a website for our research paper and project and tentative source code illustrating the solution, universal hashing, available at http://www.cs.rice.edu/~scrosby/hash/ 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: Mozilla 1.3.1 DJBDNS 1.05 TCL 8.4.3 GLIB 2.2.1 Python 2.3b1 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: Perl 5.6.1 Perl 5.8.0 Linux 2.4.20 directory cache (dcache) Squid 2.5STABLE1 Bro IDS 0.8a20 Also related is the recent linux 2.4.20 route cache attack by Florian Weimer. David Miller is working on a patch that fixes that and 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, 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 that many unexamined applications are also vulnerable. ** Impact: Varies from insignifigant to critical, depending on application and application's configuration. ** Risk: Remote and local attackers can cause system or application performance to degrade. ** Deployment: Confirmed or possibly vulnerable applications are extremely widely deployed. ** Ease of Exploitation: Relatively straightforward. The attacker compute a set of input that causes collisions. In many cases, 15 minutes of code inspection, twenty seconds programming and two hours of CPU time. ** Is exploit code available publicly? It is not known to be available publically. However, small demonstration files for several applications are available on the project page at http://www.cs.rice.edu/~scrosby/hash
