Encryption, from the ground up · Puzzle 5 · 6 of 9
A fingerprint for data
In puzzle 0, a machine in the middle could change data on its way, and encryption alone wouldn't notice. Here's the block that makes any change visible.
The problem
In puzzle 0, a machine in the middle could do three things. Encryption stopped it reading. But it can still flip bytes in the ciphertext as it passes. The result decrypts to garbage, or to something slightly different, and nothing on the other side checks. How would anyone notice that the data was changed on the way?
See it
Any data, a word or a 10 MB file, goes into a hash function. The standard one is
SHA-256.Step 1 of 4Out comes a short digest, always 256 bits: a fingerprint of the data. Same data, same digest, every time.
Step 2 of 4Flip a single bit of the file, and the digest is completely different. Predict: how does that catch a change on the way?
Step 3 of 4Hash what arrived and compare with the digest you expected. Different: someone changed the data.
Step 4 of 4
The building block
A hash function turns any amount of data, a word or a whole video, into a short number of fixed size: its digest, a fingerprint of the data. The standard one, SHA-256, always produces 256 bits.
Three properties make it useful:
- the same data always gives the same digest;
- change even one bit of the data, and the digest changes beyond recognition;
- given a digest, nobody can construct data that produces it, and nobody can find two different pieces of data with the same digest. Nobody knows a method; trying data at random would take far longer than the age of the universe.
So if you know the digest the data should have, you can check it: hash what arrived, compare. Different digest: something changed it.
There's a catch. If the attacker can change the data, it can also change a digest sent next to it: it hashes its own version and sends that digest instead. A digest helps only if the attacker can't make a matching one.
Two ways close that gap. If both sides already share a secret key, they can mix it into the fingerprint, so only they can make one: that's the next puzzle. Before there's a shared key, puzzle 7 makes a mark that only the real sender can produce.
The analogy
A fingerprint. It's tiny compared to the person, the same every time, different for everyone, and you can't build a person to match a given print. Compare prints, and you know whether it's the same person.
Check yourself
Sources
- NIST FIPS 180-4: Secure Hash Standard ("the result is an output called a message digest… it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest. Any change to a message will, with a very high probability, result in a different message digest.")
What you now know
A hash function turns any data into a short, fixed-size digest, like SHA-256's 256 bits. Change one bit of the data and the digest changes completely, and nobody can make data that matches a given digest. So comparing digests shows whether data was changed.
Answer every question above correctly to unlock the next puzzle.
Something wrong or unclear on this page? Tell me: a puzzle that didn't click is a bug in the puzzle.