Is there an exploit (PoC code) to this vulnerability (hash table collision) for python?

2011-003 multiple implementations denial-of-service via hash algorithm collision


A variety of programming languages suffer from a denial-of-service (DoS) condition against storage functions of key/value pairs in hash data structures, the condition can be leveraged by exploiting predictable collisions in the underlying hashing algorithms.

The issue finds particular exposure in web server applications and/or frameworks. In particular, the lack of sufficient limits for the number of parameters in POST requests in conjunction with the predictable collision properties in the hashing functions of the underlying languages can render web applications vulnerable to the DoS condition. The attacker, using specially crafted HTTP requests, can lead to a 100% of CPU usage which can last up to several hours depending on the targeted application and server performance, the amplification effect is considerable and requires little bandwidth and time on the attacker side.

The condition for predictable collisions in the hashing functions has been reported for the following language implementations: Java, JRuby, PHP, Python, Rubinius, Ruby. In the case of the Ruby language, the 1.9.x branch is not affected by the predictable collision condition since this version includes a randomization of the hashing function.

The vulnerability outlined in this advisory is practically identical to the one reported in 2003 and described in the paper Denial of Service via Algorithmic Complexity Attacks which affected the Perl language.

The reporters own advisory can be found at http://www.nruns.com/_downloads/advisory28122011.pdf [mods: link no longer works]


Using the link you provided, you can get the algorithms you need to write your own:

  • oCERT lists: Python 2.6.8 fixed the issue, so there should be a CVE reference in the release notes
  • Python 2.6.8 release notes shows the CVE: CVE-2012-1150
  • NIST NVD listing for CVE-2012-1150 shows the reference to the exploit
  • the exploit reference on the Python mailing list shows the link to the original notification at the top
  • the original notification lists the link to the original presentation that outlines in detail how the exploit works (in a variety of languages)
  • the original presentation shows exactly how to exploit this problem

Now, the presentation does not provide PoC code in Python, but it gives you the math to sort it out.

If you are looking for code, though, I searched for "advisory28122011.pdf" (the broken link in the CVE description) and Google returned a "meet-in-the-middle" PoC, written in Python (in order to get the hash collisions, you need to run a meet-in-the-middle attack, according to the original paper).

Google also returns "The Browser Hackers Handbook" where there is Java PoC code on page 488, a Metasploit pre-built module for PHP and Java, which should be simple enough to port to Python.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.