HashDoS and Security Considerations

A Hash Collision Denial-of-Service (HashDoS) attack occurs when an attacker supplies craftily chosen keys (such as HTTP query parameters, JSON object keys, or form fields) that all collide into the exact same hash bucket, degrading $O(1)$ hash table insertions into $O(n^2)$ total time and freezing the server CPU.

How a HashDoS Attack Degrades $N$ Insertions to $O(n^2)$

If a server parses $N = 50,000$ JSON fields into a HashMap that uses a predictable, unseeded hash function (like FNV-1a or FxHash):

1. An attacker precomputes $50,000$ short strings that all produce the same hash under that fixed algorithm.
2. Inserting the $i$-th colliding key must probe past all $i - 1$ previously inserted keys and compare each one with Eq::eq.
3. Total comparisons for $N$ insertions jump from $N$ ($\sim 50,000$ ops) to $\frac{N(N - 1)}{2} \approx 1.25 \times 10^9$ comparisons, pinning a CPU core for seconds from a single kilobyte request.

Normal Traffic (Uniform Hashes):         HashDoS Attack (All Keys Collide):
Bucket 0: [ k1 ]                         Bucket 0: [ k1, k2, k3, ..., k_N ]
Bucket 1: [ k2 ]                         Bucket 1: [ ]
Bucket 2: [ k3 ]                         Bucket 2: [ ]
Total time for N inserts: O(N)           Total time for N inserts: O(N^2)!

How Rust Protects Against HashDoS by Default (RandomState + SipHash-1-3)

By default, std::collections::HashMap<K, V> and HashSet<T> use RandomState, which combines two defenses:

1. Per-instance random 128-bit key (k0, k1): Every new HashMap seeds its BuildHasher from OS entropy (via thread-local CSPRNG). Even if an attacker knows the source code, they do not know the secret (k0, k1) seed of the HashMap inside the running process.
2. SipHash-1-3 keyed pseudorandom function (PRF): Mixes input bytes with the 128-bit secret key using cryptographic ARX (add-rotate-xor) rounds so an attacker cannot deduce colliding inputs without knowing the secret seed.

use std::collections::hash_map::RandomState;
use std::hash::{BuildHasher, Hasher};

fn hash_with_state(state: &RandomState, text: &str) -> u64 {
    let mut hasher = state.build_hasher();
    hasher.write(text.as_bytes());
    hasher.finish()
}

fn main() {
    // Two independent RandomState instances generate different random seeds:
    let state_a = RandomState::new();
    let state_b = RandomState::new();

    let h_a = hash_with_state(&state_a, "user_input");
    let h_b = hash_with_state(&state_b, "user_input");

    println!("Map A hash of 'user_input': 0x{h_a:016x}");
    println!("Map B hash of 'user_input': 0x{h_b:016x}");
    assert_ne!(h_a, h_b);
}

Map A hash of 'user_input': 0x73a1f9c24b8019d2
Map B hash of 'user_input': 0xe14908b36d25a04f

Security Rules When Choosing a Non-Default Hasher