Hashing — tables, crypto, rings, passwords, Bloom

cs · folio

In one line: A hash maps any input to a fixed-size value. Table hashes want speed, spread and a secret seed against flooding (SipHash); cryptographic hashes want preimage and collision resistance (SHA-256, SHA-3); password hashes want to be slow and memory-hard (Argon2id); a MAC needs a key (HMAC). Collisions always exist — the question is only what it costs to find one.

Download PDF Print view LaTeX source

Hashing — tables, crypto, rings, passwords, Bloom — figure 1

Hash tables in real runtimes

tablelayoutgrowhash · seed
Swift Set, Dictionaryopen addressing, linear probing, occupancy bitmap; delete shifts the chain back — no tombstones3/4SipHash-1-3; 128-bit seed per process + per table
CPython dictcompact (3.6): sparse index → dense entries in insertion order (guaranteed 3.7); probe j ←5j+1+perturb; delete leaves a dummy2/3str / bytes: SipHash-1-3 (3.11); seeded since 3.3; PYTHONHASHSEED
Java HashMapchaining; 16 buckets, doubles; adding to a bin of ≥8 makes it a red-black tree (if ≥64 buckets, else resize); list again at ≤60.75hashCode() xor h>>>16; unseeded: String is h ←31h + c per char
Rust HashMapport of Google’s SwissTable—SipHash 1-3; seed per instance
Go map (1.24)Swiss Table: groups of 8 slots + a control byte each (7 hash bits); ≤1024 entries per table, each grows alone7/8random seed per map; iteration order randomised

Seeds against flooding

  • HashDoS (oCERT-2011-003, Klink & Wälde, Dec 2011): POST parameters chosen to collide put every key in one bucket — dict insertion becomes O(n2), 100 % CPU for hours. Java, PHP, Python, Ruby, V8 and more; the same class as Crosby & Wallach’s 2003 attack on Perl.
  • SipHash (Aumasson & Bernstein, 2012): a keyed PRF built against hash flooding. SipHash-c-d = c rounds per 8-byte word, d at the end; reference 2-4, 128-bit key, 64-bit result. c ≥2, d ≥4 is the conservative bound — Swift, Rust and CPython run 1-3 for speed.
  • Non-cryptographic hashes (xxHash) are fast but not PRFs; Rust’s docs: faster hashers “will typically not protect against attacks such as HashDoS”.
  • Java’s String.hashCode is a specified, unseeded formula; Java 8 fixed the table instead (JEP 180): colliding bins become trees, worst case O(n) → O(log n), best with Comparable keys. With random hashes at load 0.75 a bin of 8 has odds 6×10-8 — a tree bin means a bad hashCode or an attack.
  • Cost of seeding: hashValue and iteration order change per launch — Swift also reseeds per table, so two equal Sets may iterate differently. SWIFT_DETERMINISTIC_HASHING=1 / PYTHONHASHSEED=0 pin it for tests.

Birthday bound

n items in m values collide with P ≈1 - e-n2/2m, 50 % at n ≈1.18√(m). 23 people → 50.7 %; 64-bit hash → ∼5×109 items; UUIDv4 (122 random bits) → 2.71×1018 (1 in 109 within 103 trillion). So an n-bit hash gives only n/2 bits of collision resistance.

Growth

Past the load limit: allocate (Java: double), re-insert all — O(n) once, O(1) amortised, a latency spike. Redis keeps two tables and moves buckets a step per operation; Go caps a table at 1024 entries, so the worst insert copies 1024.

Consistent hashing

  • hash(key) mod N: change N and nearly every key moves. The ring (Karger et al., STOC 1997) moves only ∼keys/slots on average.
  • Virtual nodes: many tokens per server even out load; a dead node’s load spreads over many others; more tokens = bigger share (weight). Each token adds up to 2 (RF-1) neighbours: Cassandra 2.x needed 256 random tokens, 3.x+ allocates them deterministically — default num_tokens: 16.
  • Rendezvous / highest random weight (Thaler & Ravishankar 1996): key → the node with the largest h(key, node); O(nodes) per lookup, no ring.
  • Jump hash (Lamping & Veach 2014): ∼5 lines, no storage, more even than the ring — but buckets must be numbered 0…n-1: shards, not web caches.

Bloom filter

p ≈(1-e-kn/m)k, best k = (m/n)ln2, so m/n = 1.44log2(1/p): 1 % ≈ 9.6 bits per item, k = 7; every +4.8 bits/item cuts p 10×. No false negatives, no delete (counting variant can). LevelDB at 10 bits/key: ∼100× fewer needless disk reads per Get; Akamai keeps one-hit wonders out of its disk caches.

Cryptographic hashes

functionblock / statecollisionpreimage2nd preimage
SHA-1512-bit block<80160160 - L(M)
SHA-256512, 64 rounds128256256 - L(M)
SHA-5121024, 80 rounds256512512 - L(M)
SHA-512/2561024, truncated128256256
SHA3-256sponge, r 1088 + c 512128256256

Strength in bits (NIST). L(M) = log2 of the message length in blocks: long messages ease second preimages on Merkle–Damgård (Kelsey–Schneier).

Hashing — tables, crypto, rings, passwords, Bloom — figure 2

Length extension: SHA-256’s digest is its final chaining state, so from H(k ‖m) and the length anyone continues the chain. SHA-3 and BLAKE3 resist it. Broken: MD5 collisions in ≤10 s on a Pentium 4 (2007) — never for signatures; SHA-1 SHAttered (CWI + Google, Feb 2017): two different PDFs, one SHA-1, 263 computations, >100 000× faster than brute force. NIST: SHA-1 out by 31 Dec 2030.

MAC: HMAC vs a plain hash

A plain hash only catches accidents — anyone can recompute it. HMAC (RFC 2104) = H((K ⊕opad) ‖H((K ⊕ipad) ‖m)), ipad = 0x36, opad = 0x5C repeated to the block size (64 B for SHA-256); longer keys are hashed first, keys shorter than the output are discouraged. The nesting defeats length extension. SHA-3 (KMAC), BLAKE2 and BLAKE3 take the key directly. swift-crypto (the open CryptoKit API) compares MACs in constant time in both == and isValidAuthenticationCode.

Password hashing — slow on purpose

functionOWASP minimum (2026)role
Argon2id19 MiB, t=2, p=1 — or 46/1, 12/3, 9/4, 7/5 (MiB/t)first choice; PHC winner 2015
scryptN=217 (128 MiB), r=8, p=1no Argon2id
bcryptcost ≥10; input ≤72 byteslegacy only
PBKDF2HMAC-SHA256 600 000 · -SHA512 220 000 · -SHA1 1 400 000 (legacy)FIPS-140

RFC 9106 aims higher: Argon2id t=1, p=4, 2 GiB, or t=3, p=4, 64 MiB where memory is short; 16-byte salt. Argon2id = Argon2i (side-channel safe) for half the first pass, Argon2d after. Salt: unique, stored — one hash cracked at a time, no rainbow tables, equal passwords differ. Pepper: one secret outside the DB — a DB-only leak (SQL injection, a backup) stays uncrackable; rotating it forces resets.

Traps

  • Persisting hashValue — use SHA-256 for a stable key.
  • Fast hash for passwords (SHA-256, salted or not). bcrypt over a raw digest: a 0x00 byte truncates it, and leaked hashes can be “shucked” — base64(HMAC(pepper, pw)).
  • H(key ‖msg) with SHA-2 as a MAC — length extension.
  • “A 256-bit hash = 256-bit collision strength” — it is 128.

Remember

Tables: fast + seeded. Integrity: SHA-256 / SHA-3. Authenticity: HMAC. Passwords: Argon2id + salt. Membership at scale: Bloom. Collision strength = half the bits.

Report a problem ·Discuss this folio