Introduction to Hash DoS Attacks

Someone asked me about the Hash DoS [2] attack recently disclosed at CCC, so I thought I would give a high level explanation of it here in case it benefits others as well. Hash tables are often used in programming languages to map data keys and values together. A comparable real world example could be a phone book which maps a person's name (the key) to their phone number (the value). Web App languages often parse user-supplied request data into hash tables to allow developers easy access to the request. For example, in PHP you can access the fname parameter submitted in a POST request via the $_POST["fname"] variable.

When hashing strings, it is not uncommon for more than one unique string to end up with the same hashed value. This is known as a Hash Collision [3]. Normally this is not a problem, as languages use various strategies [4] to resolve these collisions. However, an attacker can exploit this behavior to exhaust the CPU by forcing a large number of collisions via a single request with many parameters. Krzysztof Kotowicz created a demo [5] that can be used to test whether your app is vulnerable.

The core issue has been known since 2003 and as a result several languages, such as Perl and CRuby, have added randomization to their hash functions. Other languages have recently limited the number of parameters allowed in a single request, e.g. PHP's max_input_vars directive [6]. By default, the max_input_vars directive limits the number of GET, POST and Cookie input variables to 1000. For those who can not patch their application framework, ModSecurity can be used to virtually patch this flaw. The rule below implements the same default functionality of the max_input_vars directive described above.

SecRule &ARGS|&REQUEST_COOKIES_NAMES|&REQUEST_COOKIES "@gt 1000" "phase:2, \
  t:none,log,block,severity:2,msg:'Hash DoS Detected'"