title: “Hash-Flooding DoS Attacks and Defense in Rust” meta_description: “Learn about HashDoS attacks, SipHash, RandomState, and how to protect HashMap from algorithmic complexity attacks.” keywords: [“hashdos”, “hash flooding”, “siphash rust”, “randomstate”, “dos attack prevention”, “algorithmic complexity attack”]

🔐 Reinventing from Scratch: Building HashMap

Chapter 6 — “Hasher and DoS Resistance”

“A predictable hash function is an attacker’s best friend.”

🧭 6.1. The Hash-Flooding Attack

Imagine an attacker who can send data to your server:

// Your innocent HashMap
let mut cache: HashMap<String, Data> = HashMap::new();

// Attacker sends these keys (carefully chosen):
for key in attacker_keys {
    cache.insert(key, data);
}

What if all those keys hash to the same bucket?

💥 6.2. Algorithmic Complexity Attack

Normal Case (Good Distribution)

Buckets: [X, _, X, _, X, _, X, _]
Lookups: O(1) average

Attack Case (Forced Collisions)

Buckets: [XXXXXXXXXX, _, _, _, _, _, _, _]
All 10 keys in bucket 0!
Lookups: O(n) — must check all 10 entries

Impact:

• 1,000 malicious keys → 1,000x slower
• 10,000 keys → 10,000x slower
• Server grinds to a halt → Denial of Service

🎯 6.3. How Attackers Find Collisions

Step 1: Reverse-Engineer the Hash Function

If you use a deterministic, public hash function:

// If everyone uses the same FNV hash...
fn fnv_hash(s: &str) -> u64 {
    let mut hash = 0xcbf29ce484222325u64;
    for byte in s.bytes() {
        hash ^= byte as u64;
        hash = hash.wrapping_mul(0x100000001b3);
    }
    hash
}

Attacker can:

1. Download your code
2. Find the hash function
3. Generate keys that collide

Step 2: Generate Colliding Keys

# Attacker's script
def find_collisions(target_hash, count):
    collisions = []
    for i in range(1000000):
        key = f"attack_{i}"
        if fnv_hash(key) % 16 == target_hash:
            collisions.append(key)
            if len(collisions) >= count:
                break
    return collisions

# Generate 10,000 keys that all hash to bucket 0
attack_keys = find_collisions(0, 10000)

Step 3: Send to Victim

# Attacker floods your API
for key in attack_keys:
    POST /api/data {"key": key, "value": "X"}

Your server’s HashMap now has 10,000 entries in one bucket → O(n) operations.

🛡️ 6.4. Defense: Randomized Hashing

Solution: Add a secret random seed to the hash function!

struct RandomState {
    k0: u64,  // Random seed 1
    k1: u64,  // Random seed 2
}

impl RandomState {
    fn new() -> Self {
        Self {
            k0: rand::random(),
            k1: rand::random(),
        }
    }
}

Now the hash depends on the seed:

hash("attack_0") with seed_A = 42
hash("attack_0") with seed_B = 9831  // Different!

Attacker can’t predict which bucket keys will land in!

🔒 6.5. SipHash: Cryptographic Hashing

Rust uses SipHash by default (via RandomState):

What Makes SipHash Special?

1. Keyed hash function — Requires a secret key
2. Cryptographically strong — Can’t reverse-engineer easily
3. Fast enough — Not as fast as FNV, but secure

The Algorithm (Simplified)

pub struct SipHasher {
    k0: u64,  // Secret key part 1
    k1: u64,  // Secret key part 2
    // ... internal state ...
}

impl SipHasher {
    fn new_with_keys(k0: u64, k1: u64) -> Self {
        // Initialize internal state with keys
        // Process data through multiple compression rounds
        // Output is cryptographically strong
    }
}

Key point: Without knowing k0 and k1, attackers can’t predict collisions.

⚖️ 6.6. Performance Tradeoff

Rust’s default (RandomState → SipHash):

• Fast enough for most uses
• Secure against DoS
• Good default choice

🎲 6.7. Implementing Custom BuildHasher

You can provide your own:

use std::hash::BuildHasherDefault;
use rustc_hash::FxHasher;  // Fast but NOT DoS-resistant

type FastHashMap<K, V> = MyHashMap<K, V, BuildHasherDefault<FxHasher>>;

let mut map = FastHashMap::default();

When is this OK?

• Internal data structures
• No untrusted input
• Performance critical and you trust your data

🧪 6.8. Testing DoS Resistance

#[test]
fn test_different_seeds_produce_different_hashes() {
    let map1 = MyHashMap::<String, i32>::new();
    let map2 = MyHashMap::<String, i32>::new();
    
    let key = "test_key";
    
    let hash1 = map1.hash_key(&key);
    let hash2 = map2.hash_key(&key);
    
    // With RandomState, these should differ!
    assert_ne!(hash1, hash2);
}

#[test]
fn test_collision_attack_resistance() {
    let mut map = MyHashMap::new();
    
    // Try to create collisions (won't work with random seed!)
    for i in 0..10000 {
        map.insert(format!("attack_{}", i), i);
    }
    
    // Measure max probe distance
    // Should be reasonable (< 20) even with 10k entries
    // If using predictable hash, would be > 1000
}

🌐 6.9. Real-World DoS Attacks

Case Study: Python 2.x (Pre-2012)

Python’s dict used predictable hashing:

# Attacker could generate keys that all collide
hash("Aa") == hash("BB")  # True in Python 2!

Result: Websites crashed when sent ~100KB of colliding JSON keys.

Fix: Python 3 added randomized hashing (like Rust).

Case Study: Ruby (2011)

Similar issue — predictable hash function led to DoS attacks on Rails apps.

Lesson: Always use randomized hashing for untrusted input!

🧠 6.10. Chapter Takeaways

🚀 6.11. What’s Next

We now have:

• Secure hashing (RandomState + SipHash)
• Insertion and deletion
• Safe iteration

Next: Chapter 7 — Panic Safety and Invariants

Learn how to maintain HashMap invariants even when code panics, ensuring no memory leaks or corruption.

💡 Exercises

1. Implement your own BuildHasher using FNV hash
2. Benchmark SipHash vs FxHash on small keys
3. Try to generate colliding keys for FNV (it’s possible!)
4. Measure probe distances with predictable vs random hash
5. Research other DoS-resistant hash functions (AHash, HighwayHash)

Next: Chapter 7 — Panic Safety and Invariants ⚠️