DSP Explorables

The one-time pad

Every cipher on Old ciphers, and breaking them fell to the same weakness: the key was small, or it repeated, so patterns in the message showed through. Take that to its end, and make the key as long as the message, random, and never used again, and something remarkable happens: a cipher that can’t be broken at all, not with any amount of cleverness or computing power. This page is about that cipher, the one-time pad, and why, despite being perfect, it’s almost never used.

1 · A key as long as the message

Vigenère shifts each letter by a letter of its key, and the key repeats: that repetition is what breaks it. So don’t repeat it. Write the key out as long as the message, every letter chosen at random, and shift each letter of the message by its own letter of the key (A shifts by 0, B by 1, and so on, wrapping round from Z to A):

message   H E L L O
key       X M C K L
shifted   E Q N V Z

To decrypt, shift each letter back by the same key letter. Every letter of the key is a fresh random choice, so there’s no pattern for a codebreaker to find.

Computers do the same with bits. Each character is stored as a number, a byte of eight bits: H is 72, or 01001000 in binary. And instead of shifting, each bit of the message is combined with a bit of the key by XOR (exclusive or, written ⊕): the answer is 1 when the two bits differ, 0 when they’re the same.

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

XOR with a 1 flips a bit; XOR with a 0 leaves it alone. Flip a bit twice and it’s back where it started, so XORing with the same key a second time undoes the first: (message ⊕ key) ⊕ key = message. Encrypting and decrypting are the same operation.

A message XORed, bit by bit, with a pad of random bytes (written in hexadecimal, two digits a byte), then XORed with the same pad again. Bits that are 1 are shaded. Each 1 in the pad flips the message’s bit above it; the second XOR flips the same bits back. Type a message, or draw a new pad: the ciphertext changes completely, and the message always comes back.

The name comes from the paper pads the keys were printed on: a sheet for each message, torn off and destroyed once it had been used. Gilbert Vernam built the bitwise version into a teleprinter at AT&T in 1917, XORing each character with one punched on a paper tape.

2 · Perfect secrecy

Why can’t it be broken? Not because the attacker can’t try every key, but because trying every key doesn’t help.

Suppose an attacker, Eve, has a ciphertext of 14 bytes. For any message of 14 characters she cares to imagine, there’s exactly one pad that turns the ciphertext into it: ciphertext ⊕ that message. And the pad was chosen at random, every one of them as likely as every other. So every message she can imagine is exactly as likely as every other, as far as the ciphertext can tell her.

A ciphertext of 14 bytes, made with a one-time pad. Type any message of 14 characters (or pick one): the middle row is the pad that would have turned that message into this ciphertext, and the bottom row checks it. Every guess has its own pad, and nothing in the ciphertext says which pad was used, so nothing says which message was sent.

The ciphertext tells Eve the length of the message, and nothing else. Claude Shannon proved this in 1949 and gave it a name: perfect secrecy. He also proved the price: any cipher with perfect secrecy needs a key at least as long as the messages it protects. There’s no clever way round it.

3 · The catch

Perfect secrecy holds only while all of these do:

The pad is truly random. If it comes from a predictable process, an attacker who can predict it can read everything. Making unpredictable numbers is harder than it sounds: it’s the subject of Randomness.
The pad is as long as everything ever sent. A gigabyte of messages needs a gigabyte of pad.
The pad reaches the other end secretly. Both sides need the same pad, so it must be carried there, on paper or a disk, by someone trusted. But if there’s a safe way to carry a gigabyte of pad, why not carry the messages that way instead?
No page is ever used twice. The next section shows why.

So the one-time pad lives where those can be met: between governments, with pads carried by couriers. The Moscow–Washington hotline, set up in 1963 after the Cuban missile crisis, sent its teleprinter messages encrypted with one-time tapes, which the two sides exchanged through their embassies.

And even a perfect pad only hides a message. It doesn’t stop it being changed: flip a bit of the ciphertext, and the same bit of the decrypted message flips, as What we want from cryptography shows. Secrecy and protection from tampering are separate jobs.

4 · Using it twice

Making pads is hard work, and it’s tempting to use a page again. Here’s what that gives away. Two messages, m₁ and m₂, encrypted with the same pad k:

c₁ = m₁ ⊕ k and c₂ = m₂ ⊕ k

An attacker who has both XORs them together, and the pad cancels (k ⊕ k is all zeros):

c₁ ⊕ c₂ = m₁ ⊕ k ⊕ m₂ ⊕ k = m₁ ⊕ m₂

No key needed. What’s left is the two messages XORed together: not either message, but no longer random. Pictures show it best.

Two pictures, made of dots (1 for a dot, 0 for none), each XORed with the same random pad. Each ciphertext on its own is noise, about half its dots on, whatever the picture. XOR the two ciphertexts, and the pad cancels: what’s left is the two pictures XORed together, both in plain view (the last tile counts the dots where that isn’t so). Type your own words, or draw a new pad.

Where the two pictures overlap, the dots cancel, but every stroke of each word is still there to read. Text doesn’t show through so plainly, but as the next section shows, it doesn’t take much more to pull it apart.

5 · Pulling two messages apart

Two messages, sent with the same pad. The attacker has c₁ ⊕ c₂ = m₁ ⊕ m₂, and a guess: messages in English are full of common words. Suppose ” the ” (with its spaces) is somewhere in message 1. Put it at some position, XOR it with c₁ ⊕ c₂ there, and out comes what message 2 must say at that position. If the guess is in the wrong place, that’s gibberish. If it’s in the right place, it’s a piece of real text. This is called crib dragging: the guess is the crib, dragged along the ciphertext a position at a time.

top: ciphertext 1 ⊕ ciphertext 2 (hex)message 1message 2· not known yet● the guess reads well here

Two messages of 62 characters, sent with the same pad: all you have is the top row, the two ciphertexts XORed. Slide the guess along (or click a column): the other message’s row shows what it must say there, green if it’s readable, red if not, and ● marks every place the guess reads well. Keep a guess that looks right, then build on it: guess how the words you’ve found go on, and which message they’re in. Start again if a guess turns out to be wrong, or ask to be shown.

” the ” reads well in four places. Three are real: two with ” the ” in message 1 and one with it in message 2 (the figure doesn’t know which, so try both). The fourth gives “ijiqb”: only letters, but not words, a false alarm that a reader spots at once and a program has to be taught to. From each real fragment, guess how it goes on: “as ch” could be the end of “has” and the start of “changed”, say. Each word added to one message reads off the same stretch of the other, and the two messages come out together.

A small trick helps too. A space is 00100000 in binary; a small letter XORed with it is the same letter as a capital. So wherever c₁ ⊕ c₂ is a capital letter’s byte (41 to 5A in hexadecimal), one message very likely has a space there, and the other that letter.

And once either message is known, so is the pad (c₁ ⊕ m₁ = k), for as far as the message went.

This isn’t only a puzzle. In the early 1940s, under the pressure of war, the Soviet Union’s pad makers produced some pages more than once. American and British codebreakers, in the project later called Venona, found the duplicates and read parts of thousands of Soviet messages from them over the following decades. The work stayed secret until 1995.

Summary