![wedding-crashers[1]](http://blog.eeye.com/wp-content/uploads/2011/12/wedding-crashers1-98x98.jpg "wedding-crashers[1]")
HashDoS Crashes Your New Year’s Eve Party (and your web server)
Microsoft made the last few days of 2011 somewhat exciting by releasing an out -of-band patch, the only time all year they’ve deviated from a normal Patch Tuesday distribution. We’ll update this blog with new developments, so keep checking back for new information. So, what’s all the excitement about?
The Microsoft advisory released yesterday addresses a hash collision vulnerability that affects all versions of ASP.NET. This advisory is in direct response to some very interesting research that presented at the recent Chaos Communication Congress (CCC). There, hash collisions were shown to consume all available resources in a web server. However, the theory behind this vulnerability is nothing new. As stated in the presentation, this is a known issue and the recent work is based off of theories that have been around as far back as 2003. This presentation showed that most web servers that support POST based requests are vulnerable to this issue.
Let’s Look at the Cause of the Issue
Upon receiving any POST based request, a web server will process the submitted parameters and put them into hash tables for use by the web application developers. This is completely normal and expected behavior.
These hash tables work by taking the user controlled input and running it through a mathematical equation. This equation is a many-to-one type of equation in that, it takes input from all possible inputs, and maps that input into a finite space. The mapping is then used as an index into the collection of inputs.
This type of data structure is useful for performing quick look-ups among large amounts of data. Instead of having to search all of the values in your collection, you can quickly calculate the location where it is stored and grab the element you want. There is however, a catch. When two inputs map to the same location, the hash table then has to deal with this “collision.”
Collisions of this nature can cause a system to perform a substantial amount of work, and that is exactly what is happening with this vulnerability. By submitting several parameters in the POST request that cause collisions in the hash table, the process responsible for handling incoming requests gets overwhelmed with handling these collisions. It is possible to form a rather large request in such a way that will consume all available CPU resources for that process. While that process is busy handling collisions, it won’t be able to receive any more requests and your web server will, in effect, be inaccessible.
This denial of service is particularly effective because one packet can potentially cause the server to be unresponsive for several minutes, depending on the hardware configuration on server. By flooding these specially crafted packets to a server, an attacker would be able to completely block all usability to that server.
Now, this is not some crazy and weird memory corruption, and this does not actually crash the affected server. This is an issue with hashing functions and the way they are commonly implemented in the popular web based languages. All this does is consume CPU resources and not actually crash the system, though the overall effect is the same.
Though web servers are the primary concern at the moment, this issue is technically applicable to any program that hashes user input using an algorithm that allows collisions to be easily predicted. The versatility of this vulnerability combined with the potential effects on web servers and their users definitely earn this vulnerability a gold star for criticality.
All Hope is Not Lost
Luckily, there is a fix and in fact there are many ways that this issue can be mitigated. Some vendors, such as Perl (who patched this issue using hash randomization back in 2003 with version 5.8.1) have taken steps already to address this issue. Others are following suite and are quickly releasing updates that would help prevent this attack from being exploited.
CRuby updates to version 1.9 addressed this vulnerability by including an element of randomization in their hashing function. Apache Tomcat also released updates, with versions 7.0.23 and 6.0.35 addressing the issue by limiting the number of parameters allowed by POST requests.
Microsoft released an out of cycle patch today that, among other things, addresses this problem. The bulletin, MS11-100, addresses four CVEs, with this hash collision issue (CVE-2011-3414) among them. The most critical of these CVEs does allow a remote attacker to elevate their privileges in an affected web site (CVE-2011-3416) rounding this off as a critically important vulnerability and a patch that should be applied immediately.
Of course there are also steps that can be taken in order to mitigate this vulnerability before updates can be applied. One such way is to limit how much CPU time each request is allowed. Another step would be to limit the number of parameters that your web server allows via POST requests or even to limit the overall size of the POST request in general. Due to the amount of public attention this is getting and the ease with which it is exploited; not taking immediate steps to secure your web servers could prove costly in the coming weeks as this vulnerability continues to get more and more public attention.
Detecting this Vulnerability
Our Retina family of products have been updated to check for the existence of this flaw on affected systems. You can download Retina Community here for free.
VEF/Blog Contest
Please comment on this blog and we will select the best response to win a Kindle Fire.
Permanent Link
Even if the theories had never been put into practice, the did show the vulnerability. So why would it take Microsoft over 8 years to fix it? How many versions of ASP.NET have come and gone with this flaw being passed on from generation to generation? I know Microsoft isn’t noted for swift follow up or patching, but 8 YEARS???? and then to do an out of band patch? I know they are late to the party, but I really don’t think that’s the kind of entrance any enterprise should make or even want to make… unless they figured hitting the headlines anyway at all was better than no press? I don’t get it. Oh, wait. It’s Microsoft. Enough said.
Great post, and webinar. Thanks for the details, it makes more sense with an explanation. Although, technically, isn’t a hash table a many-to-fewer to function, since it’s not all mapping to one bin (that’s the point of no collisions, right? )
Anyway, first time webinar viewer and post reader. You’ll definitely be on my RSS feed from now on, though.
The bug described here as always should be solved by default by the programmers.
Collision detection, input validation should be in their usual plan test. But deadline, knowledge limitation are still factors which could avoid such behavior.
On the other hand, some vendor/community affected by such issue have answered quickly.
The DOS is described in http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf that was published in May 2003.
Only 2 months later, Perl 5.8.1 (RC3) was released to solve the issue… vs 8 years for Microsoft !
But many others are following the Microsoft train : http://www.ocert.org/advisories/ocert-2011-003.html describe the affected OpenSource language and the version affected or not… but they are all 2011 Christmas gifts
We are focusing on Microsoft response time about it, but some other solution not based on Perl are affected too.
Anyway, the article shows that developers shouldn’t trust the platform they are coding on.. but use the best practice first and relay on vulnerability solution as yours to confirm they are not affected.
When looking at the bug, it should be interesting to check if online banking or ecommerce sites are /were affected by this issue.
But as we are now in the Cloud, such verification (without executing the real DOS) is more and more difficult. But it’s another opportunity for Vulnerability Solution to develop additional fuzzing solution.
Thanks for the article.
First, some nitpicking: it is not the web server itself that parses a POST request into a hash table based datastructure, but one layer above that: the web application server or the programming language. The web server itself typically has no need to care about the contents of POST data, but an application programmer doing anything dynamic has to have a way to access it – this is where the hash table comes in place in form of a variable/object that is autocreated when a POST request is received and parsed.
The only way to avoid this vulnerability entirely is randomizing your hash function (or switching to a different kind of data structure which does not have such a bad worst case) in order to give the attacker no chance to create those collisions in the first place.
What Microsoft has fixed (very quickly, given that they were only notified on November 29th by us, which was the day we finished the research, all the other platforms had nearly a month more time) here is only the POST parameter parsing by limiting the number of allowed POST parameters. This is reasonable, as I assume there are very little web applications which actually use more than say 50 parameters or so. So a limit of 1.000 (which is the default IIRC) is sane and severely limits the impact of the attack (it starts being interesting in about the 100.000 keys range). Similarly, there have been workaround patches for both Tomcat and PHP (release 5.3.9, which is just a few days old).
As mentioned, this only stops the POST parsing part but as correctly noted in the article, this affects all places where (lots of) attacker-controlled data is put into a hash table data structure. Where this is of course depends on your (web) application, but one thing to look in the future would be deserialization, for example in JSON, YAML, etc. As there are hash table types in the serialization format defined, those will again be deserialized into a hash table by the server. This may be the next big attack vector for those platforms which “only” provided a POST workaround (randomization is in discussion for a lot of platforms currently and is admittedly not a simple change as it affects all kind of other stuff, too).
In case you are interested in all of the details, our talk at 28C3 has been recorded and is available for viewing: http://media.ccc.de/browse/congress/2011/28c3-4680-en-effective_dos_attacks_against_web_application_platforms.html
Best,
Alex
One quick thing I forgot to mention: since a few days ago, there is public exploit code available against ASP.NET (there has been against PHP since the day of our talk), so now would be a good time to patch if you have not yet.
Best,
Alex
One more thing: we are using the @hashDoS account on Twitter to (re)tweet interesting stuff about this attack, maybe you want to follow it.
Best,
Alex