mailing list archives
Algorimic Complexity Attacks
From: Scott A Crosby <scrosby () cs rice edu>
Date: 29 May 2003 15:33:06 -0500
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
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:
Linux 2.4.20 directory cache (dcache)
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
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/.
** 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.
Varies from insignifigant to critical, depending on application
and application's configuration.
Remote and local attackers can cause system or application
performance to degrade.
Confirmed or possibly vulnerable applications are extremely
** 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
** 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
- Algorimic Complexity Attacks Scott A Crosby (May 30)