The fingerprint of everything.

A three hundred page contract, an X ray, an entire film: any sequence of bytes can be reduced to 32 bytes that represent it with no practical ambiguity. That reduction is the work of a hash function, the most heavily used and least visible component of every digital signature. Nobody signs a document; what gets signed is its hash. If the hash fails, everything else fails with it, however solid the key may be.

This article covers what a hash function is, what it must withstand, how SHA 256 is built on the inside, why SHA 3 is so different, and how MD5 and SHA 1 fell. Two labs let you watch the theory at work in your browser.

A function you cannot run backwards

Formally, a cryptographic hash function is a function H that takes an input of any length and returns an output of fixed length, n bits. It must be deterministic (the same input always yields the same output) and fast to compute. So far, any checksum would qualify. What makes it cryptographic is what must not be possible to do with it.

One point is worth stressing, because it sometimes surprises people: collisions exist, and in unimaginable numbers. There are infinitely many possible inputs and only 2²⁵⁶ outputs, so by the pigeonhole principle infinitely many messages share every hash. Security does not mean that there are no collisions; it means that nobody can find one.

The three resistances

• Preimage resistance. Given a hash y, it must be infeasible to find any x such that H(x) = y. This is the “one way” property. The generic cost is on the order of 2ⁿ attempts.
• Second preimage resistance. Given a specific message x, it must be infeasible to find a different x′ with the same hash. This is what prevents an already signed document from being swapped for another. Generic cost: 2ⁿ.
• Collision resistance. It must be infeasible to find any pair of distinct messages with the same hash. It looks like a weaker requirement than the previous one, because the attacker chooses both messages, and that is precisely why it is easier to attack: the generic cost drops to 2^n/2.

That halving of the exponent is the birthday paradox. In a group of 23 people, the probability that two share a birthday already exceeds 50%, even though the year has 365 days. With N possible values and k random attempts, the probability of at least one match is approximately:

A good hash function also exhibits a behavior that does not appear in the formal definitions but is expected of it all the same: the avalanche effect. Flipping a single input bit should change, on average, half of the output bits, with no apparent pattern. It is easy to check.

Inside SHA 256

SHA 256 belongs to the SHA 2 family, introduced by NIST in 2001 and specified today in FIPS 180 4. Its architecture is that of Merkle and Damgård, who proposed it independently in 1989: a compression function that processes fixed size blocks and is chained. If the compression function resists collisions, so does the full hash. That theorem is the reason the entire design effort is concentrated on one small component.

1. Padding. A 1 bit is appended to the message, then zeros, and finally its original length in bits, encoded in 64 bits. The result has a length that is a multiple of 512 bits. Including the length (Merkle and Damgård “strengthening”) rules out certain trivial collisions between messages of different lengths.
2. Blocks. The padded message is split into 512 bit blocks, that is, sixteen 32 bit words.
3. Initial state. Eight 32 bit words, a through h, taken from the fractional parts of the square roots of the first eight primes.
4. Compression. Each block is mixed with the state over 64 rounds. At the end, the result is added to the input state, and that becomes the new state.
5. Output. After the last block, the eight words concatenated form the 256 bit hash.

Only a handful of operations take part in each round, all on 32 bit words: rotations (ROTR), shifts (SHR), exclusive OR (⊕), logical AND (∧), negation (¬) and addition modulo 2³². Combined, they produce functions that are not linear over any convenient algebraic structure, which is exactly the goal.

The 64 constants K_t are the first 32 bits of the fractional parts of the cube roots of the first 64 primes. Choosing them this way is no whim: they are “nothing up my sleeve numbers” that anyone can recompute, and which therefore cannot hide a backdoor chosen by the designer. The words W_t are the sixteen words of the block, expanded to 64 through two further rotation mixes, σ0 and σ1.

The final addition of the input state, known as the Davies and Meyer construction, is what makes the compression irreversible. Without it, anyone who knew the block could undo the rounds one by one. The next lab shows the complete process for whatever message you type: the padding byte by byte, each of the 64 rounds and the final addition. With “abc”, the result matches the first test vector in the standard.

The Achilles’ heel: extending without knowing

The Merkle and Damgård construction has an awkward property. The hash it outputs is the complete internal state after the last block. Anyone who knows H(s ‖ m) and the length of s ‖ m, even without knowing the secret s, can resume the computation from that state and obtain H(s ‖ m ‖ padding ‖ m′) for any suffix m′ they like. This is the length extension attack.

It does not affect digital signatures, which never use a secret concatenated in this way, but it does affect anyone who builds naive authenticators of the “hash of key plus message” kind. The standard answer is HMAC, which nests two applications of the function. Truncated variants such as SHA 512/256, and the SHA 3 family, are immune by design, because they do not expose the whole state.

SHA 3: the sponge

When theoretical attacks against SHA 1 appeared in 2005, NIST feared that the same family of ideas might reach SHA 2, which shares its architecture. In 2007 it launched a public competition. There were 64 submissions, 51 advanced to the first round, and in 2012 Keccak, by Bertoni, Daemen, Peeters and Van Assche, won. FIPS 202 standardized it in 2015 as SHA 3.

Keccak does not use chained compression but a sponge construction. It has a 1600 bit state, organized as a 5 × 5 × 64 cube, split into two parts: the rate r, which comes into contact with the data, and the capacity c, which is never touched from outside.

1. Absorbing. Each r bit block of the message is combined by exclusive OR into the rate portion, and the full permutation is applied: 24 rounds of five steps called θ, ρ, π, χ and ι.
2. Squeezing. Once the input is consumed, r bits of the rate are read out as output; if more are needed, the state is permuted again and reading continues.

Generic security is determined by the capacity: c/2 bits. SHA3 256 uses r = 1088 and c = 512. Since the output never reveals the capacity, there is no length extension. And since the permutation bears no resemblance to the SHA 2 compression function, progress against one does not carry over to the other. SHA 3 did not come to replace SHA 2, which remains healthy, but to give it an independently designed alternative.

How MD5 and SHA 1 fell

The history of hash functions teaches that they do not break overnight. They crack first in theory, then in the lab and finally in practice, and between each stage there are usually years, enough time to migrate if they are put to good use.

The difference between the two kinds of collision is decisive. In an identical prefix collision, the two messages share the same beginning and differ only in a few blocks computed by the attacker; exploiting it requires hiding that difference inside a format that interprets it, as SHAttered did with images inside PDFs. In a chosen prefix collision, the attacker starts from two arbitrary, different beginnings, for example two certificates with different subjects, and computes suffixes that make the hashes equal. It is far more expensive and far more dangerous, because it allows forging exactly what the attacker wants.

What to use, and for how long

For digital signatures, SHA 256 is today the default choice, and SHA 384 or SHA 512 are preferable when the signature must hold up for many years or accompany keys at a higher security level. SHA3 256 and SHA3 512 are equally valid alternatives. MD5 and SHA 1 must not be used for new signatures, and in old documents they can only be relied upon if a later timestamp, made with strong algorithms, proves that the documents existed before forging them became possible.

And quantum computing? Grover’s algorithm reduces the cost of finding a preimage from 2ⁿ to about 2^n/2 evaluations, and the best quantum collision algorithms offer no practical improvement over the classical one because of their memory requirements. With 256 bits of output, the margin remains wide. Unlike RSA and elliptic curves, well designed hash functions survive quantum computing with, at most, longer outputs.

← All notes