Vulnerability of the day: Hash Collision TarPit
When designing an endpoint application that’s exposed to the internet, extra care must be taken when using “dicts” or “unordered maps” implemented as hash tables with trivially attackable hash functioons.
If you’re not sure how your dict is implemented, or don’t want to read too much, just don’t use them… and use a tree structures (ordered map/dict) instead.
Why?
When an unordered map is used, the performance typically averages O(1). However many implementations of unordered maps degrade to O(n) on collisions.
Imagine an api endpoint that currently performs an O(n) function on the input, say adding the words the user provides to a dictionary and then intersecting that with a set of banned words.
This endpoint should scale well, many web apis do set-intersection like things: finding friends in common, searching blacklists for ip’s, etc.
However, if the api uses an unordered map, and this map does not use a hash with some sort of random seed, an attacker can quickly determine a set of words that collide in the map. The result of this is your nice O(n) endpoint becomes O(n²).
Any exposed O(n²) public services can be trivially DOS’ed. An attacker with a single machine can attack using O(n) data, and trivially bring down all of an enterprise-scale company’s public facing systems that depend on that endpoint.
For more information see the CERT advisory:
Or, the original paper published to on this vulnerability:
Crosby, Scott A. and Dan S. Wallach. “Denial of Service via Algorithmic Complexity Attacks.” USENIX Security Symposium (2003).
