Hash Collision Attacks - When Hashing Fails — Pathological Cases & Alternatives | OneNoughtOne

0/361

Data Structures & AlgorithmsHash Tables

When Hashing Fails — Pathological Cases & Alternatives

LevelAdvanced

Duration75 mins

TopicHash Tables

1 / 4

Hash Collision Attacks

When O(1) Becomes O(n): The Security Nightmare

Throughout this chapter, we've celebrated hash tables as one of computer science's greatest inventions—providing O(1) average-time access for insertion, lookup, and deletion. But there's a dark side to this story that every professional engineer must understand: hash tables can be weaponized against the systems that use them.

In 2011, a team of security researchers presented a devastating attack at the 28th Chaos Communication Congress. By carefully crafting HTTP request parameters, they could bring web servers—running PHP, Python, Ruby, Java, and ASP.NET—to their knees with a single request. The attack exploited a fundamental weakness: hash tables with predictable hash functions are vulnerable to algorithmic complexity attacks.

This isn't theoretical. Major platforms including Tomcat, Jetty, and countless web applications were vulnerable. The attack could turn a server processing 10,000 requests per second into one struggling with a single request. Understanding this vulnerability is essential for building secure, resilient systems.

The Stakes Are Real

Hash collision attacks have been used in real-world denial-of-service (DoS) attacks against production systems. This isn't a theoretical exercise—it's a practical concern for anyone building web services, parsing user input, or processing untrusted data. By the end of this page, you'll understand exactly how these attacks work and how to defend against them.

Understanding the Attack Vector

To understand hash collision attacks, we need to revisit a fundamental promise of hash tables and examine when that promise breaks down.

The O(1) Promise:

Hash tables provide O(1) average-case performance. This average assumes that hash function outputs are distributed roughly uniformly across the hash table's buckets. When this assumption holds, each bucket contains approximately n/m elements (where n is the number of elements and m is the number of buckets), making lookups and insertions fast.

The O(n) Reality:

However, hash tables have O(n) worst-case performance. If an attacker can force all n elements to hash to the same bucket, the hash table degenerates into a linked list. Every operation—insert, lookup, delete—now requires traversing all n elements.

The Attack Principle:

An algorithmic complexity attack exploits this gap between average and worst case. Rather than attacking the network, memory, or CPU directly, the attacker exploits the algorithm's design to force worst-case behavior. For hash tables, this means finding inputs that all hash to the same value.

NORMAL OPERATION (Uniform Distribution)
════════════════════════════════════════════════════════════════
 
Hash Table with 8 buckets, 16 elements:
┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Bucket │ Bucket │ Bucket │ Bucket │ Bucket │ Bucket │ Bucket │ Bucket │
│   0    │   1    │   2    │   3    │   4    │   5    │   6    │   7    │
├────────┼────────┼────────┼────────┼────────┼────────┼────────┼────────┤
│   ●    │   ●    │   ●    │   ●    │   ●    │   ●    │   ●    │   ●    │
│   ●    │   ●    │        │   ●    │        │   ●    │   ●    │   ●    │
│        │        │        │   ●    │        │        │        │   ●    │
└────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘
 
Average chain length: 2 elements
Lookup time: O(1) — check 1-3 elements per lookup
 
 
UNDER ATTACK (All Collisions)
════════════════════════════════════════════════════════════════
 
Hash Table with 8 buckets, 16 elements (ALL in bucket 3):
┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│ Bucket │ Bucket │ Bucket │ Bucket │ Bucket │ Bucket │ Bucket │ Bucket │
│   0    │   1    │   2    │   3    │   4    │   5    │   6    │   7    │
├────────┼────────┼────────┼────────┼────────┼────────┼────────┤────────│
│        │        │        │   ●    │        │        │        │        │
│        │        │        │   ●    │        │        │        │        │
│        │        │        │   ●    │        │        │        │        │
│        │        │        │   ●    │        │        │        │        │
│        │        │        │   │    │        │        │        │        │
│        │        │        │  ...   │        │        │        │        │
│        │        │        │   ●    │ (16 elements in chain)            │
└────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘
 
Chain length: 16 elements (or n in general)
Lookup time: O(n) — must check every element!

The Quadratic Amplification

Here's the devastating math: inserting n colliding keys requires 1 + 2 + 3 + ... + n comparisons = n(n+1)/2 = O(n²) total time. For n = 100,000 keys, that's approximately 5 billion operations for what should be 100,000 operations. A single malicious request can consume CPU for minutes instead of milliseconds.

The Anatomy of a Hash Collision Attack

Let's dissect exactly how an attacker crafts collision-inducing inputs. The process requires reverse-engineering or discovering the hash function used by the target system.

Step 1: Identify the Hash Function

Many programming languages use well-known hash functions with publicly available implementations:

Java String.hashCode(): Uses a polynomial rolling hash with multiplier 31
Python dict (pre-3.3): Used a modified FNV hash
PHP arrays: Used DJBX33A (DJB's times-33 hash)
Ruby hashes (pre-1.9): Used a simple string hash

Once you know the hash function, you can analyze it mathematically to find collision patterns.

Step 2: Find Equivalent Class Inputs

For many hash functions, finding collisions is straightforward once you understand the algorithm. Consider Java's String.hashCode():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Java's String.hashCode() implementation
public int hashCode() {
    int h = 0;
    for (int i = 0; i < value.length; i++) {
        h = 31 * h + value[i];
    }
    return h;
}
 
// The mathematical formula for a string s of length n:
// hash(s) = s[0] * 31^(n-1) + s[1] * 31^(n-2) + ... + s[n-1]
 
// CRITICAL OBSERVATION:
// For two-character strings "ab":
// hash("ab") = a * 31 + b
 
// If we find strings where a₁ * 31 + b₁ = a₂ * 31 + b₂
// Then those strings collide!
 
// Example collision pair:
// hash("Aa") = 'A' * 31 + 'a' = 65 * 31 + 97 = 2112
// hash("BB") = 'B' * 31 + 'B' = 66 * 31 + 66 = 2112
 
// "Aa" and "BB" have the SAME hash code!

Step 3: Generate Exponentially Many Collisions

Once we have one collision pair, we can generate exponentially many collisions through concatenation. If strings A and B collide (hash(A) == hash(B)), then for any string X:

hash(AX) and hash(BX) also collide
hash(XA) and hash(XB) also collide
hash(AA), hash(AB), hash(BA), hash(BB) all collide with each other

From a single collision pair, we can generate 2^k colliding strings of length 2k. For k=16, that's 65,536 colliding strings—enough to devastate any server.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Starting with collision pair: "Aa" and "BB" (both hash to 2112 in Java)
 
def generate_colliding_strings(collision_pair, length_power):
    """
    Generate 2^length_power strings that all hash to the same value.
    
    Args:
        collision_pair: Tuple of two strings with same hash (e.g., ("Aa", "BB"))
        length_power: Number of times to concatenate (strings will have 2^length_power chars)
    
    Returns:
        List of 2^length_power strings, all with identical hash codes
    """
    a, b = collision_pair
    current = [a, b]  # Start with 2 colliding strings
    
    for _ in range(length_power - 1):
        next_gen = []
        for s in current:
            next_gen.append(s + a)  # Append first collision element
            next_gen.append(s + b)  # Append second collision element
        current = next_gen
    
    return current
 
# Generate 2^10 = 1024 colliding strings
collision_pair = ("Aa", "BB")
colliding_strings = generate_colliding_strings(collision_pair, 10)
 
print(f"Generated {len(colliding_strings)} colliding strings")
# All 1024 strings have the SAME Java hashCode!
 
# Verify (conceptually - actual hash would use Java's algorithm):
# "AaAaAaAaAaAaAaAaAaAa" 
# "AaAaAaAaAaAaAaAaAaBB"
# "AaAaAaAaAaAaAaAaBBAa"
# ...
# "BBBBBBBBBBBBBBBBBBBB"
# All hash to the same value!

The Attack Power

With just one 2-character collision pair, an attacker can generate millions of colliding strings. A malicious HTTP POST request containing 100,000 parameters—each with a colliding key—forces the server to perform billions of comparisons. Web frameworks that automatically parse POST data into hash tables become instant victims.

Real-World Attack Scenarios

Hash collision attacks have been demonstrated against real production systems. Let's examine specific scenarios where these vulnerabilities manifest.

Scenario 1: Web Request Parameter Parsing

When a web application receives an HTTP POST request with form data, the framework parses the parameters into a hash table (dictionary). Consider this attack:

MALICIOUS HTTP REQUEST:
════════════════════════════════════════════════════════════════
 
POST /api/submit HTTP/1.1
Host: vulnerable-server.com
Content-Type: application/x-www-form-urlencoded
Content-Length: 1234567
 
AaAaAaAaAa=1&AaAaAaAaBB=2&AaAaAaBBAa=3&AaAaAaBBBB=4&AaAaBBAaAa=5&
AaAaBBAaBB=6&AaAaBBBBAa=7&AaAaBBBBBB=8&AaBBAaAaAa=9&AaBBAaAaBB=10&
... (100,000 more parameters with colliding keys) ...
 
WHAT HAPPENS ON THE SERVER:
════════════════════════════════════════════════════════════════
 
1. Framework receives POST data
2. Parses parameters into dict/HashMap:
   params = {}
   
3. For each parameter (key=value):
   - Compute hash(key)           ← ALL keys hash to same value!
   - Insert into params[key]     ← Linear search through collision chain
   
4. Insertion complexity:
   - Parameter 1: 0 comparisons
   - Parameter 2: 1 comparison
   - Parameter 3: 2 comparisons
   - ...
   - Parameter 100,000: 99,999 comparisons
   
   TOTAL: 1 + 2 + ... + 99,999 = ~5 BILLION operations
   
5. Result: Single request takes MINUTES of CPU time
   Server becomes unresponsive to all other requests

Scenario 2: JSON Parsing

JSON objects are parsed into hash maps in virtually every language. An attacker can craft a JSON payload where all keys are carefully chosen to collide:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
{
    "AaAaAaAaAaAa": 1,
    "AaAaAaAaAaBB": 2,
    "AaAaAaAaBBAa": 3,
    "AaAaAaAaBBBB": 4,
    "AaAaAaBBAaAa": 5,
    "AaAaAaBBAaBB": 6,
    // ... 99,994 more keys ...
    "BBBBBBBBBBBB": 100000
}
 
// Every single key hashes to the same bucket
// Parsing this JSON requires O(n²) time instead of O(n)
// A 2MB JSON file that should parse in 10ms takes 10 minutes

Scenario 3: URL Query String Attacks

Web servers often parse query strings into dictionaries. A malicious URL can trigger the attack:

https://api.example.com/search?AaAaAa=1&AaAaBB=2&AaBBAa=3&... (thousands more)

Scenario 4: Configuration File Parsing

INI files, YAML documents, and TOML configurations are often parsed into dictionaries. A malicious configuration file (perhaps uploaded by an attacker or injected through a vulnerability) can trigger O(n²) parsing.

Scenario 5: Database Query Result Processing

If database results are mapped to dictionaries (by column name) and an attacker controls column names or aliases, they might be able to craft collisions.

Documented Hash Collision Vulnerabilities (2011-2012)
Platform/Language	Hash Function	CVE/Advisory	Impact
PHP	DJBX33A	CVE-2011-4885	DoS via POST parameters
Python	Modified FNV	CVE-2012-1150	DoS via untrusted input
Ruby	MurmurHash	CVE-2011-4815	DoS via request parameters
Java (Tomcat)	String.hashCode()	CVE-2011-4858	DoS via POST/GET parameters
ASP.NET	String.GetHashCode()	MS11-100	DoS via form data
V8 JavaScript	Object hash	n/a	DoS via property names

Industry-Wide Impact

When these vulnerabilities were disclosed in late 2011, virtually every major web platform was affected. The attack was simple to execute (just send a crafted POST request), effective (bringing servers down with minimal bandwidth), and universal (exploiting fundamental data structure behavior). Emergency patches were required across the entire industry.

Measuring Attack Effectiveness

To understand the severity of hash collision attacks, let's quantify the amplification factor—how much computational work an attacker can force the victim to perform relative to the attack's cost.

Attack Cost Analysis:

Attacker's work: Generate n colliding strings (O(n) time, trivial)
Attacker's bandwidth: Send n key-value pairs (approximately n × key_length bytes)
Victim's work: Insert n elements into degenerated hash table (O(n²) time)

Amplification Factor:

COST-BENEFIT ANALYSIS OF HASH COLLISION ATTACK
════════════════════════════════════════════════════════════════
 
Let:
  n = number of colliding keys in attack payload
  k = average key length in bytes
  c = time for one hash comparison (nanoseconds)
 
ATTACKER'S COST:
  Bandwidth:  n × (k + value_size) bytes
  For n = 100,000, k = 20, value = 1 byte:
  ≈ 2 MB of data (trivial for any internet connection)
 
VICTIM'S COMPUTATIONAL COST:
  Comparisons: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2
  For n = 100,000:
  = 100,000 × 99,999 / 2
  = 4,999,950,000 comparisons
  ≈ 5 BILLION operations
 
  If each comparison takes 100 nanoseconds:
  = 5 × 10⁹ × 100 × 10⁻⁹ seconds
  = 500 seconds
  ≈ 8+ MINUTES of CPU time for ONE request
 
AMPLIFICATION:
  Attacker sends:    2 MB in ~1 second
  Victim processes:  500 CPU-seconds
  
  AMPLIFICATION FACTOR = 500× 
  
  One attacker machine can keep 500 server cores busy!
 
COMPARISON TO NORMAL OPERATION:
  Normal insert of 100,000 unique keys: ~100,000 operations
  Attack insert of 100,000 colliding keys: ~5,000,000,000 operations
  
  Slowdown factor: 50,000×

Practical Impact Measurements:

The original researchers demonstrated the following attack effectiveness on common platforms (2011 hardware):

Measured Attack Performance (2011)
Platform	Normal Request (1000 params)	Attack Request (1000 colliding params)	Slowdown
PHP 5.3	~0.05 seconds	~30 seconds	600×
Python 2.7	~0.003 seconds	~7 seconds	2,300×
Ruby 1.8	~0.02 seconds	~20 seconds	1,000×
Java (Tomcat)	~0.002 seconds	~15 seconds	7,500×
ASP.NET	~0.001 seconds	~12 seconds	12,000×

Low Bandwidth, High Impact

Unlike traditional DDoS attacks that require massive bandwidth to overwhelm networks, hash collision attacks are 'asymmetric'—a small amount of attacker bandwidth translates into enormous computational cost for the victim. A single laptop on a home internet connection could theoretically bring down a major website.

Defense Mechanisms

The industry has developed several approaches to mitigate hash collision attacks. Understanding these defenses is crucial for building secure systems.

Defense 1: Hash Randomization (Primary Defense)

The most effective defense is to make hash function outputs unpredictable to attackers. Instead of using a fixed hash function, each process (or even each hash table instance) uses a randomly-seeded variation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# VULNERABLE: Fixed hash function
def vulnerable_hash(s):
    """Same input always produces same output - attackable!"""
    h = 0
    for c in s:
        h = 31 * h + ord(c)
    return h
 
# SECURE: Randomized hash function (conceptual)
import secrets
 
# Secret seed generated at process startup - unknown to attacker
HASH_SEED = secrets.randbelow(2**64)
 
def secure_hash(s):
    """Output varies with secret seed - attacker can't predict collisions!"""
    h = HASH_SEED  # Initialize with secret
    for c in s:
        h = 31 * h + ord(c)
        h ^= (h >> 17)  # Additional mixing with seed influence
    return h
 
# Attacker's dilemma:
# - They don't know HASH_SEED
# - They can't predict which inputs will collide
# - Pre-computed collision sets don't work
# - Each server (or process restart) has different seed
 
# Real implementations (Python 3.3+, Ruby 1.9+, PHP 5.4+):
# - SipHash with random keys
# - Randomized initial hash state
# - Per-process or per-table seeding

Defense 2: Limit Input Size

A simple but effective mitigation is to limit the number of parameters, keys, or elements that can be parsed from untrusted input:

CONFIGURATION EXAMPLES:
 
PHP (php.ini):
  max_input_vars = 1000        ; Limit POST/GET/COOKIE parameters
  post_max_size = 8M           ; Limit POST body size
 
Apache Tomcat (server.xml):
  maxParameterCount="10000"    ; Limit URL/body parameters
  
Python (Django settings.py):
  DATA_UPLOAD_MAX_NUMBER_FIELDS = 1000
 
.NET (web.config):
  <appSettings>
    <add key="aspnet:MaxHttpCollectionKeys" value="1000" />
  </appSettings>
 
IMPACT:
  With n limited to 1000:
  - Worst-case comparisons: 1000 × 999 / 2 ≈ 500,000
  - Still O(n²), but bounded to acceptable level
  - Processing time: milliseconds instead of minutes

Defense 3: Use Collision-Resistant Hash Functions

Some hash functions are designed specifically to resist collision attacks. SipHash, developed by Jean-Philippe Aumasson and Daniel J. Bernstein, has become the standard for hash table implementations:

Cryptographically-keyed: Requires a secret key, making collisions unpredictable
Fast: Optimized for short inputs (like hash table keys)
Proven security: Formal security proofs against collision-finding attacks

Defense 4: Use Alternative Collision Handling

Some modern hash table implementations switch collision handling based on chain length:

JAVA 8+ HASHMAP: TREEIFICATION
════════════════════════════════════════════════════════════════
 
Normal operation (short chains):
┌─────────┐
│ Bucket  │──▶ [E1] ──▶ [E2] ──▶ [E3]    (Linked list: O(n) search)
└─────────┘
 
When chain length > TREEIFY_THRESHOLD (8):
┌─────────┐
│ Bucket  │──▶ Red-Black Tree               (Tree: O(log n) search)
└─────────┘
                     [E2]
                    /    \
                 [E1]    [E3]
 
IMPACT ON ATTACK:
  - Attack still causes collisions
  - But each bucket becomes a balanced tree
  - Search degrades to O(log n) per operation, not O(n)
  - Total insert time: O(n log n) instead of O(n²)
  
  For n = 100,000:
    Without trees: 5,000,000,000 operations
    With trees:    100,000 × 17 = 1,700,000 operations
    
  Slowdown factor: ~3,000×
  Still exploitable, but much less severe

Defense in Depth

The best protection combines multiple defenses: hash randomization (makes attacks unpredictable), input limits (bounds worst-case impact), timeout limits (kills runaway requests), and monitoring (detects unusual patterns). Defense in depth ensures that even if one layer is bypassed, others still provide protection.

Modern Language Mitigations

Following the 2011-2012 disclosures, all major programming languages implemented mitigations. Understanding what your language/runtime does by default is essential for assessing your exposure.

Python 3.3+ (PEP 456)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Python 3.3+ uses SipHash-2-4 with per-process random seed
 
import sys
print(hash("hello"))  # Different each time Python starts!
 
# First run:  8757621758522689772
# Second run: -2040436329648608789
# Third run:   4918282893936604556
 
# Environment variable to control:
# PYTHONHASHSEED=random   (default: different each run)
# PYTHONHASHSEED=0        (disable randomization - NOT RECOMMENDED)
# PYTHONHASHSEED=12345    (fixed seed - for debugging only)
 
# Implications:
# - Dictionary iteration order is unpredictable (Python 3.7+ guarantees insertion order)
# - hash() values are not portable across runs
# - Collision attacks become impractical

Java 8+

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Java HashMap combines hash spreading with treeification
 
public class HashMap<K,V> {
    // DEFENSE 1: Hash spreading
    static final int hash(Object key) {
        int h;
        // XOR high bits into low bits to spread out collisions
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    // DEFENSE 2: Treeification when chains get too long
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // When a bucket exceeds 8 nodes AND table size ≥ 64:
    // Convert linked list to red-black tree (TreeNode)
    // Search becomes O(log n) instead of O(n)
}
 
// Note: Java String.hashCode() is still deterministic
// Treeification mitigates but doesn't prevent the attack
// High CPU usage is still possible (O(n log n) vs O(n) normal)

JavaScript (V8, SpiderMonkey, JavaScriptCore)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// JavaScript engines use various protections:
 
// 1. Property access uses hidden classes, not just hash tables
// 2. Hash functions are keyed/randomized per-isolate
// 3. Object shapes are tracked separately from values
 
// Example of why attacks are harder in JS:
const obj = {};
for (let i = 0; i < 100000; i++) {
    obj["key" + i] = i;  // V8 optimizes consistent property addition
}
 
// Modern V8 uses:
// - Swiss Tables (hash table with SIMD probing)
// - Randomized hash seeds
// - Multiple storage strategies based on usage patterns
 
// Node.js also limits:
// - URL query string parameters (--max-http-header-size)
// - JSON parsing depth

Current Language Protections (2024)
Language/Runtime	Primary Defense	Secondary Defense	Status
Python 3.3+	SipHash with random seed	Per-process seed	Secure by default
Ruby 1.9.3+	SipHash-2-4	Random seed per process	Secure by default
PHP 7.0+	DJB33A variant + seed	Input limits	Secure by default
Java 8+	Hash spreading	Treeification	Partially mitigated
Perl 5.18+	Perturbed hash function	Random seed	Secure by default
Node.js 12+	V8's randomized hash	Request limits	Secure by default
Go	Runtime hash randomization	Per-process seed	Secure by default
.NET Core	Randomized GetHashCode()	Request limits	Secure by default

The Industry Learned

The 2011 disclosures prompted a fundamental rethinking of hash table security. Today, most modern languages and frameworks are secure by default. However, legacy systems, custom hash tables, and embedded systems may still be vulnerable. Always verify your specific runtime version and configuration.

Detecting and Preventing Attacks in Production

Even with language-level protections, sophisticated attackers may find edge cases or target legacy systems. Here are practical strategies for detection and prevention in production environments.

Detection Strategies:

Indicators of Hash Collision Attacks

•Unusual CPU spike without I/O activity — Hash collision attacks consume CPU but don't increase disk or network I/O proportionally
•Single request consuming excessive time — Normal requests complete in milliseconds; attack requests take seconds to minutes
•Request body with many similarly-named parameters — Colliding strings often have repetitive patterns
•High parameter count relative to body size — Attacks optimize for parameter count, not data volume
•Worker thread/process starvation — All workers become busy processing slow requests

Prevention Checklist:

LANGUAGE/FRAMEWORK LEVEL:
─────────────────────────────────────────────────────────────────
□ Verify runtime uses randomized hashing (check version, docs)
□ Don't disable hash randomization (PYTHONHASHSEED=0, etc.)
□ Use latest stable version of language/runtime
□ Review any custom hash table implementations
 
APPLICATION LEVEL:
─────────────────────────────────────────────────────────────────
□ Limit maximum POST body size
□ Limit maximum number of request parameters
□ Limit maximum JSON object depth and key count
□ Limit maximum query string length
□ Set reasonable request timeout limits
□ Validate and sanitize untrusted input structure
 
INFRASTRUCTURE LEVEL:
─────────────────────────────────────────────────────────────────
□ Use load balancers with request timeout enforcement
□ Implement rate limiting per IP/client
□ Monitor CPU usage per request (APM tools)
□ Set up alerts for unusual request duration patterns
□ Deploy WAF rules to detect parameter flooding
 
MONITORING:
─────────────────────────────────────────────────────────────────
□ Track request processing time histograms
□ Alert on p99 latency increases
□ Monitor for worker pool exhaustion
□ Log requests exceeding threshold parameter counts
□ Track CPU time per request in APM

WAF Rules Can Help

Web Application Firewalls can detect and block requests with excessive parameter counts or suspicious patterns before they reach your application. Configure rules to reject requests with more than a threshold number of parameters (e.g., 1000) or parameter names matching known collision patterns.

Summary: Lessons from Hash Collision Attacks

Hash collision attacks reveal a profound truth about algorithm design: worst-case complexity matters, not just average-case. Let's consolidate the key lessons:

Key Takeaways

•Hash tables have O(n) worst-case, not O(1) — The average-case guarantee relies on assumptions about input distribution that attackers can violate.
•Predictable hash functions are a vulnerability — If an attacker can predict hash collisions, they can force worst-case behavior.
•Hash randomization is the primary defense — Using secret, per-process hash seeds makes collision prediction infeasible.
•Input limits provide backup protection — Even without hash randomization, limiting parameter counts bounds the attack impact.
•Quadratic amplification is devastating — O(n²) algorithms on attacker-controlled input are always dangerous.
•Modern languages are mostly protected — Since 2012, most major languages use randomized hashing by default.
•Defense in depth is essential — Combine hash randomization, input limits, timeouts, and monitoring.

The Broader Lesson:

Hash collision attacks exemplify a class of vulnerabilities called algorithmic complexity attacks. Any algorithm with a gap between average and worst-case complexity is potentially vulnerable when processing untrusted input. Examples include:

Regular expression denial of service (ReDoS): Backtracking regex engines have exponential worst-case
XML bombs: Entity expansion can cause exponential memory/time consumption
Sorting attacks: Some sorting algorithms have O(n²) worst-case (QuickSort with bad pivots)
Graph algorithms: Some pathfinding algorithms can be forced into expensive paths

The key insight: Always consider what happens when an adversary controls your input.

Page Complete

You now understand hash collision attacks—how they work, why they're devastating, and how to defend against them. This knowledge is essential for building secure systems that process untrusted data. Next, we'll examine another hash table pitfall: choosing poor hash functions that cause unintentional performance degradation.