Archivehashing
Hash Flooding and Why SipHash Exists
If an attacker can choose your map keys, a deterministic hash function is a denial-of-service primitive.
- Published
- Reading time
- 1 min read
Most hash tables handle collisions with chaining or open addressing. Both degrade to O(n) when many keys land in one bucket. If the hash function is public and deterministic, an attacker can compute collisions offline and send a request with thousands of them.
The 2011 wake-up call
Several language runtimes and web frameworks were taken down by a few hundred kilobytes of colliding POST parameter names. The fix was not a better table — it was a keyed hash with a per-process random seed, so collisions cannot be precomputed.
SipHash is the canonical answer: fast (a few cycles per byte), keyed, and designed for short inputs. Rust's default hasher, Python's hash randomization, and many others descend from this idea.
When it is not enough
- Keys from an untrusted source with a fixed seed — an attacker who learns the seed can still grind.
- Very large keys, where hashing cost itself dominates.
- Timing side channels from hash-dependent branches.
Takeaway: any map keyed by user input needs a keyed hash with a secret seed. A deterministic hash is a public collision generator.