Hash Collision Attacks in ASP.NET Web Applications

Overview:
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.
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.
Most hash functions used in hash table implementations can be broken faster than by using brute-force techniques (which is feasible for hash functions with 32 bit output, but very expensive for 64 bit functions) by using one of two “tricks”: equivalent substrings or a meet-in-the-middle attack.

1. Equivalent substrings
Some hash functions have the property that if two strings collide, e.g. hash(‘string1’) = hash(‘string2’), then hashes having this substring at the same position collide as well, e.g. hash(‘prefixstring1postfix’) = hash(‘prefixstring2postfix’). If for example ‘Ez’ and ‘FY’ collide under a hash function with this property, then ‘EzEz’, ‘EzFY’, ‘FYEz’, ‘FYFY’ collide as well. An observing reader may notice that this is very similar to binary counting from zero to four. Using this knowledge, an attacker can construct arbitrary numbers of collisions (2^n for 2*n-sized strings in this example).

2. Meet-in-the-middle attack
If equivalent substrings are not present in a given hash function, then brute-force seems to be the only solution. The obvious way to best use brute-force would be to choose a target value and hash random (fixed-size) strings and store those which hash to the target value. For a non-biased hash function with 32 bit output length, the probability of hitting a target in this way is 1/(2^32).
A meet-in-the-middle attack now tries to hit more than one target at a time. If the hash function can be inverted and the internal state of the hash function has the same size as the output, one can split the string into two parts, a prefix (of size n) and a postfix (of size m). One can now iterate over all possible m-sized postfix strings and calculate the intermediate value under which the hash function maps to a certain target. If one stores these strings and corresponding intermediate value in a lookup table, one can now generate random n-sized prefix strings and see if they map to one of the intermediate values in the lookup table. If this is the case, the complete string will map to the target value.
Splitting in the middle reduces the complexity of this attack by the square root, which gives us the probability of 1/(2^16) for a collision, thus enabling an attacker to generate multi-collisions much faster.
The hash functions we looked at which were vulnerable to an equivalent substring attack were all vulnerable to a meet-in-the-middle attack as well. In this case, the meet-in-the-middle attack provides more collisions for strings of a fixed size than the equivalent substring attack.

The different language use different hash functions which suffer from different problems. They also differ in how they use hash tables in storing POST form data.

ASP.NET uses the Request.Form object to provide POST data to a web application developer. This object is of class NameValueCollection. This uses a different hash function than the standard .NET one, namely CaseInsensitiveHashProvider.getHashCode(). This is the DJBX33X (Dan Bernstein’s times 33, XOR) hash function on the uppercase version of the key, which is breakable using a meet-in-the-middle attack.
CPU time is limited by the IIS webserver to a value of typically 90 seconds. This allows an attacker with about 30kbit/s to keep one Core2 core constantly busy. An attacker with a Gigabit connection can keep about 30.000 Core2 cores busy.

Java offers the HashMap and Hashtable classes, which use the String.hashCode() hash function. It is very similar to DJBX33A (instead of 33, it uses the multiplication constant 31 and instead of the start value 5381 it uses 0). Thus it is also vulnerable to an equivalent substring attack. When hashing a string, Java also caches the hash value in the hash attribute, but only if the result is different from zero.
Thus, the target value zero is particularly interesting for an attacker as it prevents caching and forces re-hashing.
Different web application parse the POST data differently, but the ones tested (Tomcat, Geronima, Jetty, Glassfish) all put the POST form data into either a Hashtable or HashMap object. The maximal POST sizes also differ from server to server, with 2 MB being the most common.
A Tomcat 6.0.32 server parses a 2 MB string of colliding keys in about 44 minutes of i7 CPU time, so an attacker with about 6 kbit/s can keep one i7 core constantly busy. If the attacker has a Gigabit connection, he can keep about 100.000 i7 cores busy.
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).

Workarounds:

1. Limiting CPU time
The easiest way to reduce the impact of such an attack is to reduce the CPU time that a request is allowed to take. For PHP, this can be configured using the max_input_time parameter. On IIS (for ASP.NET), this can be configured using the “shutdown time limit for processes” parameter.

2. Limiting maximal POST size
If you can live with the fact that users can not put megabytes of data into your forms, limiting the form size to a small value (in the 10s of kilobytes rather than the usual megabytes) can drastically reduce the impact of the attack as well.

3. Limiting maximal number of parameters
The updated Tomcat versions offer an option to reduce the amount of parameters accepted independent from the maximal POST size. Configuring this is also possible using the Suhosin version of PHP using the suhosin.{post|request}.max_vars parameters.