Section 5: Hashing

A cryptographic hash function is the workhorse of modern security. It takes an input of any length — one byte, a 4 GB disk image, the collected works of Shakespeare — and produces a fixed-length output called a digest: 256 bits for SHA-256, 512 bits for SHA-512. Three properties make it useful:

• Deterministic — the same input always produces the same digest, on any machine, forever.
• Fast — SHA-256 runs at several gigabytes per second on modern hardware (and even faster with the SHA-NI CPU instructions).
• One-way — given a digest, there is no better way to find an input that produces it than brute-force guessing.

That combination shows up everywhere: integrity checks (download a file, compare its SHA-256 against the published value), deduplication (backup systems store one copy of identical blocks by comparing hashes), git (every commit ID is a hash of its content and its parents, which is why history cannot be silently rewritten), password storage (servers store a hash, never the password itself), and digital signatures (you sign the 32-byte hash of a document, not the megabyte document — so the security of the signature rests entirely on the hash).

Try it: live hash playground

Do this now: add a single period to the end of the sentence and watch the digest. Every hex character scrambles. This is the avalanche effect: a one-bit change in the input flips, on average, half of the output bits. Without it, similar inputs would have similar hashes and an attacker could home in on a target digest incrementally. The demo below shows two inputs differing by exactly one character:

The three security properties

"One-way" is really three distinct properties, and confusing them is the most common hashing mistake:

1. Pre-image resistance. Given a digest h, it is infeasible to find any message m with hash(m) = h. This is what protects hashed passwords: the attacker has the digest and wants an input.
2. Second pre-image resistance. Given a specific message m1, it is infeasible to find a different m2 with hash(m2) = hash(m1). This protects a signed document from being swapped for a forgery with the same hash.
3. Collision resistance. It is infeasible to find any pair m1 ≠ m2 with hash(m1) = hash(m2). The attacker chooses both messages — a much weaker requirement, which is why collisions always fall first.

Why is finding an arbitrary collision so much cheaper? The birthday paradox: in a room of just 23 people there is a better-than-even chance two share a birthday, because what matters is the number of pairs, which grows quadratically. Hash an ever-growing pile of random messages and after roughly 2^(n/2) attempts two of them will collide. So an ideal n-bit hash gives:

This is why a 256-bit hash is said to give "128-bit collision resistance," and why 128-bit hashes like MD5 were doomed on paper from the start: 2⁶⁴ operations were already within reach of well-funded attackers in the 1990s, even before any cryptanalytic shortcut was found.

MD5 and SHA-1: broken

Both of these "died" not with a single blow but a slow collapse — and the gap between "academically broken" and "actually exploited in the wild" was under a decade in each case.

1991  MD5 published (Rivest)
1995  SHA-1 published (NIST)
2004  Wang et al. produce MD5 collisions on a desktop PC
2008  Researchers forge a rogue CA certificate using MD5 collisions
      (200 PlayStation 3s, Sotirov / Stevens et al.)
2012  Flame malware uses a novel MD5 chosen-prefix collision to forge
      a Microsoft code-signing certificate — Windows Update spoofed
2017  SHAttered (Google + CWI): first public SHA-1 collision,
      ~9.2 quintillion SHA-1 computations, two valid PDFs, one hash
2020  SHA-1 chosen-prefix collisions for ~$45,000 of GPU time
      (Leurent and Peyrin) — practical certificate forgery
2030  NIST deadline: SHA-1 disallowed in all US government use
    

The distinction between collision types matters here. A plain (identical-prefix) collision gives the attacker two related blobs with the same hash — bad, but constrained. A chosen-prefix collision lets the attacker pick two arbitrary, different, meaningful prefixes — say, a harmless certificate request and a rogue CA certificate — and compute suffixes that make the hashes match. That is what turned MD5 collisions from a curiosity into the Flame attack: malware that presented a certificate chain Windows accepted as signed by Microsoft, letting it spread via what looked like Windows Update. SHAttered (see shattered.io) did the same for SHA-1 in 2017 — the attack cost about 110 GPU-years, roughly 100,000 times faster than brute force — and by 2020, chosen-prefix SHA-1 collisions cost about the price of a used car.

The SHA-2 family and Merkle–Damgård

SHA-2 (2001) is a family: SHA-224, SHA-256, SHA-384, SHA-512, plus the truncated variants SHA-512/224 and SHA-512/256. SHA-256 does 64 rounds over 32-bit words; SHA-512 does 80 rounds over 64-bit words and is actually faster on 64-bit CPUs. Despite two decades of scrutiny, no attack comes anywhere near breaking full SHA-256 — the best collision attacks reach only 31 of its 64 rounds.

SHA-2, like MD5 and SHA-1 before it, uses the Merkle–Damgård construction: pad the message, split it into fixed-size blocks, and feed the blocks one at a time through a compression function that mixes each block into a running internal state. The final state is the digest.

There is one structural flaw: because the digest is the final internal state, anyone who knows hash(m) and the length of m can pick up where the computation left off and compute hash(m || pad || extra) for any suffix — without knowing m. This is the length-extension attack. It is harmless for file checksums, but fatal if you tried to build an authentication tag as hash(secret || message): an attacker who sees one valid tag can append data and forge a valid tag for the extended message. This single flaw is the reason HMAC exists (below), and it is why SHA-512/256 — which computes SHA-512 internally but outputs only 256 of the 512 state bits — is immune: the attacker never learns the full internal state, so they cannot resume the chain.

SHA-3: the sponge

After SHA-1 fell in 2004–2005, NIST worried that SHA-2 — built from the same Merkle–Damgård design lineage — might fall next, and ran a public competition. The winner (2012, standardized 2015) was Keccak, standardized as SHA-3. It abandons Merkle–Damgård entirely for the sponge construction: a large 1600-bit internal state that absorbs message blocks by XORing them into part of the state and permuting, then squeezes output blocks from the same partial view of the state.

            absorb phase                     squeeze phase
      M1        M2        M3                out1      out2
      |         |         |                  ^         ^
      v XOR     v XOR     v XOR              |         |
 +---------+---------+---------+        +---------+---------+
 | rate r  |  perm   |  perm   |  perm  | rate r  |  perm   |  ...
 |---------|  --->   |  --->   |  --->  |---------|  --->   |
 | cap. c  | (state) | (state) |        | cap. c  | (state) |
 +---------+---------+---------+        +---------+---------+
   only the "rate" part of the state is ever touched by input
   or revealed as output; the "capacity" c stays hidden
    

Because the output reveals only the rate portion and never the hidden capacity bits, SHA-3 is structurally immune to length extension. SHA-3 is not a replacement for SHA-2 — SHA-2 remains unbroken and is usually faster in software — it is an insurance policy: a hash with a completely different internal design, so a breakthrough against one construction cannot take out both.

HMAC: hashing with a key

Suppose a server and client share a secret key K and want to authenticate messages. The naive design tag = SHA-256(K || message) is broken by exactly the length-extension attack above: an intercepted (message, tag) pair lets the attacker forge a valid tag for message || pad || anything, never learning K. The other naive order, SHA-256(message || K), degrades to an offline collision attack on the hash. The fix, standardized in 1997 and still the workhorse today, is HMAC:

HMAC(K, m) = H( (K ⊕ opad)  ||  H( (K ⊕ ipad) || m ) )

  ipad = 0x36 repeated to one block    opad = 0x5c repeated to one block
    

The inner hash binds the key to the message; the outer hash re-processes the inner digest under a differently-masked key, so a length-extension of the inner computation produces garbage after the outer pass. HMAC carries a security proof (it is a PRF as long as the compression function is) and even HMAC-MD5 has never been practically forged — though you should still not use it. You meet HMAC constantly: API request signing (AWS Signature v4), JWTs with the HS256 algorithm, TLS 1.2 record authentication and the TLS 1.3 key schedule (HKDF is built from HMAC), and cookie/session integrity in most web frameworks.

Password hashing: fast is the enemy

Every property that makes SHA-256 great for signatures makes it terrible for passwords. A single consumer GPU computes on the order of 10 billion SHA-256 hashes per second; a cracking rig with eight of them tests every 8-character lowercase password in minutes. When a password database leaks — and they leak constantly — the only thing standing between the attacker and every account is the cost of each guess. Password hashing therefore inverts the usual goal: we want a hash that is deliberately, tunably slow.

Two ingredients:

• Salt — a unique random value stored alongside each hash and mixed into it. Without salts, the attacker hashes each guess once and compares it against every user simultaneously, and can use precomputed rainbow tables. With per-user salts, every account must be attacked individually from scratch.
• Work factor — a tunable cost parameter (iteration count, memory size) that makes each single hash take tens of milliseconds. Irrelevant to a user logging in once; catastrophic to an attacker making billions of guesses. As hardware improves, you turn the knob up.

The modern refinement is memory hardness: GPUs and ASICs get their speed from thousands of cores with little memory each, so an algorithm that forces every evaluation to use tens of megabytes of RAM erases most of the attacker's hardware advantage.

The widget below makes work factors visceral. PBKDF2 is just HMAC iterated N times; watch what happens to the wall-clock time as N climbs from a legacy-era 1,000 to the current OWASP recommendation of 600,000. Now remember the attacker pays that cost per guess, per account.

Check your understanding

Further resources