Web Server DoS by Hash Collision

For efficiency reasons, most web servers store the request parameters in a hash table. However, when a request contains many parameters, say 10000 parameters, and the hash values for the parameter names are all the same, then the web server will spend a lot of time parsing the request. In such scenario, the hash insertion is very slow because of hash collisions. Some people wrote about this before, but nobody really knew how to generate a large amount of multi-collision strings, until Dec 28th...

“alech” and “zeri” pointed out that most String hashing functions are either based on DJBX33A or DJBX33X algorithms which are vulnerable to “Equivalent substrings” and “Meet-in-the-middle” attacks respectively. DJBX33A has the property that if two strings collide, e.g. hash('ABC') = hash('XYZ'), then hashes having this substring at the same position collide as well, e.g. hash('prefixABCpostfix') = hash('prefixXYZpostfix'). Therefore, you can easily generate infinite number of collided strings by something like “ABCABC”, “ABCXYZ”, “XYZABC”, etc. DJBX33X is not vulnerable to “Equivalent substrings” attack but is vulnerable to “Meet-in-the-middle”. By using “Meet-in-the-middle”, an attacker can get collided strings with probability of around 1/2^16, which can easily be searched. By using these techniques, “alech” and “zeri” are able to DoS the following servers:

Status:

• Microsoft released a patch (MS11-100) on Dec 29th. The patch adds a new ASPX config parameter “aspnet:MaxHttpCollectionKeys”, default value is 1,000.
• Tomcat released 7.0.23 and 6.0.35: new configuration parameter “maxParameterCount”, default value is 10,000.
• PHP released 5.4.0 RC4: new “max_input_vars” directive to prevent attacks based on hash collisions.

References:

• Original Paper http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf
• n.runs-SA-2011.004 Advisory http://www.nruns.com/_downloads/advisory28122011.pdf