Hash Tables and Hash Flooding

Hash tables (dictionaries, maps, hashes, or objects depending on the language) are the most used data structure in web applications. Request parameters, headers, JSON objects, routing tables, and session data all land in one, usually before your application code runs at all. That ubiquity is why a flaw in how they handle worst-case input became a cross-language denial-of-service class.

How they work

A hash table stores entries in an array of buckets. To insert a key, it computes a hash of the key, reduces that hash to a bucket index (typically hash mod number_of_buckets), and stores the entry there. Lookups repeat the same calculation and jump straight to the bucket. With a hash function that spreads keys evenly, entries scatter across buckets and both operations are constant time on average.

When two keys reduce to the same bucket, that is a collision. The bucket holds a short list (or, in some implementations, a tree) of entries, and the table searches within it.

Load factor and resizing

The load factor is entries divided by buckets. As it rises, buckets hold more entries and operations slow, so tables resize (often doubling the bucket array and rehashing everything) when the load factor crosses a threshold like 0.75. Resizing is an O(n) operation amortized across many O(1) inserts, which is why “amortized constant time” is the honest description. An attacker who can force frequent worst-case behavior defeats the amortization, which is the door hash flooding walks through.

The worst case

If every key lands in the same bucket, the table degrades to a single linear list. Each insert must scan everything already in that bucket to check for duplicates, so inserting n colliding keys costs O(n²) overall. For n = 100,000 that is billions of comparisons instead of a hundred thousand, which is seconds-to-minutes of pure CPU for a single request.

Hash flooding

In 2011, researchers (and later the MurmurHash collision work in 2012) showed the hash functions in PHP, Java, Python, Ruby, ASP.NET, V8, and others were deterministic and simple enough to let an attacker precompute large sets of keys that all collide. One POST body of a few megabytes of carefully chosen parameter names kept a server pinned at full CPU for minutes, because the framework parsed every parameter into a hash table before the application ever saw the request. It needed no authentication and no vulnerability in the app itself, only the framework’s trust that input keys would be ordinary.

The fix: keyed hashing

• Randomized, keyed hash functions. Languages adopted hash functions seeded with a secret per-process key, chiefly SipHash. SipHash mixes the key into the computation so that, without knowing the key, an attacker cannot predict which inputs collide; every process effectively has a different, unpredictable bucket assignment. Python, Ruby, Rust, and others now hash strings this way. This is the same principle as a MAC: when predictability would be abused, mix in a secret.
• Tree buckets. Java’s HashMap converts a long collision chain into a balanced tree, bounding a flooded bucket at O(log n) per operation instead of O(n).
• Input limits. Frameworks began capping the number of parameters, headers, and JSON keys per request. PHP’s max_input_vars came directly from this incident.

Field notes: triggering hash flooding

The attack is cheap when the hash is unkeyed and known. You generate a set of keys that all land in the same bucket, then send them where the framework builds a hash table before your code runs: POST body parameters, JSON object keys, query-string parameters, and HTTP headers.

• Where to send them. A few thousand colliding parameter names in one application/x-www-form-urlencoded body forces O(n squared) insertion as the framework parses the request, pinning a CPU core for seconds to minutes per request. No auth and no app bug required, because the parser runs first.
• Generating collisions. For a known unkeyed function (old PHP DJBX33A, pre-fix Java String.hashCode) collisions are constructed directly with published generators; for MurmurHash a seed-recovery step preceded collision generation in the 2012 work. The key property you are exploiting is that the function is deterministic and public.
• Confirming the fix. Modern runtimes seed the hash with a per-process secret (SipHash), so externally generated collisions no longer work. You can still DoS via sheer count where no limit exists, which is why max_input_vars, header-count caps, and JSON key limits matter independently.

Demonstrate this only against your own service or an authorized target, and in a controlled way, because it is a genuine denial of service.

Lessons that generalize

• Any data structure an attacker can fill deserves an explicit worst-case analysis, not just an average-case benchmark.
• An unkeyed hash of attacker input is predictable, and predictability is exploitable. When it matters, use a keyed function.
• Limits on input size and count are cheap and shut down whole families of resource exhaustion at the edge, before expensive code runs.