Hash Collision Attacks

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

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!

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!

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!

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

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

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

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

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×

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

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

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

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

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)

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

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

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