CVE-2012-0039: Algorimic Complexity Attack on GLIB 2.2.1

• From: Scott A Crosby <scrosby cs rice edu>
• To: gtk-devel-list gnome org
• Subject: Algorimic Complexity Attack on GLIB 2.2.1
• Date: 29 May 2003 15:33:10 -0500

Hello. We have analyzed this software to determine its vulnerability to a new class of DoS attacks that related to a recent paper. ‘’Denial of Service via Algorithmic Complexity Attacks.’’

This 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.

As part of this project, I have examined GLIB 2.2.1, and the hash function ‘g_str_hash’ is deterministic. Thus, those who use it may vulnerable to the attacks I discuss. Also, its design is such that fast collisions are easy to generate. This means that *any* program using glib that hashes a large number of keys from an untrusted source is potentially subject to a severe performance degradation. GTK-Gnutella would seem vulnerable, among others.

Depending on the application, this could be a critical DoS.

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. Our paper has graphs and charts of our benchmarked performance.

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

• Follow-Ups:
  • Re: Algorimic Complexity Attack on GLIB 2.2.1
    • From: Sander Vesik
  • Re: Algorithmic Complexity Attack on GLIB 2.2.1
    • From: Owen Taylor

[Date Prev][Date Next] [Thread Prev][Thread Next] [Thread Index] [Date Index] [Author Index]