Hashes and checksums
A hash turns any amount of data into a short fixed-size fingerprint. Everything from a download's integrity check to git to Bitcoin is a different answer to the question of what that fingerprint should promise.
1. Six functions, one input
These are all "hashes" in the loose sense: they map an input of any length to a fixed number of bits. They differ enormously in what they guarantee. The first four are checksums, built to catch accidents. The last two are cryptographic hashes, built to survive an adversary.
| Function | Value (changed characters highlighted) | Bits flipped |
|---|---|---|
| Byte sum 8-bit checksum | … | |
| XOR 8-bit checksum | … | |
| Adler-32 32-bit checksum | … | |
| CRC-32 32-bit checksum | … | |
| SHA-1 160-bit hash | … | |
| SHA-256 256-bit hash | … |
Change one letter. The checksums move a little and predictably; SHA-256 flips about half its 256 bits, and which half is unguessable. That property, called the avalanche effect, is what makes a hash usable as a fingerprint.
A checksum's changes are small and structured because the function is simple arithmetic: a sum moves by the difference of the bytes you changed. A cryptographic hash is designed so that no such relationship exists. If you know the hash of one message, you know nothing about the hash of any other, even one that differs by a single bit.
2. Checksums catch accidents, not attackers
A byte sum is what a 1970s serial protocol used, and the demo shows why nobody does now: reorder the bytes and it does not notice. CRC-32 is the fix that most file formats settled on. It treats the message as a giant binary number, divides it by a fixed 33-bit polynomial, and keeps the remainder. Division depends on where each bit sits, so a CRC catches any reordering, any single flipped bit, and every burst of errors shorter than 32 bits. Ethernet frames, zip entries and PNG chunks all carry one.
| Function | Original | Swapped |
|---|---|---|
| Byte sum | … | … |
| XOR | … | … |
| Adler-32 | … | … |
| CRC-32 | … | … |
A sum is a sum whatever the order, so the two cheapest checksums cannot tell these apart. Adler-32 and CRC-32 can, because their arithmetic depends on position. That is why a real file format never uses a plain byte sum.
But a CRC is linear. Given a message and its CRC, working out which bytes to change so the CRC still matches is a small exercise in algebra, not a search. That is fine when the enemy is cosmic rays and useless when the enemy is a person. This is the line between a checksum and a hash: a checksum promises to notice noise, a hash promises to notice intent.
3. The check digit in your wallet
Card numbers carry the smallest checksum of all: one digit. The Luhn algorithm doubles every second digit from the right, adds them up, and requires the total to end in zero. It exists so a form can reject a typo before a network round trip, and it was designed for exactly two mistakes: one wrong digit, or two neighbours transposed.
Passes Luhn. A form would accept this before ever contacting a bank.
Change any one digit, or swap two neighbours: it fails. Swap two digits that are not neighbours and it may well still pass. Luhn was designed in 1954 for the mistakes hands make, not the ones adversaries make.
4. One-way, but only if there is somewhere to hide
A cryptographic hash is one-way: from the output there is no path back to the input. Websites use this to store passwords, keeping the hash instead of the secret. But one-way is not the same as unguessable. If the input came from a small set, the attacker does not reverse the hash. They hash every candidate and compare.
- SHA-256 of the PIN: this is all an attacker gets
- enter four digits
Two defences, and they are different. A salt, random bytes mixed into each password before hashing, stops one precomputed table cracking every account at once. A slow hash like PBKDF2, bcrypt or Argon2 makes each guess cost real time, so a small input space becomes an expensive one. Neither makes a four-digit PIN safe, which is why your phone also wipes itself after ten tries.
This site hashes one thing about you: your IP address, which the leaderboard and the party rooms keep to rate limit requests. Counting requests from one place only needs to know that two of them match, never where they came from, so a hash looks like the right tool. On its own it is not. An IPv4 address is a 32-bit number, a PIN with ten digits instead of four. There are about 4.3 billion of them, and one graphics card can hash every one in under a second, so a plain SHA-256 of an address hides nothing from anyone holding a copy of the database.
Neither defence above helps. A salt would have to be shared by every row, or two requests from one address would never match, and a shared salt sits in the same database as the hashes. A hash slow enough to make 4.3 billion guesses expensive would be too slow to run on every request. What works is a key. The site stores an HMAC of your address: a hash mixed with a long random secret that lives in the server's configuration, never in the database. Without the secret an attacker cannot hash their guesses, so there is nothing to compare against. The addresses are still a small set, but every guess now needs the secret too, and the secret has somewhere to hide. The key also changes every day, so the same address hashes differently tomorrow and one day's rows cannot be matched to the next. Hashes more than a day old are cleared out as new ones arrive.
5. Chaining hashes: git and blockchains
Put the previous block's hash inside the next block before hashing it, and you have a structure where changing anything in the past changes every fingerprint after it. A git commit id is the hash of the commit, which includes the hash of its parent, which includes the hash of its parent, all the way back. That is why you cannot quietly edit an old commit: every id downstream changes, and everyone who has a copy sees the mismatch. A blockchain is the same structure with a rule that makes recomputing each block expensive, so redoing history costs more than the history is worth.
Edit block 1. Its hash no longer matches, and every block after it now rests on a hash that describes nothing. Fixing block 1 alone just moves the break to block 2. To make an edit stick you must redo every later block, and in git that means every commit id after it changes, which is exactly how everyone else notices.
Which one, when
- Detecting corruption in transit or storage: CRC-32. Cheap, and exactly built for it.
- Fingerprinting a file so two parties can confirm they have the same one: SHA-256. SHA-1 is broken for this: two different files with the same SHA-1 have been published.
- Storing a password: not a hash at all in the plain sense. A salted, slow, memory-hard function: Argon2id, or bcrypt if that is what you have.
- Matching a value from a small set, like an IP address or a phone number, without storing it: an HMAC, with the key kept apart from the data. A plain hash of it can be undone by hashing every candidate.
- Proving a message came from you: a hash on its own proves nothing about origin. You need a signature, or an HMAC if you share a secret. See the encryption page.