Encryption, from the ground up · Puzzle 1 · 2 of 9

Bits, XOR and a toy cipher

Puzzle 0 said encryption turns data into gibberish with a key. Before any real cipher, here's the one operation every cipher you'll meet ends with, and a complete cipher you can do by hand.

The problem

Puzzle 0 said a key turns data into gibberish and back. That's a black box. How can a number possibly hide a message, and get it back exactly?

See it

Data bits 0101 XORed with key bits 0011 give 0110; XORing 0110 with the same key gives back 0101; reusing the key for two messages lets the listener cancel it data0 1 0 1key0 0 1 1 XOR0 1 1 0gibberish XOR key0 1 0 1the data again same key twice: the two ciphertextsXORed together cancel it
  1. Data is bits; a key is bits too. Line them up.

    Step 1 of 4
  2. XOR them: 1 where the bits differ, 0 where they're equal. The result is gibberish.

    Step 2 of 4
  3. XOR with the same key again, and the data comes back exactly. That's a cipher. Predict: what if the key is used twice?

    Step 3 of 4
  4. XORing the two ciphertexts cancels the key: a one-time pad must be used once. Real ciphers make a fresh keystream instead.

    Step 4 of 4

The building block

Everything your app sends is bits: zeros and ones, eight to a byte. A key is bits too.

XOR (exclusive or) combines two bits: the result is 0 if they're equal, 1 if they differ. Do it bit by bit to two strings:

data0101
key0011
data XOR key0110
… XOR key again0101, the data

XOR with the same key twice gives you back what you started with. That's a cipher: XOR the data with the key to encrypt, XOR the result with the key again to decrypt.

If the key is truly random, as long as the data, and used only once, that's a one-time pad: every possible message is equally likely from the ciphertext, so the listener learns nothing at all.

Its weakness is the "once". Use the same key for two messages, and the listener XORs the two ciphertexts: the key cancels out, leaving the two messages XORed together, which is often enough to read both.

Real ciphers keep the XOR and fix the key problem: from one short key they generate a long, fresh stream of key bits, a keystream, different for every message. The next puzzle shows a real cipher doing exactly that.

The analogy

A stencil of random holes over a page of letters: shift each letter where there's a hole, leave it where there isn't. With the same stencil, the friend undoes it exactly. Use the stencil twice, and overlaying the two pages shows where they differ.

Check yourself

Data 1100, key 1010. What is data XOR key?

Not quite. That's AND; XOR gives 1 where the bits differ.

Not quite. That's OR; XOR gives 0 when both bits are 1.

Right. Different gives 1, equal gives 0.

The same one-time pad key encrypts two messages. What can the listener do?

Not quite. The key cancels out when the two ciphertexts are combined.

Right. Reusing the key cancels it.

Not quite. Not directly; the leak comes from combining the two.

What's the difference between a one-time pad key and a keystream?

Right. Truly random vs generated.

Not quite. That's the two swapped. Re-read that part ↑

Sources

  • NIST SP 800-38A (exclusive-OR: "The bitwise addition, modulo 2, of two bit strings of equal length")
  • RFC 4949, Internet Security Glossary (one-time pad: "An encryption algorithm in which the key is a random sequence of symbols and each symbol is used for encryption only one time")

What you now know

Data is bits, and a key is a string of bits too. XOR combines two bits: 0 if they're equal, 1 if they differ; XOR the same key in twice and you're back where you started. A one-time pad XORs each data bit with a key bit: perfectly secret if the key is random, as long as the data, and used once. Reuse the key, and XORing two ciphertexts cancels it, leaking the two messages XORed together.