When 2 MB of Data Can Take Down a Server: The Hidden Mathematics of Hash Collisions

On December 28, 2011, at the 28th Chaos Communication Congress in Berlin, Alexander Klink and Julian Wälde demonstrated something that sent shockwaves through the software industry. With just 2 megabytes of carefully crafted POST data, they kept a single CPU core busy for over 40 minutes. The attack didn’t exploit buffer overflows or SQL injection—it exploited the fundamental mathematics of hash tables.

The technique, dubbed HashDoS, works because hash tables have a worst-case performance that’s dramatically different from their average case. When you understand the mathematics behind this vulnerability, you’ll see why it affected virtually every major programming language and why modern hash table implementations look very different from their predecessors.

The Birthday Paradox: Why Collisions Are Inevitable

The mathematical foundation of hash collisions comes from a problem that seems counterintuitive at first. In a room of 23 people, what’s the probability that at least two share a birthday? Most people guess somewhere around 6% (23/365). The actual answer: approximately 50%.

This counterintuitive result—the birthday paradox—has profound implications for hash tables. The reason is that we’re not asking “what’s the chance someone shares a birthday with a specific date?” We’re asking “what’s the chance that any two people share any birthday?”

For hash tables, the calculation is similar. Given $k$ items hashed into $N$ possible buckets, the probability of at least one collision is:

This can be approximated as:

For a 32-bit hash (like Java’s String.hashCode()), you have $N = 2^{32} \approx 4.3$ billion possible values. The probability of a collision reaches 50% when $k \approx 77,163$. That’s surprisingly small for a space of 4 billion possibilities.

Image source: Preshing on Programming

But here’s the critical insight: this probability assumes a uniform random distribution. Real-world hash functions aren’t perfectly random, and attackers can exploit this.

How Hash Tables Degrade

A hash table promises O(1) average-case performance for insertions, lookups, and deletions. But this promise rests on a crucial assumption: that the hash function distributes keys uniformly across the buckets.

When collisions occur—when two different keys hash to the same bucket—performance begins to degrade. The collision resolution strategy determines how gracefully the system handles this degradation.

Separate Chaining

The simplest approach stores a linked list at each bucket. When a collision occurs, the new element is appended to the list. In the worst case—when all $n$ elements hash to the same bucket—lookup becomes an $O(n)$ operation, as you must traverse the entire linked list.

This is exactly what the HashDoS attack exploited. By finding strings that all hash to the same value, attackers could force the hash table into its worst-case behavior.

Open Addressing

Instead of using linked lists, open addressing stores all elements directly in the array. When a collision occurs, the algorithm “probes” for the next available slot using a predetermined sequence.

Linear probing checks the next slot: $h(k, i) = (h(k) + i) \mod m$. It’s cache-friendly but suffers from primary clustering—long runs of occupied slots tend to grow longer, as any key hashing into the cluster must be placed at its end.

Quadratic probing uses a quadratic function: $h(k, i) = (h(k) + c_1 i + c_2 i^2) \mod m$. This eliminates primary clustering but introduces secondary clustering—keys with the same initial hash follow the same probe sequence.

Double hashing uses a second hash function: $h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m$. This provides the most uniform probe sequences but requires computing two hash values.

Modern Variants: Robin Hood, Cuckoo, and Hopscotch

Recent years have produced sophisticated collision resolution strategies that push performance boundaries.

Robin Hood hashing is a variation of open addressing that minimizes the variance of probe lengths. When inserting an element, if it would have a longer probe length than an element already in the table, they swap positions. This “robs from the rich” (elements with short probe lengths) to “give to the poor” (elements that would have long probe lengths). The result: all lookups complete within a bounded number of probes, typically under 12 even for heavily loaded tables.

Cuckoo hashing uses two (or more) hash functions and maintains the invariant that each element must be in one of its designated positions. On insertion, if both positions are occupied, the existing element is “kicked out” and moved to its alternate position. This can trigger a chain of displacements, but guarantees $O(1)$ worst-case lookup time—either check position 1 or position 2, no probing required.

Hopscotch hashing combines ideas from linear probing and cuckoo hashing. Each bucket maintains a bitmap indicating which nearby slots contain elements that belong to it. This bounds the maximum probe length while maintaining good cache locality.

The HashDoS Attack: Anatomy of a Vulnerability

The 2011 HashDoS presentation revealed that most programming languages used hash functions with predictable behavior. Consider Java’s String.hashCode():

public int hashCode() {
    int h = 0;
    for (int i = 0; i < value.length; i++) {
        h = 31 * h + value[i];
    }
    return h;
}

This function, documented since Java 1.2, computes: $h(s) = \sum_{i=0}^{n-1} 31^{n-1-i} \cdot s[i]$

The key insight: certain string pairs produce identical hashes. For example, "Aa" and "BB" both hash to 2112. This extends: "AaAa", "AaBB", "BBAa", and "BBBB" all hash to the same value. With $n$ such pairs, you can generate $2^n$ colliding strings.

PHP, ASP.NET, Python, Ruby, and JavaScript all used similar functions. The DJBX33A hash (multiply by 33, add character) appeared in PHP and several other languages. The attack found equivalent substrings for these functions, enabling the generation of millions of colliding keys.

The presentation showed that with 200,000 colliding keys—roughly 2 MB of POST data—the server would perform 40 billion string comparisons. At 1 GHz, that’s at least 40 seconds of CPU time on a single core. With a 1 Gbit/s connection, an attacker could keep approximately 10,000 CPU cores busy.

How Languages Responded

The HashDoS revelation triggered a wave of security patches across the industry.

Perl: The Pioneer

Perl had already addressed this vulnerability in 2003, adding hash randomization with the PERL_HASH_SEED feature. The fix was simple: seed the hash function with a random value determined at process startup, making it impossible for attackers to predict which strings will collide.

Ruby: Immediate Response

Ruby’s security team was particularly responsive. CRuby 1.9 already used a randomized hash function, but CRuby 1.8, JRuby, and Rubinius were vulnerable. Within weeks of disclosure, new versions were released with randomized hashing and CVE-2011-4815 was assigned.

Python: SipHash Adoption

Python 3.3 introduced hash randomization controlled by the PYTHONHASHSEED environment variable. But this wasn’t considered sufficient. In 2013, PEP 456 proposed switching to SipHash, a cryptographically-secure pseudorandom function designed specifically for hash table security.

SipHash, created by Jean-Philippe Aumasson and Daniel J. Bernstein in 2012, provides strong collision resistance while remaining fast enough for hash table use. Python 3.4 adopted it as the default for string and bytes hashing.

Java: Tree Bins

Java took a different approach. Instead of changing the hash function (which would break compatibility), JEP 180 added a clever optimization: when a bucket’s linked list grows too long (default threshold: 8 elements), it’s converted to a balanced tree (red-black tree).

This changes the worst-case complexity from $O(n)$ to $O(\log n)$. An attack that would have taken 40 seconds might now take milliseconds. The trade-off: slightly higher memory usage and complexity for tree nodes.

Rust: Security by Default

Rust’s standard library hash map uses SipHash by default, providing resistance against HashDoS attacks out of the box. The documentation explicitly states: “By default, HashMap uses a hashing algorithm selected to provide resistance against HashDoS attacks.”

For performance-critical applications where DoS isn’t a concern, Rust allows using faster non-cryptographic hash functions like AHash through the BuildHasher trait.

The Modern Hash Table: SwissTable

In 2017, Google engineers introduced SwissTable, a hash table implementation that achieves 2-3× better performance than previous designs. SwissTable is now the default in Abseil (Google’s C++ library) and has been adopted by Go (as of Go 1.24).

SwissTable’s innovations include:

1. Control bytes: A metadata array stores control bytes for each slot, enabling SIMD-accelerated lookups. A single 128-bit SSE instruction can check 16 slots simultaneously.

2. Quadratic probing with limited search: The probe sequence is bounded, ensuring cache-friendly access patterns while avoiding pathological clustering.

3. High load factor: SwissTable can operate at load factors above 87.5% while maintaining excellent performance, as the metadata array enables fast rejection of non-matching slots.

The performance improvements come with trade-offs: SwissTable uses more memory for the control array, and deletion is slightly more complex. But for most applications, the speed gains far outweigh these costs.

The Mathematics of Clustering

Understanding why clustering degrades performance requires analyzing probe length distributions.

For linear probing with load factor $\alpha = n/m$ (where $n$ is the number of elements and $m$ is the table size), Knuth showed in The Art of Computer Programming that the expected number of probes for a successful search is approximately:

At $\alpha = 0.5$, this is about 1.5 probes. At $\alpha = 0.9$, it rises to 5.5 probes. But this is the average—worst-case probe lengths can be much higher due to clustering.

Primary clustering occurs because the probability that a given slot will be the next insertion target is proportional to the length of the cluster preceding it. Once a cluster forms, it acts like a “gravity well” for subsequent insertions, growing faster than isolated slots.

Robin Hood hashing addresses this by ensuring the probe length variance is minimized. If we define the “poverty” of an element as its probe length (how far it is from its ideal position), Robin Hood ensures that no element is significantly poorer than average. The result: predictable, bounded worst-case behavior.

Perfect Hashing: When Collisions Are Unacceptable

For static sets of keys where the entire key set is known in advance, perfect hashing guarantees zero collisions. A minimal perfect hash function maps $n$ keys to exactly $n$ consecutive integers with no collisions.

Perfect hashing is used in compiler symbol tables, database indexes, and any application where keys are fixed and lookup speed is critical. The trade-off: the hash function must be computed specifically for the key set, and adding or removing keys requires rebuilding the function.

Modern minimal perfect hash function algorithms, such as CHD (Compress, Hash, and Displace), can construct functions for millions of keys in seconds while using close to the theoretical minimum of space: approximately 2.07 bits per key.

Load Factor: The Hidden Performance Dial

The load factor $\alpha = n/m$ is the most important tuning parameter for hash tables. It represents the fraction of occupied slots.

Low load factors mean fewer collisions but more wasted memory. High load factors save memory but increase probe lengths and collision probability.

Most hash table implementations use a default load factor around 0.75, balancing memory usage and performance. Java’s HashMap and Python’s dict use exactly this value.

When the load factor exceeds the threshold, the table must be rehashed—all elements are moved to a larger table. This is an $O(n)$ operation that can cause unexpected latency spikes. Some applications pre-size hash tables to avoid rehashing during critical operations.

Resizing and Rehashing Costs

When a hash table grows beyond its capacity, it must be resized. Typically, the new size is double the old size, and all existing elements must be rehashed into their new positions.

This creates a subtle performance problem: a single insertion that triggers resizing takes $O(n)$ time instead of $O(1)$. For most applications, this amortized cost is acceptable—but not for latency-sensitive systems.

Incremental resizing addresses this by performing the rehash gradually. During each operation, a small number of elements are moved to the new table. Both tables are consulted during lookups until the migration completes. This spreads the $O(n)$ cost across many operations, eliminating latency spikes at the cost of slightly higher constant factors during the transition period.

The Enduring Lessons

The HashDoS attack of 2011 taught the software industry several lessons:

1. Algorithmic complexity is a security surface. Operations that are fast in the average case can become attack vectors if the worst case is dramatically different.

2. Deterministic algorithms are predictable. Hash functions that produce consistent output for the same input allow attackers to construct worst-case inputs.

3. Defense in depth matters. Randomization, tree-based fallbacks, and input size limits all provide different layers of protection.

4. Performance and security often trade off. SipHash is slower than simple hash functions but provides essential protection. Java’s tree bins add complexity but limit attack effectiveness.

Today’s hash tables are more sophisticated than ever—SwissTable’s SIMD optimizations, Rust’s trait-based hash function selection, and Java’s tree bin fallbacks all represent advances that balance performance, memory efficiency, and security. But the fundamental tension remains: hash tables achieve their remarkable average-case performance by accepting the possibility of worst-case degradation.

The mathematics that enables this—probability theory, clustering analysis, and the birthday paradox—has been understood for decades. What changed in 2011 was the realization that these mathematical properties could be weaponized. Modern hash table designs carry that lesson forward, building defenses against the predictable unpredictability of collisions.

References

1. Klink, A., & Wälde, J. (2011). “Effective Denial of Service Attacks against Web Application Platforms.” 28th Chaos Communication Congress.

2. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.

3. Aumasson, J. P., & Bernstein, D. J. (2012). “SipHash: A Fast Short-Input PRF.” International Conference on Cryptology in Africa.

4. Crosby, S. A., & Wallach, D. S. (2003). “Denial of Service via Algorithmic Complexity Attacks.” USENIX Security Symposium.

5. Preshing, J. (2011). “Hash Collision Probabilities.” Retrieved from https://preshing.com/20110504/hash-collision-probabilities/

6. Wikipedia. (2025). Hash table. Retrieved from https://en.wikipedia.org/wiki/Hash_table

7. Wikipedia. (2025). Birthday problem. Retrieved from https://en.wikipedia.org/wiki/Birthday_problem

8. OpenJDK. (2013). “JEP 180: Handle Frequent HashMap Collisions with Balanced Trees.” Retrieved from https://openjdk.org/jeps/180

9. Python Enhancement Proposals. (2013). “PEP 456 – Secure and interchangeable hash algorithm.” Retrieved from https://peps.python.org/pep-0456/

10. Abseil. (2018). “Swiss Tables and absl::Hash.” Retrieved from https://abseil.io/blog/20180927-swisstables

11. Go Blog. (2025). “Faster Go maps with Swiss Tables.” Retrieved from https://go.dev/blog/swisstable

12. Herlihy, M., Shavit, N., & Tzafrir, M. (2008). “Hopscotch Hashing.” International Symposium on Distributed Computing.

13. Pagh, R., & Rodler, F. F. (2004). “Cuckoo Hashing.” Journal of Algorithms, 51(2), 122-144.

14. Celis, P. E. (1986). Robin Hood Hashing. Ph.D. Thesis, University of Waterloo.

15. Richter, S., Alvarez, V., & Dittrich, J. (2015). “A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing.” Proceedings of the VLDB Endowment.

16. CERT. (2011). “VU#903934: Hash table implementations vulnerable to algorithmic complexity attacks.” Retrieved from https://www.kb.cert.org/vuls/id/903934

17. Ruby Language. (2012). “Hash-flooding DoS vulnerability for ruby 1.9 (CVE-2012-5371).” Retrieved from https://www.ruby-lang.org/en/news/2012/11/09/ruby19-hashdos-cve-2012-5371/

18. Lemire, D. (2013). “Hashing and the Birthday paradox: a cautionary tale.” Retrieved from https://lemire.me/blog/2013/06/17/hashing-and-the-birthday-paradox-cautionary-tale/

19. Slater, M. (2023). “Optimizing Open Addressing.” Retrieved from https://thenumb.at/Hashtables/

20. Wikipedia. (2025). Perfect hash function. Retrieved from https://en.wikipedia.org/wiki/Perfect_hash_function