Understanding Attack Vector
How HashMap's work
Say a comment form on a blog accepts the parameters - first_name, last_name, comment as post parameters. Internally, Tomcat stores these parameters as a HashMap.
The logical structure of this HashMap is like this -
"first_name" --> "Sripathi"
"last_name" --> "Krishnan"
"comment" ---> "DoS using poor Hashes"
But the physical structure is different. The keys are first converted into a hashCode, and then the hashCode is converted into an array index.
The ideal physical structure thus becomes -
0 --> "Sripathi"
1 --> "Krishnan"
2 --> "DoS using poor Hashes"
But the possible keys are infinite. So at some point, two keys will have the same hash code. This becomes a hash collision.
With collisions, the physical structure becomes :
0 --> "Sripathi" -> "Krishnan"
1 --> Empty
2 --> "DoS using poor hashes"
Hash Collisions and impact on performance
When you have hash collisions, inserting a new entry means iterating over all the elements sequentially just to find out if it already exists in the map. Inserting one element becomes O(n) complexity. Inserting n elements makes it O(n*n) complexity.
In short : If you insert thousands of keys that have the same hashCode, the server will require a lot of CPU cycles.
How do you generate keys with the same Hash?
In Java, "Aa" and "BB" have the same hash code.
Because of a property called "Equivalent Substrings", we can generate several other strings with the same hashcode, just by starting with these 2 strings.
First Iteration : "AAAA", "AABb", "BbAA", "BbBb" have the same hash code
Now, we have 4 strings with the same hash code. We can permute them to generate 16 strings that will have the same hash code. For example :
"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",
"AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",
"BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",
All these 16 strings have the same hash code.
You can now take these 16 strings, and generate 256 strings that have the same hashcode.
In short : It is very easy to generate a large set of strings that will have the exact hash code.
How do you attack the server?
- Create thousands of string that have the same hash code (see above)
- Construct a POST request like this - AaAa=&AaBB=&BBAa=&BBBB= ....
- Submit the form
- Repeat in a loop, and create several threads so that all server resources are used up
Because this is just a POST request, an attacker can also use innocent browsers to attack a server. Just find a website with a cross site scripting vulnerability, embed code to make a POST request, and then use social engineering to spread the link to as many users as you can.
In general, the underlying platform cannot fix this. This is considered to be a application framework problem. In other words, Tomcat has to fix this, not Oracle/Sun.
Possible fixes include :
Restrict the number of POST parameters - Tomcat 6.035+ has a new parameter maxParameterCount. The default value is 10,000. The lower the better, as long as it does not break your functionality.
Restrict the size of the POST request - For the attack to work, the Payload has to be huge. The default POST allowed by Tomcat is 2MB. Reducing this to say 200KB will reduce the effectiveness of this attack. The parameter in tomcat is maxPostSize
Web Application Firewall - If you have a web application firewall, you can configure it to block requests that look suspicious. This is a reactive measure, but is nice to have in case you cannot use one of the above solutions.
FYI - Tomcat's documentation is here - http://tomcat.apache.org/tomcat-6.0-doc/config/http.html