Hash Functions

Chapter 6 mentioned GCM's authentication tag without explaining how anything like it is actually built. Hash functions are the primitive that makes it possible — and they're a genuinely different tool from everything covered so far: no key in their basic form, and deliberately, permanently not reversible.

What Is a Hash Function?

A cryptographic hash function takes an input of any length — a single character or an entire multi-gigabyte file — and deterministically produces a fixed-length output, called a digest or hash. The same input always produces the same output, but there's no way to run the process backward: given only the digest, there's no operation that recovers the original input.

Hash ≠ Encryption

This is one of the most common mix-ups in casual security conversation — "we encrypted your password" almost always actually means "we hashed it," and the two are fundamentally different operations:

"Decrypting a hash" isn't a meaningful operation at all — there's no key to decrypt it with, and the transformation was never designed to be reversed.

The Three Security Properties

A cryptographically secure hash function needs to resist three distinct kinds of attack:

• Preimage resistance — given only a hash output H, it should be computationally infeasible to find any input that produces H.
• Second-preimage resistance — given a specific input M1, it should be infeasible to find a different input M2 that produces the same hash as M1.
• Collision resistance — it should be infeasible to find any two different inputs M1 and M2 (neither one given in advance) that happen to produce the same hash.

Collision resistance is strictly the hardest of the three to achieve — and, thanks to a genuinely counterintuitive piece of probability, it needs considerably more output bits than the other two properties to hold up.

The Birthday Paradox & Why Collision Resistance Needs More Bits

The "birthday paradox" observes that in a room of just 23 people, there's already a better-than-even chance two of them share a birthday — far fewer people than the 366 you might naively expect, because you're comparing every pair of people against each other, not just one person against everyone else.

The same math applies to hash collisions. Finding a specific preimage for an n-bit hash takes roughly 2ⁿ attempts on average. But finding any collision at all — any two inputs that happen to match — takes only about 2ⁿ/² attempts, because every new attempt is being checked against every previous attempt, not just one fixed target.

The Avalanche Effect

A well-designed hash function exhibits the avalanche effect: changing even a single bit of the input should completely and unpredictably change the output digest, with roughly half of the output bits flipping on average. Two near-identical inputs should never produce even remotely similar-looking hashes — this is the same underlying idea Chapter 5 introduced for AES's MixColumns step, now the defining property of an entire class of primitive.

MD5 — Broken

Designed in 1992 with a 128-bit output, MD5 was for years the internet's default hash function. Its 128-bit output already gives only ~2⁶⁴ collision resistance per the birthday paradox above — a real weak point even before anything else went wrong. In 2004, researchers (Wang et al.) demonstrated practical collision attacks, dramatically faster than the theoretical 2⁶⁴ figure, exploiting real structural weaknesses in MD5's design. The consequences were not theoretical: the 2012 Flame malware used a forged MD5 collision to fake a legitimate Microsoft code-signing certificate. MD5 is still sometimes used for non-security checksums (verifying a file wasn't corrupted in transit) but must never be used anywhere security depends on it.

SHA-1 — Also Broken

Designed in 1995 with a 160-bit output, SHA-1 became the internet's next default — used for years in TLS certificates, and still used today inside Git for commit hashing (a non-security use, more on that distinction shortly). In 2017, Google and CWI Amsterdam publicly demonstrated SHAttered, a practical SHA-1 collision, using an approach echoing MD5's own 2004 break. Browsers and certificate authorities deprecated SHA-1 for TLS certificates around the same time.

SHA-2 — The Current Workhorse

Published in 2001, SHA-2 is actually a family of functions — SHA-256, SHA-384, SHA-512, named for their output size in bits. Despite being designed by the NSA (a detail that draws periodic suspicion), SHA-2 has been public and openly scrutinized for over two decades, per Chapter 1's Kerckhoffs's Principle, with no practical attack ever found. It remains the dominant hash function in TLS, Bitcoin, and countless other systems today.

SHA-3 — A Structurally Different Backup

MD5, SHA-1, and SHA-2 all share the same underlying internal design, called the Merkle-Damgård construction. SHA-3, standardized by NIST in 2015 after another open public competition (again mirroring the AES competition from Chapter 5), uses a completely different internal design called the sponge construction, based on an algorithm called Keccak. SHA-3 isn't a replacement for SHA-2 — SHA-2 remains fully secure — it exists specifically as a structural hedge: if some future breakthrough attack targets a weakness shared by the Merkle-Damgård construction itself, SHA-3's genuinely different internals wouldn't be affected the same way.

What Hash Functions Are Actually Used For

• Integrity verification — confirming a downloaded file or received message wasn't altered, by comparing hashes.
• Digital signatures — signing algorithms (Chapter 10) actually sign a message's hash, not the raw message itself, since hashes are small and fixed-size regardless of the original message's length.
• Content addressing — Git identifies every commit by its hash; blockchain systems chain blocks together the same way.
• Password storage — with an important, easily-missed caveat below.

Hands-On Exercises