One-Time Pad: Unbreakable Once, Broken Twice

XOR every byte of a message with a random key byte and the ciphertext tells an enemy nothing. Use the same key on two messages and it drops out: guess a word, slide it along, and read the other message underneath.

Worked example — One-Time Pad: Unbreakable Once, Broken Twice

Characters	14
Possible keys of this length	5.2 × 10³³
Messages of this length the ciphertext could be	1.1 × 10²⁰

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — One-Time Pad: Unbreakable Once, Broken Twice

A one-time pad combines each character of a message with a key character chosen at random, used for that one character and never again. Here the combination is the bitwise exclusive or, byte by byte: C = P ⊕ K, and decryption is the same operation, P = C ⊕ K. With a random key as long as the message the cipher has perfect secrecy: seeing the ciphertext changes nobody's estimate of which message was sent. Used on two messages the key cancels, C₁ ⊕ C₂ = P₁ ⊕ P₂, and crib-dragging slides a guessed word w along it: wherever one message really contains w, w ⊕ C₁ ⊕ C₂ is the other message.

What each symbol means

P: the message, one byte per character
K: the key: random bytes, as many as the message has characters
C: the ciphertext, P ⊕ K
⊕: exclusive or: each bit of the result is 1 where the two bits differ
w: the crib, a word guessed to be in one of the messages

Assumes: Messages are lowercase letters and spaces stored as ASCII bytes. The key bytes come from a generator started at a 32-bit seed, so the page reaches only 2³² ≈ 4.3 × 10⁹ keys; from seven characters on that is fewer keys than messages, and by Shannon's count the page's own pad is not perfectly secret. A real pad needs bytes nobody can regenerate. A fragment “looks like text” when every byte is a letter or a space and every run of three characters in it occurs in the first two thirds of Poe's “The Gold-Bug” (1843); the measured pairs come from the last third. XOR rather than letters added mod 26, because XOR has no sign: one fragment comes out whichever message holds the crib.

Trying every key finds every message 🖖

Step through Attack at dawn and look at the bottom two rows. They hold the key that would turn the very same ciphertext into “retreat at ten”. Type any other 14 letters and single spaces into the second box and a key for that appears too, because XOR undoes itself: the ciphertext XOR your message is the key. So an enemy who tries all 256¹⁴ keys does not end up with the message. He ends up with every one of the 27¹⁴ ≈ 1.1 × 10²⁰ strings of that length, each from exactly one key, and since every key was equally likely the interception has not made any of them more likely than it was before. Shannon called that perfect secrecy in 1949 and proved what it costs: at least as many keys as possible messages. A Vigenère key that repeats has far fewer, which is why counting can break it.

The spaces show through before any guess 🖖

Press Where the spaces are. The key has cancelled: C₁ ⊕ C₂ is P₁ ⊕ P₂, byte for byte, with nothing of the key left in it. Now look at the blue bytes, 19 of the 50. A small letter is a byte from 0x61 to 0x7a and a space is 0x20, and only a letter against a space sets the 0x40 bit, so every byte of 64 or more marks a place where exactly one of the two messages has a space. Before anyone guesses a word, the gaps between words are showing, though not which message each gap belongs to. Over 2,000 pairs of 60-character passages from The Gold-Bug about 30% of positions show one. The Soviet traffic that Meredith Gardner began reading in 1946, under the American cover name Venona, added key digits to code groups instead of XORing bytes, but subtracting one ciphertext from another cancels a shared key just the same. The key had been shared by accident: under the pressure of the German advance on Moscow, the company that made the KGB's pads turned out about 35,000 pages of duplicate key.

The two spaces round a crib do most of the work 🖖

Press Without the spaces. “the” at position 26 gives “org”, letters only, and every run of three in it occurs in the reference text, yet neither message has “the” there. Put the spaces back, “ the ”, and only real hits pass on this pair. Over 2,000 pairs of 60-character passages from the last third of The Gold-Bug, which the reference never saw, “ the ” passed at 3,661 positions and was really there at 3,281, about 9 in 10. “the” passed at 9,615 and was there at 4,169, fewer than half. The reason is the blue bytes. A space in the crib comes out as a letter only over a byte of 64 or more and as a space only over a 0; over anything else it gives a byte that is no letter at all. So each space in the crib must land where one message really has a gap, and a wrong position rarely manages two.

Problem solved in full

Five letters out of two messages that share a pad 4 steps
Two messages of 50 characters went out under the same one-time pad. At positions 32 to 36, C₁ ⊕ C₂ reads 54 06 09 0c 4e in hexadecimal. Guess that one of the messages has “ the ” there, the bytes 20 74 68 65 20. What does the other message say at those five places? If the guess belongs to message 2, whose ciphertext there is 9d 8e 23 40 9e, what are the five key bytes? Then press Worked problem and take the next step on the page.

Open this problem in the tool
1. Write the first pair in binary: 0x54 is 01010100 and the space 0x20 is 00100000. XOR sets a bit where the two differ, giving 01110100, which is 0x74, the letter t. The 0x40 bit of 0x54 had already said, before any guess, that one message has a space at position 32.
  
  $0x54 \oplus 0x20 = 01010100 \oplus 00100000 = 01110100 = 0x74 = t$
2. The other four: 0x06 ⊕ 0x74 = 0x72, r; 0x09 ⊕ 0x68 = 0x61, a; 0x0c ⊕ 0x65 = 0x69, i; 0x4e ⊕ 0x20 = 0x6e, n. The other message reads “train”, and its three runs of three, “tra”, “rai” and “ain”, all occur in the reference.
  
  $54 06 09 0c 4e \oplus 20 74 68 65 20 = 74 72 61 69 6e = train$
3. If “ the ” is in message 2, the key is C₂ ⊕ P₂: 0x9d ⊕ 0x20 = 0xbd, 0x8e ⊕ 0x74 = 0xfa, 0x23 ⊕ 0x68 = 0x4b, 0x40 ⊕ 0x65 = 0x25, 0x9e ⊕ 0x20 = 0xbe. Had the guess belonged to message 1, message 2 would read “train” and the key bytes would be C₁ ⊕ “ the ” instead. C₁ ⊕ C₂ is the same either way, so the arithmetic cannot say which.
  
  $K = C_{2} \oplus P_{2} = 9d 8e 23 40 9e \oplus 20 74 68 65 20 = bd fa 4b 25 be$
4. On the page “ the ” is kept in message 2 at 32, and the crib box holds “ train ” at 31, a bet that message 1's “train” is a whole word. Out comes “y the r” for message 2: letters and spaces, every run of three seen before. Keep it in message 1 and both rows grow to seven characters.
  
  $(C_{1} \oplus C_{2})_{31..37} \oplus 20 74 72 61 69 6e 20 = 59 54 06 09 0c 4e 52 \oplus 20 74 72 61 69 6e 20 = 79 20 74 68 65 20 72$
Answer

“train”, and key bytes bd fa 4b 25 be if the guess was message 2's. Nothing in C₁ ⊕ C₂ says which message holds “ the ”, and nothing ever will: swap the two messages whole and C₁ ⊕ C₂ is unchanged. What the next guess decides is which fragments belong to the same message. The page also counts how many recovered characters are right, because it was given both messages. An interceptor has only the two rows and whether they make sense.

$train, K_{32..36} = bd fa 4b 25 be$

Learning path

How codes are broken

References (2)

The first insight's perfect secrecy and its cost in keys, and the Vigenère link: C. E. Shannon, "Communication Theory of Secrecy Systems," Bell System Technical Journal 28(4), pp. 656–715, October 1949. §10 "Perfect Secrecy", Theorem 6 (pp. 679–682).
The second insight's Venona history: the additive key, the duplicate pages, Gardner's first message: "VENONA: An Overview," Cryptologic Almanac 50th Anniversary Series, Center for Cryptologic History, National Security Agency. DOCID 3575728, approved for release 2009.

By the 42Math team · Reviewed against published sources. Corrections welcome.