Hash Functions and Their Attacks
A hash table is only as good as its hash function. One that spreads keys evenly makes every operation O(1) on average. One that sends many keys to the same slot turns every operation into a scan. When the keys come from strangers, as form fields, JSON object keys or HTTP headers do, an attacker who can predict the hash can send thousands of keys that all collide, and make one request occupy a processor core for minutes.
That attack is why Python salts its string hashes with a random secret every time it starts. It is also why the hash inside a hash table is a different tool from the one inside a checksum or a password store, even though all three are called hash functions.
What Makes a Good Hash
A hash function for a table needs three properties. It must be deterministic within a run: the same key gives the same hash every time the process asks. It must be fast on short keys, because most keys are short. And it must be uniform: every output bit should flip about half the time when any input bit changes, so that similar keys, such as user1 and user2, land far apart.
A hash that ignores part of the key, or maps many common keys to the same low bits, fills a few slots and leaves the rest empty. The table still gives correct answers. It gives them slowly, because every lookup that lands on a crowded slot compares against everything piled there.
Hash Flooding
If every key collides, inserting n keys costs about n squared over 2 comparisons, because each new key is compared against every key already in the pile. A 2-megabyte form post can carry about 200,000 short field names. If they all collide, building the table of parameters costs about 20 billion comparisons: tens of seconds to minutes of processor time on one core, from one request.
The attack was described in 2003 by Scott Crosby and Dan Wallach. In December 2011, Alexander Klink and Julian Wälde demonstrated it against the web stacks of PHP, Java application servers, Ruby, Python and Microsoft's ASP.NET at once. The first fix most platforms shipped was a cap on the number of parameters in one request: PHP 5.3.9 added a setting that limits a request to 1,000 input variables by default.
The Fix: A Secret Key
To flood a table, the attacker has to predict which slot each key lands in. A keyed hash mixes a random secret, chosen when the process starts, into every hash it computes. Collisions worked out offline, against a different secret, are useless against the running server, and the secret never leaves the process.
CPython has randomized the hashes of strings and bytes by default since version 3.3; it was available as an option in several older releases before that. Since 3.4 the function is SipHash, a keyed function designed in 2012 by Jean-Philippe Aumasson and Daniel Bernstein for this job. Python 3.11 switched to its faster variant, SipHash-1-3, which is what CPython 3.15 reports using. An environment variable, PYTHONHASHSEED, can fix the seed; it exists to reproduce a run, not for production.
print(hash("lantern"), hash(1048576)) # run 1: 2917537548867105371 1048576 # run 2: 4137227930696443322 1048576
The listing prints the hash of the string lantern and of the integer 1048576, Lantern's record for The Dispossessed. Run twice in two separate processes, the string's hash came out completely different each time, because each process drew its own secret. The integer's hash was 1048576 both times: the number itself.
What Randomization Does Not Cover
Integers hash to themselves, reduced modulo a large prime, 2 to the power 61 minus 1 on 64-bit builds. Keys that an attacker supplies as numbers are therefore predictable, and so is anything built from them. A class with a hand-written hash method has whatever weakness its author wrote into it, and randomization of strings does nothing for it.
Java took another route. Since Java 8, a HashMap bucket that grows past eight entries turns into a balanced tree (Chapter 6). That does not prevent the collisions; it caps the damage at O(log n) per operation instead of O(n), so a flood costs n log n instead of n squared.
Why a Cryptographic Hash Is the Wrong Fix
A cryptographic hash such as SHA-256 or BLAKE2 makes it infeasible to find two inputs with the same full output. But a chained table with a million slots uses only the low 20 bits of the hash, and finding keys that agree on 20 bits takes about a million attempts per key, cheap enough to compute once, offline. So an unkeyed cryptographic hash is slower on short keys and still floods. What a table needs is not strength against collisions in the full output, but an attacker who does not know the function, and only a secret key provides that.
Fast unkeyed hashes such as FNV, MurmurHash and xxHash are fine for data nobody hostile chooses. Several popular ones turned out, in a talk by Aumasson, Bernstein and Martin Boßlet in December 2012, to have collisions that work for every seed, which is why SipHash exists. Detecting accidental corruption is a third job, with no adversary at all, and it belongs to checksums (Chapter 12).
Randomized Hashes in Production
Randomization changes behaviour in visible ways. A set of strings iterates in a different order on every run, so a test that prints a set is flaky. Code that stores Python's built-in hash, or uses it to pick a shard, sends the same key to different places from different worker processes, because each worker has its own secret.
The defence against flooding is layered: a keyed hash in the runtime, a cap on the number of keys per request at the edge, and a bound on the size of any body the service parses. Each layer costs almost nothing, next to one request pinning a core for minutes.
- "Python's hash is stable, so I can store it or shard on it." For strings and bytes it changes with every process start, and has since Python 3.3. Two workers disagree about the same key.
- "Hashing with SHA-256 would make my hash table safe." The table uses a few low bits, and collisions in a few bits of a public function are cheap to find offline. Safety comes from a secret key, not from cryptographic strength.
- "Hash tables are O(1), so an attacker cannot make one slow." O(1) is the average for evenly spread keys. With colliding keys, building the table is O(n²).
- "A hash method that returns a constant, or hashes one coarse field, is fine because the dictionary still works." The results stay correct, and every lookup degrades to a comparison against every key in the pile.
- "Seeding MurmurHash with a random number is as good as SipHash." Seed-independent collisions were published for MurmurHash2, MurmurHash3 and CityHash in 2012. A seed is not a key unless the function is designed to use it as one.
- Never persist or share Python's built-in hash across processes; use a stable, named hash function when a value must mean the same thing tomorrow. The built-in is salted per process on purpose.
- Cap the number of keys and the size of any body you parse from a stranger. Bound n and the n² cannot hurt.
- Hash exactly the immutable fields that decide equality. Equal objects must hash equal, and every field left out piles more keys into the same slots.
- Keep hash randomization on in production, and fix the seed only to reproduce a failure. A fixed seed is a published seed.
Knowledge Check
Why does a keyed hash such as SipHash stop hash flooding when an unkeyed SHA-256 does not?
- SipHash has more output bits, so the table's slots never collide
- The attacker cannot predict slots without the process's secret key
- SHA-256 is too slow, so the server times out before the table fills
- SipHash stores every key twice, so collisions are resolved faster
An attacker sends n keys that all land in the same slot of a chained hash table. About how many comparisons does building the table take?
- About n, one per key, because each insert still finds its slot at once
- About n log n, because the pile is searched by halving
- About n²/2, because each key is compared with every key before it
- About n³, because every insert also rehashes all the existing keys
A service stores hash(user_id) in its database to route requests to shards. user_id is a string. What goes wrong?
- Nothing, because the language fixes a string's hash for every Python process
- Only lookups slow down, because the stored hash values are too large to index
- The database rejects the values, because hash values can come out negative
- Each process salts differently, so the same id routes to different shards
Which Python key types does hash randomization protect against flooding?
- Strings and bytes, but not integers or classes with their own hash
- Every hashable type, because the secret key is mixed into all hashes
- Integers only, because strings are hashed with a fixed function
- None of them, because randomization only changes iteration order
Java's HashMap and Python's dict defend against flooding in different ways. How do the two strategies differ?
- Java blocks requests with many keys, while Python sorts every key
- Java encrypts its keys, while Python stores keys in a balanced tree
- Java caps the damage with tree bins; Python prevents the collisions
- Both do the same thing, a random seed chosen when the program starts
You got correct