hash flooding
An attack that sends a server many keys crafted to collide in its hash tables, turning each O(1) operation into O(n) and exhausting its CPU.
A few crafted requests can pin a server's CPU and deny service to everyone else.
In more detail
Inserting n colliding keys costs O(n^2) in total, so a single request of a few hundred kilobytes could keep a web server busy for minutes. In 2011 researchers showed it against Python, Ruby, Java, PHP and others, tracked for Python as CVE-2012-1150. The defence is a secret, per-process random seed mixed into string hashing, so attackers cannot predict which keys collide.
Related terms
- hash randomisation — Mixing a secret random value, chosen when a process starts, into string hashing so that hash values cannot be predicted from outside.
- PYTHONHASHSEED — The environment variable that controls the seed Python uses to randomise str, bytes and datetime hashes.
- denial of service — An attack that makes a service unavailable to its real users by overloading it or making it crash.
- adversarial input — Input chosen deliberately by someone who wants your code to behave badly, often by hitting its worst case.
- SipHash — A fast keyed hash function designed so that, without the secret key, attackers cannot predict or engineer collisions.
Taught in
- What A Hash Function Promises — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers