SHA & HMAC, hand-cranked

That last property is the most interesting cryptographically. The output space of SHA-256 is 2256 values; the input space is infinite, so collisions must exist. The guarantee is just that you can't find one — even with arbitrary computational resources by today's standards.

The bound isn't 2256 tries, though. By the birthday paradox, you only need ~2n/2 tries to find a collision in an n-bit hash. So SHA-256's collision resistance is really 128 bits of work — which is still far beyond reach, but it's why nobody seriously proposes a 128-bit cryptographic hash.

We'll find a real collision in a truncated SHA-256 below. With 24 bits of output, the birthday-attack expected work is just 212 = 4096 tries — a fraction of a second.

SHA-256 reads a message in 512-bit (64-byte) blocks and threads a 256-bit state through them. The structure is Merkle-Damgård: an initial hash H₀, a compression function C(state, block) → state, and a final output. The compression function is where all the cryptographic action happens.

SHA-3 isn't a faster SHA-2. It's a totally different construction designed as a hedge: if anyone ever found a flaw in Merkle-Damgård, the world would have a fallback that doesn't share the same mathematical structure.

Instead of a small state threaded through compression rounds, SHA-3 uses a giant sponge: a 1600-bit state that absorbs message blocks by XOR'ing them in, then squeezes hash output bits out, with a permutation applied between operations. The state is organized as a 5×5×64 cube; the permutation does five things (theta, rho, pi, chi, iota) for 24 rounds.

For SHA3-256 specifically, the rate is 1088 bits (136 bytes) and the capacity is 512 bits. Each message block is 136 bytes; the permutation runs after each absorb. To produce 256 bits of output, a single squeeze of the rate is enough.

A consequence of the structure: SHA-3 is naturally extensible. The same primitive supports arbitrary output lengths (SHAKE-128, SHAKE-256) just by squeezing more bits, with extra permutations in between. ML-KEM and ML-DSA use SHAKE internally as their pseudo-random generator — which is why post-quantum cryptography quietly depends on SHA-3 even though it wasn't strictly required to.

Performance-wise, SHA-3 in software is somewhat slower than SHA-256. In hardware (where Keccak's bitwise structure shines), the gap narrows. For most applications, SHA-256 remains the practical default; SHA-3 is the strategic backup.

A plain hash is unkeyed: anyone can compute it, anyone can verify it. That's useless for authentication — a man-in-the-middle could rewrite a message and recompute the hash. HMAC adds a secret key to a hash, producing an authenticator that only someone with the key can generate or verify.

The construction is bizarrely simple: hash the message twice, with a key XOR'd against two different fixed pads. That's it. The cleverness is in why it's secure — the double-hash structure is what saves it from length-extension attacks that affect plain SHA-256(key || message).

The birthday paradox: in a room of 23 people, there's a 50% chance two share a birthday. The math: with N possible birthdays and k people, the probability of a collision is ~k²/2N. Set that to 0.5 and you get k ≈ √N = √365 ≈ 19 for actual birthdays (closer to 23 once you account for higher-order terms).

For an n-bit hash function, N = 2n, so you find a collision after roughly 2n/2 tries — not the 2n you might naively expect. That's why a 128-bit hash gives only 64 bits of collision resistance.

Below: real SHA-256, truncated to whatever bit length you choose. Click Find collision and watch the simulator hash random inputs until two of them produce the same truncated digest.