THE FOLD / CHEAT / THE EXPLOIT / THE HASH FLOODING
THE HASH FLOODING
they declined to be the average case
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A hash table is O(1) on average. Average over what? Over inputs an adversary did not choose. If the hash function is fixed and public, keys that collide can be computed in advance, and the table degenerates into one long list.
LIT verified live. 2,000 keys crafted to collide under a fixed
LIT verified live. 2,000 keys crafted to collide under a fixed
x*31+c hash, inserted into a 1,024-bucket table. They land in 1 bucket, forming a chain of 2,000, and cost 1,999,000 comparisons — exactly n(n−1)/2, the quadratic. The identical keys under a seeded hash spread over 503 buckets, longest chain 12, and cost 3,975 — 502.9× less work for the same input.2 HOW IT WAS WEAVED · AI + HUMAN
Crosby and Wallach published algorithmic complexity attacks in 2003; the fix is a per-process random seed, which is why SipHash now sits under Python, Ruby and Rust dictionaries.
AVAN (AI) checked that the degenerate case is exactly quadratic rather than merely bad, because
AVAN (AI) checked that the degenerate case is exactly quadratic rather than merely bad, because
n(n−1)/2 is falsifiable and “slow” is not. The attack needs no privileged access and no clever timing — only the hash function, which was published. The seed does not make the hash stronger in any cryptographic sense; it makes it unknown, and that alone is the entire defence.3 ONE DIMENSION
Same 2,000 keys. Two hash functions.
4 TWO DIMENSIONS · INTERACTIVE
Feed the table more crafted keys and watch the work square.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a table with one very long row.
AVAN’s addition (the inverse-companion): the forward reading is that a fixed hash is a security hole. The inverse is that the hole was in the phrase “on average”. O(1) was always a statement about a distribution of inputs, and every complexity bound quietly names an adversary it assumes does not exist. The keys here are not malformed — they are ordinary strings that happen to be inconvenient. Read backwards, an attacker did not break the data structure; they simply declined to be the average case it was analysed against.
LIT 2,000 keys crafted to collide under a fixed x*31+c hash land in 1 bucket of 1,024, forming a chain of 2,000 and costing 1,999,000 comparisons - exactly n(n-1)/2 - while the identical keys under a seeded hash spread over 503 buckets with a longest chain of 12 and cost 3,975, which is 502.9 times less work for the same input
FIG Crosby and Wallach published algorithmic complexity attacks in 2003; the fix is a per-process random seed, which is why SipHash now sits under Python, Ruby and Rust dictionaries. AVAN checked that the degenerate case is exactly quadratic rather than merely bad, because n(n-1)/2 is falsifiable and slow is not. The attack needs no privileged access and no clever timing, only the hash function, which was published. The seed does not make the hash stronger in any cryptographic sense - it makes it unknown, and that alone is the defence.
FIG Crosby and Wallach published algorithmic complexity attacks in 2003; the fix is a per-process random seed, which is why SipHash now sits under Python, Ruby and Rust dictionaries. AVAN checked that the degenerate case is exactly quadratic rather than merely bad, because n(n-1)/2 is falsifiable and slow is not. The attack needs no privileged access and no clever timing, only the hash function, which was published. The seed does not make the hash stronger in any cryptographic sense - it makes it unknown, and that alone is the defence.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EXPLOIT · David Lee Wise (ROOT0), with AVAN