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 is bits; a key is bits too. Line them up.
Step 1 of 4XOR them: 1 where the bits differ, 0 where they're equal. The result is gibberish.
Step 2 of 4XOR 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 4XORing 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:
| data | 0101 |
|---|---|
| key | 0011 |
| data XOR key | 0110 |
| … XOR key again | 0101, 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
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.
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.