Level 3 · How it worksThe village#177

Hash functions explained: a seal is only as good as its length

A hash function turns any data into a fixed-size fingerprint. A good one makes it practically impossible to go back from the fingerprint, or to find two different inputs with the same one. That second promise is harder to keep, and it's why SHA-1 was retired while SHA-256 secures Bitcoin.

Every page in the village notebook gets a wax seal, pressed from the page itself. Ben has given up trying to change a page without changing its seal. Too obvious. So he has a quieter plan.

He'll write two different pages that happen to make the same seal. One says he owes Anna 10 coins, the other says 1. He gets the first one sealed and agreed, then swaps in the second. Same seal, different debt. Nobody would notice.

Whether Ben's plan can work depends on one thing: how long the seal is. Make it short and he wins in an afternoon. Make it long enough and no computer on earth finishes the job.

What it is

A hash function is a fixed recipe that turns any input, a word or a whole block, into an output of fixed size, called a hash or digest. NIST's standard says what it's for: "to detect whether messages have been changed" (NIST FIPS 180-4).

A good one makes two things "computationally infeasible": finding an input that matches a given hash, and finding "two different messages that produce the same message digest" (NIST FIPS 180-4). The second is called collision resistance. It is the one Ben is after, and the one that breaks first.

How it works: Ben's two pages, with a short seal

Here are three inputs and their SHA-256 hashes, first 16 characters only. You can reproduce them with any SHA-256 tool.

  • "Rosa's jam: 12 jars" gives 0df96418c32d5ab2...
  • "Rosa's jam: 13 jars" gives a2a65b21ca744734...
  • "Rosa's Jam: 12 jars", one capital letter, gives 52c838559a687b3d...

Same input, same hash, every time. Any change, a completely different one. Now Ben's plan.

  1. Shorten the seal. Suppose the village only kept the first 8 characters of each SHA-256 hash. That's 32 bits, about 4.3 billion possible seals.
  2. Write pages and compare. We hashed "Page 0", "Page 1", "Page 2" and so on, and kept a list of every 8-character seal. On page 28,427, the input "Page 28426", the seal 5d1e2587 turned up for the second time. Its twin was "Page 11882". Two different pages, one short seal. A laptop found it in under a second.
  3. Notice the shortcut. Ben didn't need 4.3 billion tries. He needed about 28,000. When you're looking for any two pages that match, not a match for one particular page, the odds pile up fast. It's the same effect that makes two people in a room of 23 more likely than not to share a birthday.
  4. Lengthen the seal. NIST puts this in one sentence: "The expected collision-resistance strength of a hash function is half the length of the hash value" (NIST SP 800-107r1). For full SHA-256, 256 bits long, that means 128 bits of collision strength. Ben's afternoon becomes 2 to the power of 128 tries: a number with 39 digits.

That's why seal length matters more than anything else on this page. Halve the length you think you have, and that's what the forger is really up against.

Why it matters

Ben's trick isn't theoretical. On 23 February 2017, Google and the CWI institute in Amsterdam published "two PDFs that have identical SHA-1 hashes but different content". It took "nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total", and was "more than 100,000 times faster than a brute force attack" (Google Security Blog, 2017). SHA-1's seal is 160 bits, and NIST rates its collision strength at less than 80 bits (NIST SP 800-107r1).

On 15 December 2022, NIST announced that SHA-1 should be phased out by 31 December 2030, and recommended that anyone relying on it "migrate to SHA-2 or SHA-3 as soon as possible" (NIST, 2022). SHA-2 is the family that includes SHA-256. SHA-3, published as FIPS 202 in August 2015, is based on a different design called Keccak (NIST FIPS 202).

Bitcoin uses SHA-256 everywhere a seal is needed. Block headers and the rows of transaction hashes that lead to the Merkle root are hashed with "SHA256(SHA256())", SHA-256 applied twice (Bitcoin developer reference). Who gains: everyone who checks the notebook. Who pays: a forger, who would need a collision in a hash that NIST rates at 128 bits of collision strength.

Where people get it wrong

  • "Collisions don't exist for good hashes." They must exist: infinitely many inputs, a fixed number of outputs. A good hash only makes them impossible to find in practice.
  • "256 bits means 256 bits of protection." Against collisions, half: 128 bits, per NIST. Still far beyond reach, but the halving is why short seals die young.
  • "SHA-1 broken means Bitcoin is next." Different recipe, and a longer seal: 256 bits against SHA-1's 160. Bitcoin's proof of work and block chain use SHA-256.
  • "Any checksum is a hash function." A checksum catches typos. A cryptographic hash also has to survive someone like Ben trying on purpose.

Check which seal you're trusting

When software, a wallet app or a document comes with a published hash for you to check, look at the name next to it. SHA-256 or SHA-3: fine. MD5 or SHA-1: that seal no longer proves nobody swapped the page, only that nobody tried very hard.

Ben's plan works perfectly against an 8-character seal: 28,427 pages and one second. Against 64 characters he needs around 2 to the power of 128 pages, and he is going to run out of village first. Good luck, Ben.

Frequently asked questions

What is a hash function?

A hash function is a fixed recipe that turns any input into an output of a fixed size, called a hash or digest. The same input always gives the same hash, and any change gives a completely different one. Cryptographic hash functions such as SHA-256 are also designed so the input can't be worked out from the hash.

What is a hash collision?

A collision is two different inputs that produce the same hash. They always exist in theory, because there are more possible inputs than outputs. A secure hash function makes finding one computationally infeasible.

Why was SHA-1 retired?

In February 2017, Google and CWI published two different PDF files with the same SHA-1 hash, a practical collision. NIST announced in December 2022 that SHA-1 should be phased out by 31 December 2030 and replaced with SHA-2 or SHA-3.

How secure is SHA-256 against collisions?

NIST rates SHA-256's collision resistance at 128 bits, half its 256-bit output length. That means an attacker would need around 2 to the power of 128 attempts, which is far beyond any known computing power.

Which hash function does Bitcoin use?

Bitcoin uses SHA-256, applied twice, for block headers, the Merkle tree of transactions and proof of work. SHA-256 is part of the SHA-2 family defined by NIST in FIPS 180-4.

Sources

  1. NIST, FIPS 180-4 Secure Hash Standard (August 2015)
  2. NIST, SP 800-107 Revision 1, Recommendation for applications using approved hash algorithms (August 2012)
  3. Google Security Blog, Announcing the first SHA1 collision (23 February 2017)
  4. NIST, NIST retires SHA-1 cryptographic algorithm (15 December 2022)
  5. NIST, FIPS 202 SHA-3 Standard (August 2015)
  6. Bitcoin developer reference, Block chain

Read next.