XOR and the one-time pad

A pad the size of your palm. Every page holds columns of random digits and nothing else. The cipher clerk takes the top page, adds its digits to the digits of the report, sends the result by telegraph and burns the page. In Moscow, in the only other copy of the pad, the same page waits its turn: it will be subtracted from the telegram and burned as well.

This is the one-time pad, a cipher that a quarter of a century after its invention was proved to be unbreakable. Not “hard”, not “slow”: impossible in principle, no matter how many computers or how much time you have. In this lesson we’ll see why, and why American codebreakers nonetheless read thousands of such telegrams.

Bits and the XOR operation

A computer keeps everything as bits, marks that come in just two kinds: 0 and 1. A letter, a digit, a pixel is only an agreement about which string of bits stands for what. Eight bits in a row make a byte.

For encrypting bits there’s a handy operation called XOR (exclusive or), written ⊕. It takes two bits and gives one back, by the rule “one or the other, but not both”:

a	b	a ⊕ b
0	0	0
0	1	1
1	0	1
1	1	0

You don’t have to memorise the table. Think of the second bit as a switch. If it’s 0, the first bit passes through untouched. If it’s 1, the first bit flips: 0 becomes 1 and 1 becomes 0. That’s the whole rule.

And that gives XOR its key property. Flip a bit twice and it’s back where it was. So (message ⊕ key) ⊕ key = message. The same operation with the same key both encrypts and decrypts, like ROT13 from the Caesar lesson, only bit by bit.

To encrypt letters we first turn them into bits. Computers use UTF-8 for that (see the lesson on encodings), but here we’ll use a simpler “telegraph code”: a space is 0, A is 1, B is 2, and so on up to Z = 26. Each letter takes five bits. D, for instance, is the fourth letter: 4 = 00100.

Try an all-zero key: the cipher equals the message. Now make the key equal to the message itself: you get all zeros, because x ⊕ x = 0. Both of these extremes will matter by the end of the lesson.

You’ve intercepted one character of a cipher: 01101. You know from elsewhere that the plaintext letter was T (the twentieth letter, 20 = 10100). Which five bits was it encrypted with?

Cipher = text ⊕ key. Move the text to the other side: key = cipher ⊕ text. XOR is its own inverse.

Go bit by bit from the left: where the cipher bit and the text bit match, the key has a 0; where they differ, a 1.

XOR them: 01101 ⊕ 10100. The first bits, 0 and 1, differ: write 1. Then 1 and 0 → 1, 1 and 1 → 0, 0 and 0 → 0, 1 and 0 → 1. The key is 11001, the number 25.

Notice that a single plaintext–cipher pair was enough to reveal a piece of the key. If that piece of key is ever used again, the cipher there is gone. Hold on to that thought: the second half of the lesson is about it.

Vernam and the endless tape

In 1917 Gilbert Vernam, an engineer at the American telephone company AT&T, was working with teleprinters, machines that sent text down a wire. A teleprinter coded every letter as five positions across a paper tape, each punched or not: 1 or 0. That five-bit code is the ancestor of our telegraph code.

Vernam devised a simple attachment. Next to the message tape runs a second tape holding the key. The machine compares them hole by hole and punches a new hole wherever the two tapes differ. That is exactly XOR. At the other end of the line an identical key tape took the cipher off again. Nobody had to do anything by hand: you typed your text and gibberish went down the wire. Vernam was granted a patent in 1919.

The first version had a weakness: the key tape was glued into a loop, so the key repeated. And a repeating key is nearly a Vigenère cipher, which falls once you find the key length. The fix came from Joseph Mauborgne, a US Army Signal Corps officer: the key must be truly random, as long as the whole message, and never used again. That’s the one-time pad as we know it.

Why it can’t be broken

Remember how we broke Caesar: we tried every key and kept the one that made the text readable. Let’s do the same to a one-time pad. The key is as long as the message, every bit random. We start trying…

And here’s the trap. Among all the keys there is certainly one that turns the cipher into ATTACK AT DAWN. And another that gives RETREAT TO HILL. And a third for BUY MILK AND EGGS. Every meaningful text of the right length comes out of some key. Brute force doesn’t give you one answer; it gives you every possible answer at once, with nothing to choose between them.

Claude Shannon, the founder of information theory, turned this argument into a rigorous theorem. He proved it in a classified report in 1945 and published it in 1949 in “Communication Theory of Secrecy Systems”. Shannon called the property perfect secrecy: the cipher text tells you nothing about the message except its length. If before the intercept the enemy thought an attack was 30 % likely, after reading the intercept they still think 30 %. The cipher text hasn’t moved their knowledge a hair.

Shannon also proved the converse: perfect secrecy is only possible if the key is at least as long as the message. No clever cipher with a short key can give it. Absolute security costs miles of key.

If the one-time pad can’t be broken, why don’t we encrypt everything with it?

You need as much key as data, and it must be delivered to the receiver secretly in advance Because XOR is too slow to compute Because people learned to break it long ago

To send a gigabyte of video you’d first have to get a gigabyte of random key to the receiver, secretly, in person or by courier. And if you have such a safe channel, you might as well send the video through it. So the pad suits rare, short messages and is a poor fit for the internet.

The two-time pad mistake

The most fragile condition is “exactly once”. Let’s see what happens when the same pad page is used for two different messages.

Say we’ve intercepted two ciphers: c₁ = m₁ ⊕ k and c₂ = m₂ ⊕ k, with the same key k. XOR them: c₁ ⊕ c₂ = m₁ ⊕ k ⊕ m₂ ⊕ k. The key appears twice, and x ⊕ x = 0, so it cancels out. What’s left is m₁ ⊕ m₂, a blend of the two plaintexts with no key at all.

A blend isn’t text yet, but from here on ordinary wit takes over. Suppose one telegram contains the word PASSWORD. Lay it over the blend in the right place and it “subtracts out”, leaving a piece of the other telegram showing through. In the wrong place you get mush. Such a guess is called a crib, and the method is crib-dragging: you slide the crib along the tape until something readable appears underneath.

Find a piece of one telegram and you have a piece of the other. The new piece suggests how to continue (“HANGED” surely was “CHANGED”), and now you have a few more letters of the first telegram. Step by step both unravel completely, and the key comes with them: k = c₁ ⊕ m₁.

Two telegrams were encrypted with one pad page. Intelligence is sure that one of them contains the word MIDNIGHT. Drag it along the tape. Which word stands in the other telegram at the same place?

Most positions show some red dots: there the crib can’t be. Look for a position where everything underneath is letters and they make a real word.

A word like MIDNIGHT usually ends a sentence. Start from the last positions.

At the last position, the 24th, MIDNIGHT reveals THURSDAY. A few other positions give letters too (“AVMZOOTT”, “CSDWHVTN”), but they are mush.

The full telegrams: “WAIT FOR OUR SIGNAL AT MIDNIGHT” and “THE CARGO WILL SHIP ON THURSDAY”. From there you could unravel the rest with cribs like “ THE ” and “ AT ”. Shannon guaranteed the safety of one page, not of two.

Venona: saving on paper

This exact mistake happened for real. In early 1942, at the hardest point of the war, the Soviet office that produced cipher pads couldn’t keep up with demand. Some pages were printed twice and bound into different pads. Each pad on its own was used “correctly”, once, but duplicate pages ended up with different senders.

In February 1943 the US Army’s Signal Intelligence Service at Arlington Hall began studying intercepted Soviet diplomatic telegrams. The project was later named Venona. The codebreakers noticed matches: some telegrams had been encrypted with the same key. Then came years of painstaking work with codebooks and cribs. From 1946 the linguist Meredith Gardner rebuilt the vocabulary of the Soviet code.

Only a fraction of the telegrams were read, often only in pieces, but it was enough. The decrypts helped lead to the physicist Klaus Fuchs, who had passed on atomic bomb secrets, and to Julius Rosenberg’s network. The project ended in 1980 and was made public in 1995.

An agent encrypted the same report twice, with two different pad pages, and sent both. What does the enemy get by XORing the two ciphers?

A blend of the two key pages, k₁ ⊕ k₂; the text cancels out The plaintext itself All zeros

(m ⊕ k₁) ⊕ (m ⊕ k₂) = k₁ ⊕ k₂: the identical text cancels and two random pages remain. That’s useless to the enemy, though sending the same report twice is still a habit worth avoiding.

XOR today

One-time pads are still used where the key can be delivered in advance and messages are few. The Washington–Moscow hotline, opened in 1963, was protected by teleprinters with one-time tapes. But the internet needs something else: you can’t drive a suitcase of random bytes to every website beforehand.

The answer is stream ciphers. They take a short key, say 256 bits, and stretch it into an arbitrarily long tape of pseudo-random bits, then XOR that with the data, just like Vernam. The tape isn’t truly random, so there’s no Shannon-style perfect secrecy. But telling it apart from random would mean trying more keys than all the world’s computers could manage. One such cipher, ChaCha20, protects a share of today’s HTTPS connections.

The leading modern cipher, AES, works differently: it scrambles data in 16-byte blocks, round after round. Yet every one of its rounds includes an XOR with part of the key, and in its most popular mode AES also produces a tape that is XORed with the data. Try it in the AES password encryption tool. And the XOR tool lets you play with repeating keys and the known-plaintext attack, which will come in handy in the quest.

What to take with you

• XOR means “one or the other, but not both”. A 1 in the key flips a bit, a 0 leaves it. Applying the key twice gives the text back.
• The one-time pad: a random key as long as the message, XOR (or addition), once. Shannon proved such a cipher reveals nothing about the text but its length.
• Encrypt two texts with one key page and the key cancels: c₁ ⊕ c₂ = m₁ ⊕ m₂. Cribs unravel the rest. That’s how Venona worked.
• Know a piece of the plaintext, and XOR hands you a piece of the key at once: k = c ⊕ m.
• Modern stream ciphers and AES give up perfect secrecy to get by with a short key, and there’s XOR inside them all the same.

A cipher hides a message so it can be recovered. But what if you never need to recover anything, only to check: is this the same file, the same password? For that, people invented fingerprints of data. Next: hashes →