Date: 29 May 2003 15:33:06 -0500
From: Scott A Crosby <scrosby@...rice.edu>
To: bugtraq@...urityfocus.com
Subject: Algorimic Complexity Attacks



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

Powered by blists - more mailing lists