Hash functions
How does a website know your password is correct without knowing your password? How does your phone notice that a downloaded file got damaged along the way? Both times with the same trick: a fingerprint of the data. Small, always the same size, and unique to whatever went in.
Words you might need
- Hash (or hash function)
- A calculator that you give something — a word, a photo, a whole book — and that always turns it into a string of characters of the same length. The same input always gives the same output. A different input, even just one letter, gives a completely different output.
- Bit
- The smallest piece of information: a 0 or a 1. Eight bits make a byte. If something is "256 bits", that's 256 zeros and ones in a row.
- SHA-256
- The name of the hash function most used today. The 256 is the number of bits in the output: always exactly 256, whether you feed in one letter or a whole movie. In hexadecimal that's 64 characters.
- Algorithm
- A fixed recipe of calculation steps. SHA-256, SHA-1 and MD5 are three different recipes with the same goal.
- Hexadecimal
- You know it from chapter 1: writing down bytes with the digits 0–9 and the letters a–f, two characters per byte. So every hex character stands for four bits. That's how a hash is shown below — and it isn't used for anything else.
Three rules a hash sticks to
| Rule | What it means |
|---|---|
| One-way traffic | You can't calculate the input back from the hash. Not "hard", not "possible with a fast enough computer" — there simply is no way back. Like you can't get the cow back from a ground beef patty. |
| No collisions | Two different inputs shouldn't get the same hash. In theory it could happen (there are infinitely many texts and only 2256 hashes), but no one manages to find one. |
| Avalanche effect | One letter different, and roughly half of all the bits in the output flip. Nothing is left that resembles the previous hash. |
Try it yourself
Everything happens in your browser. Nothing is sent to the server.
- Click Make the fingerprint. You'll see four hashes of the same sentence, using four different recipes. Notice how long each one is.
- Change one letter in the sentence and click again. Compare. Do you still recognise anything?
- Click Show the avalanche effect: the demo changes one character itself and counts how many bits flip.
- Paste in a really long text — song lyrics, an essay. The hash stays the same length.
What exactly you're looking at
Those rows of characters are not base64. They consist only of 0–9 and a–f, and that's hexadecimal: two characters per byte, four bits per character. Do the maths — 64 characters × 4 = 256 bits, exactly what it says behind SHA-256. For SHA-1 you count 40 characters, so 160 bits.
Why hexadecimal here and base64 in chapter 1? Because here it's about looking. Hexadecimal is longer but you can still follow it: every character is exactly four bits, and you can put two hashes side by side and compare them letter by letter. Base64 is shorter and therefore handier to send, but the boundary between two bytes falls in the middle of a character there. The same bytes, a different way of writing them down — exactly the point of the previous chapter.
Why that length matters
256 bits means 2256 possible outcomes. That's a number with 78 digits. For comparison: the number of atoms in the universe is a number with roughly 80 digits. Every possible text gets a spot in a space as big as the universe — the chance that two different texts accidentally land on the same spot is practically zero.
The lesson you can't see
Look at the SHA-1 line in the demo. It looks exactly as random as SHA-256, just shorter: 160 bits instead of 256, so 40 hex characters instead of 64. Yet SHA-1 is broken: in 2017, researchers from Google and CWI in Amsterdam showed two different PDF files with the exact same SHA-1 hash. The "no collisions" rule had been broken. MD5 had gone down much earlier.
You can't tell any of that from the output. Whether a hash function holds up doesn't depend on how random it looks, but on whether mathematicians have found a weak spot in it. That's why you use SHA-256 today and not something that "also looks fine".
Can you "decrypt" a hash? No. Nothing was encrypted, there's nothing to decrypt. Yet there are websites that claim they can — and sometimes they really do pull it off. How that's possible, and why it matters for your passwords, is the next chapter.
This is math: the birthday paradox
Roll a die. How many rolls before you get a six? Six on average. But how many rolls before you see any number a second time? After four rolls that chance is already 72%. That goes much faster — and it's the same phenomenon as in a classroom: with 23 students, the chance that two share a birthday is over 50%. While there are 365 days.
The trick is in what you're looking for. You're not looking for someone born on your birthday — for that you need over 250 people. You're looking for any two. With 23 students you can form 253 different pairs, and every pair is a chance at a duplicate. That's why "duplicate" arrives so much sooner than your gut says.
| Possibilities | A duplicate is likely after |
|---|---|
| 6 (a die) | 4 rolls |
| 365 (birthdays) | 23 students |
| 1,000,000 | about 1,200 attempts |
| 2256 (SHA-256) | about 2128 attempts |
See the pattern? It's roughly the square root of the number of possibilities every time. With a million possibilities you already have a duplicate after a good thousand attempts — not after half a million.
And now the hash. A hash is the "birthday" of a text: every text gets one, out of 2256 possible ones. A collision — two texts with the same hash — is therefore just two students sharing a birthday. And the table says how many texts you have to try before that probably happens: not 2256, but 2128. A hash is only half as strong as its length suggests.
That's the reason 256 is the standard and not 128. A hash of 128 bits gives a collision after 264 attempts — and all the computers running Bitcoin today work out that many hashes together in less than a second. With 256 bits, 128 are left, and nobody reaches that. This is probability theory: one little sum about dice decides how long every hash in the world has to be.