Tuesday, March 13, 2012

HashDoS: DoS using Hash Collision


HashDoS is a term coined for Denial of Service (DoS) attack using Hash Collision. Last year, many of the programming languages and application servers were proved to be vulnerable to this attack. It can be exploited by leveraging collisions in hashing algorithm of the storage data structures used for request parameters.  Most servers store request parameters in hash table.

In case when hashing algorithm is not sufficiently randomized, the colliding keys increases complexity of inserting n elements into the table to O(n**2).

If someone creates a HTTP request which has request parameters with colliding keys, this can cause a single request to exhaust hours of CPU time. The required bandwidth, time and size of data is very less in this condition.

Hashing for HashMap/Table:

We know that in hashing data is put into buckets accroding to the keys. If two items have same key, then they are added in same bucket. Now if we have a lot of keys eligible to be put in same bucket, then inserting a new entry means iterating over all the elements sequentially just to find out if it already exists.

Java HashMap and Hashtable classes use the String.hashCode() hash function. It uses the multiplication constant 31 and instead of the start value 0 to compute a hash code. Also When hashing a string, Java caches the hash value in the hash attribute, but only if the result is different from zero. So target value 0 prevents caching and forces rehashing.

Attack Vector:


In Php "Ez" and "FY" have same hash code. Similarly in Java, "Aa" and "BB" have the same hash code. Now we can make use of vulnerability of hashing algorithm known as "Equivalent Substrings" (read below for detail of this vulnerability), and generate several other strings with the same hashcode, which start with these 2 strings.

In First Iteration we will get: "AAAA", "AABb", "BbAA", "BbBb" having the same hash code. By permuting them further we can generate 16 Strings having same hash code and so on.

Example:

"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",
"AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",
"BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa", all have the same hash code.

In summary: It is very easy to generate a large set of strings that will have the exact hash code.

Recommendation: Upgrade your servers with latest security Hot-fix and protect against this attack. For ColdFusion here is the link for Security bulletin for the hot-fix.

Equivalent Substrings:

No programming language has a perfectly randomized hashing algorithm being used. Most String hashing functions are either based on algorithms which are vulnerable to “Equivalent substrings” and “Meet-in-the-middle” attacks.

If two strings ABC and XYZ have same hash value hash('ABC') = hash('XYZ'), then hashes having this substring at the same position collide as well, hash('ColdABCFusion') = hash('ColdXYZFusion'). This is defined as "Equivalent substrings".


3 comments:

  1. I would also check you app server for any security updates around hashdos as well. I know Tomcat came out with some changes.

    ReplyDelete
  2. hey that was nice work. I am a CEH.
    Can you explain me more about php hash DOS attack?

    ReplyDelete

You can subscribe to the comments by licking on "Subscribe by email".