Several vendors are currently working to resolve a hash collision vulnerability, which if exploited can trigger a denial-of-service condition on multiple platforms.
Update: Microsoft to Issue Emergency Fix to Address Hash Collision Attack Vulnerability
The problem was first researched and exposed in 2003, but recent research has discovered the issue on a wider scale, including most of the mainstream web development platforms deployed today.
At issue is the POST function, which can be perverted to trigger the DDoS, if targeted on a massive scale, or DoS if targeted from a single source. According to n.runs AG, the research firm who discovered the issue, the usage of hash tables in Perl and CRuby was found vulnerable to collisions in 2003, prompting the platforms to alter how hashes were used, and introducing randomization.
Eight years later, the vulnerability has been discovered to impact PHP 5, Java, .NET, and Google’s v8, while PHP 4, Ruby, and Python are somewhat vulnerable. The Ruby security team has addressed the issue, as well as Tomcat. Oracle says nothing needs to be done, and Microsoft has issued an advisory on the problems within ASP.NET.
“Hash tables are a commonly used data structure in most programming languages. Web application servers or platforms commonly parse attacker-controlled POST form data into hash tables automatically, so that they can be accessed by application developers,” n.runs AG’s report explains.
“One of the most critical properties of a hash function, from a security point of view, is that it be collision resistant. In other words, there should be no method faster than brute force that allows you to find two inputs that produce the same hash value,” Chris Eng, Vice President of Research at Veracode told SecurityWeek. “Inadequate collision resistance is what led to the ‘MD5 considered harmful today’ paper in 2008 which allowed researchers to create a rogue certificate authority. The hash functions used by ASP.NET, Java, PHP, and the other technology platforms in the advisory are vulnerable to such attacks. When the attacker sends hundreds of thousands of form values that produce the same hash value, it creates significant additional work for the CPU, which causes the DoS condition.”
“If the language does not provide a randomized hash function or the application server does not recognize attacks using multi-collisions, an attacker can degenerate the hash table by sending lots of colliding keys. The algorithmic complexity of inserting n elements into the table then goes to O(n**2), making it possible to exhaust hours of CPU time using a single HTTP request,” n.runs’ report continues.
“Any website running one of the above technologies which provides the option to perform a POST request is vulnerable to very effective DoS attacks. As the attack is just a POST request, it could also be triggered from within a (third-party) website. This means that a cross-site-scripting vulnerability on a popular website could lead to a very effective DDoS attack (not necessarily against the same website),” the n.runs report concludes.
“The impact of this vulnerability is similar to other Denial of Service attacks that have been released in the past, such as the Slowloris DoS or the HTTP POST DoS,” Eng added. “Unlike traditional DoS attacks, they could be conducted with very small amounts of bandwidth. This hash table multi-collision bug shares that property. What’s particularly unique about this bug is that it affects a broader range of platforms and technologies in a virtually identical way.”
“This isn’t your average DoS attack because it doesn’t take a botnet or a lot of coordination to take a web server down. Most DoS attacks rely on a huge number of small requests targeted at a specific web server to overwhelm it,” added Andrew Storms, director of security operations for nCircle. “In this case, a single request can consume a single core for 90 seconds. Queue up a few of these requests every few minutes and the site will be essentially knocked offline.”
“Every year around the holidays we get a security fire drill and this year is no exception. I’d expect Microsoft to deliver a patch out of band for this zero-day bug pretty quickly,” Storms added. “The good news is the shopping season is over, the bad news is most enterprise IT teams are now running skeleton crews. Everyone will be hard pressed to find the resources required to test and deploy the emergency patch we’ll probably see this week.”
Administrators and developers are advised to contact their respective vendors for additional guidance, and to update where possible. In addition, CERT has taken n.run AG’s advice and offered the following mitigations:
Limit CPU time: Limiting the processing time for a single request can help minimize the impact of malicious requests.
Limit maximum POST size: Limiting the maximum POST request size can reduce the number of possible predictable collisions, thus reducing the impact of an attack.
Limit maximum request parameters: Some servers offer the option to limit the number of parameters per request, which can also minimize impact.
The research from n.runs AG is available here. Information on mitigation and patches are available for the following: PHP | Ruby | Microsoft | Tomcat
Steven Ragan contributed to this report.