Algorimic Complexity Attacks

[Scott A Crosby]

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

[Solar Designer]

On Thu, May 29, 2003 at 03:33:06PM -0500, Scott A Crosby wrote:
> 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.

This is precisely one of the attacks which have been considered,
avoided(*), and documented in my Phrack #53 article entitled "Designing
and Attacking Port Scan Detection Tools" - "Data Structures and
Algorithm Choice" back in 1998. Now you report another port scan
detector (Bro) still vulnerable to this attack. I'm not surprised.

(*) http://www.openwall.com/scanlogd/

As for solutions, while using a keyed hash function offers the best
performance with a large enough number of entries (but not with a
small one!), it is rather complicated when done right, too easy to do
wrong, and may be imperfect anyway because of timing leaks (see
below). It requires that a cryptographically random secret is used
(and really kept secret!), that it is large enough to not be
successfully brute-forced, and a cryptographic hash function is used
(or it might be possible to infer the secret). This is why a hashing
library like yours is needed. But for many applications it could make
more sense to use another data structure and algorithm (such as binary
search).

Now the promised attack on using a keyed hash function with the above
requirements met. Let's assume that all input to the hash function,
except for the secret, is under control of an attacker. Further,
let's assume that she is able to infer if a hash collision occurs by
measuring the time it takes to process a request (possibly repeating
each request multiple times). After a bit of trying, she will know
that inputs A and B produce a collision. She will then keep A and B
fixed and search for an input C which will collide with A and B. And
so on.

Changing the secret once in a while reduces this attack and may well
make it impractical with many particular applications. Note that one
doesn't have to use any additional true randomness (and possibly
exhaust the randomness pool) for each new secret to be used with the
keyed hash. If the secret itself is not leaked in the attack (and it
shouldn't be), something as simple as secret++ could suffice.
However, this does have its difficulty: maintaining existing entries.

--
Alexander Peslyak <solar@openwall.com>
GPG key ID: B35D3598 fp: 6429 0D7E F130 C13E C929 6447 73C3 A290 B35D 3598
http://www.openwall.com - bringing security into open computing environments

[Pavel Kankovsky]

On Sat, 7 Jun 2003, Nicholas Weaver wrote:

> > First, let us observe the attacker needs no less than O(h) inserts (where
> > h is the size of the hash table) to find a collision of an unknown hash
> > function with a non-negligible probability of success.
>
> Actually, thanks to the Birthday paradox, it is O(sqrt(h)) when
> collisions start to appear.

Ugh. *bang* *bang* *bang* (This was my head hitting my desk.)
Of course, you are right.

Fortunately, the attacker needs much more than a single collision to carry
out the kind of attack being discussed. He needs to find a set of keys S
such that: 1. F(x) = F(y) for each x, y in S (where F is the hash
function), 2. |S| is large enough, say \Omega(log h) (*).

As far as I remember one needs to try out something like \Omega(h)
randomly chosen keys to find such a set with a non-negligible probability
(**). And any attacker's choice of keys can be considered random when the
hash function is (pseudo)random from the attacker's POV.

(*) Asymptotically equal or greater than C log h for some positive
constant C.

(**) Having a constant (i.e. not dependent on h) positive lower bound.

> Likewise, another solution is to simply use a GOOD cryptographic
> function for your hash. If, for an attacker to create h(y) == h(x),
> requires the attacker to discover the key used in the hash function or
> otherwise break the hash function, simply make sure that the key is
> well created and use a strong cypher as the basis of the hash
> function.

We need a function having a (relatively) small set of results in order to
build a hash table. We can also assume the information about collisions
leaks out via a timing channel. Ergo, a persistent attacker can find
enough collisions by trial and error.


--Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."

[Nicholas Weaver]

On Sun, Jun 08, 2003 at 06:17:38PM +0200, Pavel Kankovsky composed:
>
> We need a function having a (relatively) small set of results in order to
> build a hash table. We can also assume the information about collisions
> leaks out via a timing channel. Ergo, a persistent attacker can find
> enough collisions by trial and error.

IF the hash is good, FINDING collisions doesn't necessarily help the
attacker, as the attacker really needs to generate lots of collisions
to make the searches O(n) instead of O(1), since that is teh key
behind this attack.

--
Nicholas C. Weaver nweaver@cs.berkeley.edu

[Pavel Kankovsky]

On Sat, 7 Jun 2003, Nicholas Weaver wrote:

> > First, let us observe the attacker needs no less than O(h) inserts (where
> > h is the size of the hash table) to find a collision of an unknown hash
> > function with a non-negligible probability of success.
>
> Actually, thanks to the Birthday paradox, it is O(sqrt(h)) when
> collisions start to appear.

Ugh. *bang* *bang* *bang* (This was my head hitting my desk.)
Of course, you are right.

Fortunately, the attacker needs much more than a single collision to carry
out the kind of attack being discussed. He needs to find a set of keys S
such that: 1. F(x) = F(y) for each x, y in S (where F is the hash
function), 2. |S| is large enough, say \Omega(log h) (*).

As far as I remember one needs to try out something like \Omega(h)
randomly chosen keys to find such a set with a non-negligible probability
(**). And any attacker's choice of keys can be considered random when the
hash function is (pseudo)random from the attacker's POV.

(*) Asymptotically equal or greater than C log h for some positive
constant C.

(**) Having a constant (i.e. not dependent on h) positive lower bound.

> Likewise, another solution is to simply use a GOOD cryptographic
> function for your hash. If, for an attacker to create h(y) == h(x),
> requires the attacker to discover the key used in the hash function or
> otherwise break the hash function, simply make sure that the key is
> well created and use a strong cypher as the basis of the hash
> function.

We need a function having a (relatively) small set of results in order to
build a hash table. We can also assume the information about collisions
leaks out via a timing channel. Ergo, a persistent attacker can find
enough collisions by trial and error.


--Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."

[Nicholas Weaver]

On Sun, Jun 08, 2003 at 06:17:38PM +0200, Pavel Kankovsky composed:
>
> We need a function having a (relatively) small set of results in order to
> build a hash table. We can also assume the information about collisions
> leaks out via a timing channel. Ergo, a persistent attacker can find
> enough collisions by trial and error.

IF the hash is good, FINDING collisions doesn't necessarily help the
attacker, as the attacker really needs to generate lots of collisions
to make the searches O(n) instead of O(1), since that is teh key
behind this attack.

--
Nicholas C. Weaver nweaver@cs.berkeley.edu