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.