For a hash table fed attacker-chosen keys, which defenses stop hash flooding and which only bound the damage?

## Sort the defenses by their promise The useful discipline here is refusing to put every mitigation in one bucket labelled "fixes it". Three distinct promises are on offer. ### 1. Remove predictability: keyed, per-process randomized hashing Instead of `hash(key)`, compute `hash(secret_key, key)` with a keyed function, where `secret_key` is random and generated fresh in each process. SipHash is the function that became the standard answer: a keyed pseudorandom function designed specifically for short inputs, fast enough to sit on the hot path of a hash table. What this buys: the attacker cannot compute a colliding set offline, because they do not know which function you are effectively using. Each process is, in effect, using a different member of a large function family. That is exactly the **universal hashing** frame. A family H of hash functions is universal if, for any two distinct keys x and y, the probability that a randomly drawn h in H maps them to the same bucket is at most 1/m. The crucial reading: the probability is over your random *choice of function*, not over the input distribution. So the expected bucket length stays O(1 + n/m) **for any key set**, including one an adversary picked — as long as it was picked without knowing which function you drew. And that last clause is the limit of the promise: - It is expected-case, not worst-case. An unlucky draw can still produce a long bucket; the guarantee is that the attacker cannot *aim* for it. - It collapses if the key leaks. Reusing one key fleet-wide, deriving it from something predictable such as a timestamp or process id, or logging it, all restore the offline attack. - Adaptive attackers can, against weak or truncated keyed functions, learn something from timing differences across many probes. This is a real research direction, not merely theoretical, so "keyed" is not permission to stop thinking. It also has one operational side effect worth naming: because the key differs per process, hash values and therefore iteration order differ between runs, and any hash value you persist or shard on is no longer stable across processes. ### 2. Bound n: caps at the parse layer Cost is quadratic in the number of keys, so a limit on how many keys a single request may create is a direct, cheap, and very effective control — an upper bound of a few hundred fields turns a potential 50-million-comparison request into a trivial one. It is unglamorous and it works. The catch is coverage. The cap must hold at every place that builds a map from untrusted input: query parameters, form bodies, headers, nested documents, batch endpoints, and any cache keyed off that data. One uncapped path restores the whole exposure, which is why caps are an excellent second layer and a weak sole layer. ### 3. Bound the per-bucket cost: an ordered fallback When a bucket exceeds some length, replace its linked chain with a balanced search structure — a red-black tree is the usual choice. Operations in that bucket become O(log n) instead of O(n), so an n-key flooding attack costs O(n log n) rather than O(n^2). At n = 10,000 that is the difference between roughly 50 million comparisons and roughly 130 thousand. This stops nothing. The collisions still happen; they just cost far less. Two properties are worth stating precisely: - **It needs a total order on keys.** Comparable keys can be ordered directly; otherwise the structure must synthesize a tie-break (typically the hash value plus some stable identity) and, where it cannot, must keep the linear chain — so the fallback is not guaranteed to engage for every key type. - **It costs complexity and memory** in the container itself, paid by every user of the container forever. ## The wrong answer this question aims at "Collisions are a statistical accident, so seeding is paranoia." This confuses two different regimes. Under natural input, collisions really are accidents and the average is a fair description. Under chosen input, the adversary *is* the distribution, and no averaging argument applies to them. The defense-in-depth argument follows: the layers protect against different failures — the keyed hash against precomputation, the cap against unbounded n, the ordered fallback against a hash key that leaked or a map nobody remembered to audit. Any single one of them can fail silently, which is precisely why mature runtimes shipped different combinations: some (Python, Ruby, Perl) went to per-process seeded hashing, PHP added a hard limit on accepted parameter count, and the JVM's mainstream map added the ordered-bucket fallback. ## What does *not* belong on the list Swapping in a stronger unkeyed hash function. Bucket index is a value modulo a small bucket count, so an attacker can collect same-bucket keys by brute-force enumeration no matter how strong the digest is. Unpredictability, not strength, is the property you need.