By websites, I should really have said Web Applications, but the end result is the same: A server which is serving pages on the Internet could see its CPU usage increasing to a level making that server unusable for a few minutes or more. All that from a relatively small specially crafted malicious HTTP request.

This vulnerability exists in most languages used to develop web applications: PHP, ASP.Net, Java, Python, Ruby, etc. And it has been known to exist in theory since 2003!

Last week, Alexander Klink and Julian Wilde explained at the 28th Chaos Communication Congress in Germany how exactly the theory became reality and the impact on the different web application languages were affected.

The core of the issue is the way hash lists have been implemented in those languages. By “Hash” they both refer to a specific type of data structure and the cryptographic function. A Hash list is a type of data structure that is very popular because it stores and accesses data in a list very quickly. Before an object is inserted into a hash list, it is first hashed using a hash function to provide a “unique” hash reference which is then used to access and store the object in the list. To simplify, it replaces the usual [i] of a standard list with a [hash reference]. (“i” being an integer).

In reality those hash references are not so unique and collisions do occur. When it happens the objects with the same hash reference are daisy chained. The longer the chain and the least efficient hash lists become. Under normal operation it does not happen often and this is not a problem.

But as first highlighted by Scott Crosby and Dan Wallach in 2003, data/object stored into hash lists can be manipulated so collisions do happen more often. So much more in fact, it can degenerate the hash list resulting into the server’s CPU going overdrive and bringing the server to its knee in the process.

Alexander and Julian explained at 28c3, as shown in this video, that for Perl the issue was located in how the DJBX33A (PHP5) and DJBX33X (PHP4) functions were generating hashes. Other languages were also vulnerable because they were using very similar functions to generate their hashes.

With the help of CERT they communicated an advanced advisory to the relevant vendors and organisations in early November 2011, after they successfully implemented an attack for most of the languages used by Web Applications. They received different responses, some more satisfactory than others…

Ruby reacted very quickly and has a patch ready, Microsoft has issued a temporary work around for ASP.Net by limiting the number of parameters, PHP and Python needs more time and Oracle, although they have provided a patch for Tomcat and will in a near future do the same for Glassfish, stated that it isn’t an issue for Java. If you watch the 28c3 video you can easily understand they are wrong (clue for Oracle, go to the 32d minute or so). Therefore we should expect a Java patch for the HashTable and HashMap functions soon, albeit too late.

To conclude, this is a serious issue that has now a practical and known way to exploit it, with a global scope and high performance impact. Microsoft in a Technet article has provided a snort signature to detect this type of attack against ASP.Net, it should be fairly easy to adapt for other languages.

The recommendation is to both monitor for a patch related to your web applications (and implement it quickly when available) and to also monitor your network for such attacks (and try to block its source IP if not coming from a distributed attack). You should bereviewing what are the versions of the languages used by your Internet facing web applications and probably also ask your 3rd party partners what they plan to do about it!

A nice summary is also available on Arstechnica.

PS: Thanks to Thierry for pointing the story to me in the first place!