Encryption, from the ground up · Puzzle 3 · 4 of 6

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

Data of any size goes into a hash function and comes out as a short digest; changing one bit gives a completely different digest; comparing digests shows a change 10 MB file SHA-256 9f2c…a71edigest: always 256 bits 1 bit flipped4be0…07c3 compare: different
  1. Any data, a word or a 10 MB file, goes into a hash function. The standard one is SHA-256.

    Step 1 of 4
  2. Out comes a short digest, always 256 bits: a fingerprint of the data. Same data, same digest, every time.

    Step 2 of 4
  3. Flip 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 4
  4. Hash 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 use a keyed check: a short value computed from the data and the key together, the way a hash is computed from data alone. Without the key, nobody can make a check that matches changed data. That's what protects your data once a connection is set up (puzzle 5). Before there's a shared key, the next block 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

One bit of a 10 MB file is flipped on the way. What happens to its SHA-256 digest?

Not quite. A hash doesn't map bits to bits: one flipped bit changes the whole digest.

Right. One bit changed, a different digest.

Not quite. Any change, even one bit, gives a different digest.

Why can't an attacker just make new data that has the expected digest?

Not quite. The digest's strength is in the hash function itself, not in AES. Re-read that part ↑

Right. Going from digest back to data is the hard direction.

What's the difference between a digest and ciphertext?

Not quite. A hash uses no key at all, and there's no way back from a digest.

Right. A fingerprint vs locked data.

Not quite. Ciphertext is about as long as the data; a digest is always the same short size.

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.