Hash Flooding and the Case for Keyed Hash Functions

Every cost analysis of a hash table rests on one assumption: the hash function distributes the actual keys in the table. The analyses bound the expected probe count over a random choice of hash, and then implementations fix one hash and apply it to keys chosen by someone else. When that someone is an attacker who knows the hash, the assumption is not merely violated; it is inverted. The attacker can choose exactly the keys that collide.

The attack reduces to filling one bucket

Consider a chained table with a fixed hash and m buckets. An attacker who can predict the hash computes m distinct keys that share the same bucket, then submits them. Each insertion walks the chain at that bucket, so the i-th insertion costs i comparisons, and filling the bucket with k keys costs k(k+1)/2. With k in the tens of thousands, the quadratic factor turns a routine operation into unbounded work per request.

The same applies to open addressing with a more elaborate construction. For linear probing, keys whose home slots are consecutive produce a single long run, and every lookup through that run pays for the whole cluster. For double hashing, keys with the same h₁ and the same h₂ collide at every probe. The attacker does not need to know the implementation’s internal details precisely; knowing the hash function and the table size is sufficient to construct a large colliding set, and the table size is often inferable or irrelevant because the collision holds for every modulus.

The distinguishing feature of the attack is that it is cheap for the attacker and expensive for the defender. Generating k colliding keys costs k hash evaluations, while processing them costs O(k²) comparisons. The asymmetry is what makes it a denial-of-service vector rather than a curiosity: a small request stream can consume all available CPU.

Crosby and Wallach named and demonstrated this class of attack against hash tables and other data structures with predictable worst cases. Their analysis makes the general point that any structure with an average-case guarantee and a deterministic tie-breaking rule has an adversarial worst case, and that the defender’s job is to make the worst case depend on a secret.

Making the collision set unguessable

The defence is to key the hash function with a secret chosen at runtime. If the hash is h_s(k) for a secret s drawn when the table or the process is created, the attacker cannot compute colliding keys without knowing s, and the collision set they construct for one instance is useless against another.

Two properties are needed. First, the function must be a pseudorandom function family: for a random secret, its outputs must be indistinguishable from random to anyone without the secret. Second, the secret must be long enough that it cannot be guessed, and it must actually be random rather than derived from a fixed value. A keyed hash with a hard-coded key provides no defence, because the key is public.

The practical construction is SipHash, designed by Aumasson and Bernstein for exactly this purpose. It is a keyed pseudorandom function over short inputs, with a 128-bit key and a 64-bit output, built from a small number of add-rotate-xor rounds over a four-word state. Its design goal was to be fast enough for hash table use, which rules out SHA-2 and other cryptographic hashes whose per-byte cost is far higher, while still resisting the differential attacks that break simpler keyed constructions.

The round count is the tunable. SipHash-2-4 performs two compression rounds per message word and four finalization rounds; variants with more rounds exist for higher assurance. The two-round variant is the one commonly deployed in language runtimes and network-facing software because it is fast and its security margin is adequate for the collision-resistance requirement, which is weaker than full cryptographic security.

M = (1 << 64) - 1

def rotl(x, b):
    return ((x << b) | (x >> (64 - b))) & M

def sipround(v0, v1, v2, v3):
    v0 = (v0 + v1) & M; v1 = rotl(v1, 13); v1 ^= v0; v0 = rotl(v0, 32)
    v2 = (v2 + v3) & M; v3 = rotl(v3, 16); v3 ^= v2
    v0 = (v0 + v3) & M; v3 = rotl(v3, 21); v3 ^= v0
    v2 = (v2 + v1) & M; v1 = rotl(v1, 17); v1 ^= v2; v2 = rotl(v2, 32)
    return v0, v1, v2, v3

def siphash24(key, msg):
    k0 = int.from_bytes(key[:8], "little")
    k1 = int.from_bytes(key[8:16], "little")
    v0 = k0 ^ 0x736f6d6570736575
    v1 = k1 ^ 0x646f72616e646f6d
    v2 = k0 ^ 0x6c7967656e657261
    v3 = k1 ^ 0x7465646279746573

    n = len(msg) & ~7
    for i in range(0, n, 8):                       # two rounds per full word
        m = int.from_bytes(msg[i:i + 8], "little")
        v3 ^= m
        v0, v1, v2, v3 = sipround(*sipround(v0, v1, v2, v3))
        v0 ^= m

    # tail: the remaining 0-7 bytes, little-endian, with the length in the top byte
    tail = int.from_bytes(msg[n:], "little") | ((len(msg) & 0xFF) << 56)
    v3 ^= tail
    v0, v1, v2, v3 = sipround(*sipround(v0, v1, v2, v3))
    v0 ^= tail

    v2 ^= 0xFF
    for _ in range(4):                              # four finalization rounds
        v0, v1, v2, v3 = sipround(v0, v1, v2, v3)
    return v0 ^ v1 ^ v2 ^ v3

The key enters the initial state before any message byte is absorbed, so two different keys produce unrelated permutations of the same input. The length is folded into the final word rather than padded, which is why the function is defined for short inputs without the Merkle–Damgård padding of a general-purpose hash.

Seeding, stability, and the cost of randomization

A keyed hash forces a decision about the lifetime of the secret. Reseeding per process is the common choice: the secret is drawn once at startup and shared by every table in the process. Reseeding per table is stronger, because a collision set built against one table does not transfer to another, but it costs a fresh secret for every table and makes iteration order differ between tables in ways that complicate reproducibility.

Per-process seeding has a residual weakness. An attacker who can observe enough of the hash’s output, such as the order in which a service returns items from a set, may learn enough about the outputs to find collisions that hold for this instance, though not for another. That is a side channel, and defending against it requires either a per-table secret or a hash strong enough that partial leakage is not exploitable.

The cost of keyed hashing is measurable but small relative to the alternatives. A keyed hash with a few rounds costs a handful of operations per short key, comparable to a multiply-based finalizer, and it dominates the cost only for very short keys where the hash is a large fraction of the total operation. For string keys the per-byte cost dominates and the keying overhead is amortized.

The other cost is reproducibility. A hash whose output depends on a per-process secret produces different iteration orders in different runs, which breaks any test or tool that depends on a stable order. Languages that adopt keyed hashing either document that iteration order is unspecified, or provide an ordered variant for the cases that need it. Go’s map iteration order is deliberately randomized, which serves the same purpose of preventing code from depending on an order that was never guaranteed.

What keying does not fix

A keyed hash restores the expected bound against an attacker who does not know the secret. It does not restore it against an attacker who can choose keys that collide for every hash in the family. If the family is universal, no such set exists beyond a small size, which is why the universality property from hash function construction is the right abstraction: the analysis holds for a random member of the family, and keying is how a random member is selected at runtime.

The defence also does not address a different class of worst case. A table can be driven to quadratic behaviour by an attacker who cannot collide keys but can force repeated resizing, by inserting and deleting at a rate that oscillates the load factor across a threshold. Hysteresis in the resize policy, discussed in incremental rehashing, is the mitigation, and it is independent of the hash function.

Finally, keying does nothing for a table whose keys are supplied by the same party that controls the hash. Internal tables indexed by integers, or tables whose keys come from a trusted source, gain nothing from a keyed hash and pay its cost. The decision is about the trust boundary, not about the table: an untrusted key source needs a keyed hash, a trusted one needs only a well-mixing function.

Designing the boundary rather than the function

The deeper lesson from hash flooding is that a hash table’s cost model has an implicit precondition, and the precondition is a statement about who chooses the keys. Implementations that expose a hash table to network input have to either satisfy that precondition with a secret or accept an unbounded worst case. Implementations that cannot afford a keyed hash because of the per-key cost can still bound the damage by capping the chain length and switching to a fallback structure when a chain exceeds it, which trades a small amount of complexity for a hard bound on the per-operation cost.

The pattern generalizes past hash tables. Any structure whose performance depends on input distribution, including balanced trees with adversarial key orders, sorting algorithms with adversarial comparators, and compression with adversarial dictionaries, has a version of the same problem. The response is always one of three: randomize the structure’s decisions so the adversary cannot predict them, bound the worst case explicitly so the damage is capped, or restrict the input so the adversary cannot choose it. Hash flooding is the clearest case because the attack is so cheap and the defence so well defined, and SipHash exists because the defence needed to be fast enough to be adopted everywhere.