This attack is known as Hash DoS, or more generally as Algorithmic Complexity Attack.
There are several ways to implement lookup tables:
- Balanced trees
The relevant operations have logarithmic performance, regardless of the data. These are naturally immune to this attack, but they're slower.
If the hashes are well distributed, the relevant operations are O(1) and really fast, but if they're badly distributed they become O(n).
There are two common strategies to avoid Hash DoS: You can switch to trees, or you can use keyed hashes.
For keyed hashes the server chooses a random secret key. Depending on the situation this key can be per-process, per-table, per-request,... Longer lifetimes can allow adaptive attacks over multiple requests, but I'm not sure how big a problem that is in practice.
Then it uses a keyed hash to determine the bucket, instead of an unkeyed hashfunction. If the keyed hash is good, this prevents the attacker from producing collisions quickly. Earlier keyed hashes often suffered from key independent collisions, and thus didn't prevent the attack once these were found. Currently SipHash is gaining popularity, since it's fast, but still cryptographically secure.
My recommendation is using SipHash and to avoid key reuse across requests where possible.
Breaking Murmur: Hash-flooding DoS Reloaded (On Martin Boßlet's blog)
Jointly with Martin Boßlet, we demonstrated weaknesses in MurmurHash (used in Ruby, Java, etc.), CityHash (used in Google), and in Python's hash. Some of the technologies affected have switched to SipHash. See this oCERT advisory, and the following resources:
- Slides of the presentation "Hash-flooding DoS reloaded: attacks and defenses" at Application Security Forum Western Switzerland 2012 (Aumasson, Boßlet)
Hash DoS against BTRFS
Many programming languages are currently upgrading their standard libraries to avoid Hash DoS. These attacks hit dynamically typed languages very hard, since they typically use hashtables almost everywhere (member names to values etc.)
Some big projects upgrading their hashtables: