Why a hash can't be run backwards

A hash function takes a message of any length and returns a short, fixed-size string of bits called a digest. Given the message, the digest is quick to compute. Given only the digest, nobody knows how to get the message back — a statement about what people can do, not a theorem.

A fingerprint for data

The Secure Hash Standard, FIPS 180-4, specifies seven such functions — SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 and SHA-512/256 — "for computing a condensed representation of electronic data". The input can be any message shorter than 2⁶⁴ bits for the first three, or 2¹²⁸ bits for the rest; the output, the message digest, is 160 to 512 bits depending on the algorithm. The widget below runs SHA-256 in your browser and measures the digest: 256 bits, every time.

Why it matters

The standard's abstract gives the job in one line: digests "are used to detect whether messages have been changed since the digests were generated." Store a file's digest and later you can check the file without keeping a second copy. The standard also lists what the functions are built into — digital signatures, keyed-hash message authentication codes, random-number generation. All lean on the same two properties, and the standard states both as a matter of computational cost.

How the digest is made

The standard lays the computation out in stages. First the message is padded with extra bits so its length fits the algorithm's block structure. Then it is parsed — cut into blocks. A hash value is set to a fixed starting constant, which the standard writes H⁽⁰⁾. Then, for each block, a fixed sequence of word-level operations — the standard's "functions and constants" — mixes it into the current hash value to produce the next. Each block's result depends on the block before. After the last block, the current hash value is the digest.

Two things follow, and each deserves honest statement.

First, collisions exist. SHA-256 has 2²⁵⁶ possible outputs but accepts inputs of almost any length, so there are vastly more messages than digests. Some different messages must share a digest; that is counting, not cryptography. The standard promises something weaker and more useful: it calls the algorithms secure because "it is computationally infeasible … to find two different messages that produce the same message digest." The collisions are there. Finding one is meant to be out of reach.

Second, the digest is not reversible in practice. The same sentence in the standard makes it "computationally infeasible … to find a message that corresponds to a given message digest." Note the word. It does not say impossible, and there is no proof that a shortcut cannot exist. Padding, parsing, and mixing are fully specified and public; the difficulty is that nobody knows a way to undo the mixing faster than guessing messages and hashing forward. The standard adds that "any change to a message will, with a very high probability, result in a different message digest." It does not say how different. That is what the widget is for: flip one bit of your message and count how many output bits move. The standard defines what SHA-256 is; the count is yours to observe.

In short

A hash pads a message, cuts it into blocks, and feeds each through the same fixed mixing steps, carrying a running value along until a fixed-size digest is left. Many messages share every digest, because there are more messages than digests, so the standard promises only that finding two is computationally infeasible. Running the digest backwards is, by the same standard, infeasible rather than impossible — a statement about the best known methods, which is why the wording is careful.