Hashing Denial-Of-Service Attack Leaves More Than Half Of The Internet Vulnerable

A recent research Alexander “alech” Klink and Julian “zeri” Wälde shows that more than half of Internet is vulnerable to Hashing Denial of service vulnerability. The HDOS vulnerability exploits the hash tables consuming more than 99% of the CPU usage hence causing a Denial of service attack.

The security researchers demonstrated the  HDOS vulnerability at 28th Chaos Communication Congress security conference in Berlin, Germany, Earth, Milky Way. The talk was titled as "Efficient Denial of Service Attacks on Web Application Platforms". The reaserch shows that most of the web programming languages including PHP, ASP.NET, Java, Python, Ruby, Apache Tomcat (The list goes on and on) are vulnerable to the HDOS vulnerability

PHP 5, Java, ASP.NET as well as V8 are fully vulnerable to this issue and PHP 4, Python and Ruby are partially vulnerable, depending on version or whether the server running the code is a 32-bit or 64-bit machine. 

 Hash tables are a commonly used data structure in most programming languages," they explained. "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. 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."

Demonstration

The researchers have also posted a video demonstration as a proof of the vulnerability.

Countermeasures


Mircosoft has also provided the workaround for the asp.net vulnerability, You can find it here.

PHP advises to limit the number of different http request parameters. For this purpose PHP has added a max_input_vars function which gives the flexibility to limit the number of paramters.

Furthur Resources:

If you would like to learn more about the vulnerability, here are some useful links:

http://www.ocert.org/advisories/ocert-2011-003.html
http://permalink.gmane.org/gmane.comp.security.full-disclosure/83694