# 4.3 Multiple Use of a One-Time Pad

Alice sends messages to Bob, Carla, and Dante. She encrypts each message with a one-time pad, but she’s lazy and uses the same key for each message. In this section, we’ll show how Eve can decrypt all three messages.

Suppose the messages are ${M}_{1}\text{,}\text{}{M}_{2}\text{,}\text{}{M}_{3}$ and the key is $K$. The ciphertexts ${C}_{1}\text{,}\text{}{C}_{2}\text{,}\text{}{C}_{3}$ are computed as ${M}_{i}\oplus K={C}_{i}$. Eve computes

Similarly, she obtains ${M}_{1}\oplus {M}_{3}={C}_{1}\oplus {C}_{3}$ and ${M}_{2}\oplus {M}_{3}={C}_{2}\oplus {C}_{3}$. The key $K$ has disappeared, and Eve’s task is to deduce ${M}_{1}\text{,}\text{}{M}_{2}\text{,}\text{}{M}_{3}$ from knowledge of ${M}_{1}\oplus {M}_{2}$, ${M}_{1}\oplus {M}_{3}$, ${M}_{2}\oplus {M}_{3}$. The following example shows some basic ideas of the method.

Let’s assume for simplicity that the messages are written in capital letters with spaces but with no other punctuation. The letters are converted to ASCII using

(the letters $A$ to $Z$ are the numbers 65 through 90 written in binary, and *space* is 32 in binary; see Table 4.1).

The XORs of the messages are

Note that the first block of ${M}_{1}\oplus {M}_{2}$ is `0000000`

. This means that the first letter of ${M}_{1}$ is the same as the first letter of ${M}_{2}$. But the observation that makes the biggest difference for us is that “*space*” has a 0 as its leading bit, while all the letters have 1 as the leading bit. Therefore, if the leading bit of an XOR block is 1, then it arises from a letter XORed with “*space*.”

For example, the third block of ${M}_{1}\oplus {M}_{2}$ is `1100100`

and the third block of ${M}_{1}\oplus {M}_{3}$ is `1100001`

. These can happen only from $\u201cspace\oplus \text{1000100}\u201d$ and $\u201cspace\oplus \text{1000001}\u201d$, respectively. It follows easily that ${M}_{1}$ has “*space*” as its third entry, ${M}_{2}$ has $1000100=H$ as its third entry, and ${M}_{3}$ has $A$ as its third entry. Similarly, we obtain the 2nd, 7th, 8th, and 9th entries of each message.

The 5th entries cause a little more trouble: ${M}_{1}\oplus {M}_{2}$ and ${M}_{1}\oplus {M}_{3}$ tell us that there is “*space*” XORed with $A$, and ${M}_{2}\oplus {M}_{3}$ tells us that the 5th entries of ${M}_{2}$ and ${M}_{3}$ are equal, but we could have “*space A A*” or “*A space space*.” We need more information from surrounding letters to determine which it is.

To proceed, we use the fact that some letters are more common than others, and therefore certain XORs are more likely to arise from these than from others. For example, the block 0010001 is more likely to arise from $E\oplus T=\text{1000101}\oplus \text{1010100}$ than from $K\oplus Z=\text{1001011}\oplus \text{1011010}$. The most common letters in English are $E\text{,}\text{}T\text{,}\text{}A\text{,}\text{}O\text{,}\text{}I\text{,}\text{}N\text{,}\text{}S\text{,}\text{}H\text{,}\text{}R\text{,}\text{}D\text{,}\text{}L$. Make a table of the XORs of each pair of these letters. If an XOR block occurs in this table, we guess that it comes from one of the pairs yielding this block. For example, `0001001`

arises from $A\oplus H$ and from $E\oplus L$, so we guess that the 11th block of ${M}_{1}\oplus {M}_{2}$ comes from one of these two combinations. This might not be a correct guess, but we expect such guesses to be right often enough to yield a lot of information.

Rather than produce the whole table, we give the blocks that we need and the combinations of these frequent letters that produce them:

Let’s look at the next-to-last block of each XOR. In ${M}_{1}\oplus {M}_{2}$, we have `0010111`

, which could come from $D\oplus S$ or $E\oplus R$. In ${M}_{1}\oplus {M}_{3}$, we have `0000100`

, which could come from $A\oplus E$ or $H\oplus L$. In ${M}_{2}\oplus {M}_{3}$, we have `0010011`

, which could come from $A\oplus R$. The only combination consistent with these guesses is $E\text{,}\text{}R\text{,}\text{}A$ for the next-to-last letters of ${M}_{1}\text{,}\text{}{M}_{2}\text{,}\text{}{M}_{3}$, respectively. This type of reasoning, combined with the information obtained from the occurrence of spaces, yields the following progress (- indicates a space, * indicates a letter to be determined):

The first letter of ${M}_{3}$ is a one-letter word. The XOR block `0000001`

gives us the possibilities $D\text{,}\text{}E\text{,}\text{}H\text{,}\text{}I\text{,}\text{}R\text{,}\text{}S\text{,}\text{}$ so we guess ${M}_{3}$ starts with $I$. The XORs tell us that ${M}_{1}$ and ${M}_{2}$ start with $H$.

Now let’s look at the 12th letters. The block `0001111`

for ${M}_{1}\oplus {M}_{2}$ suggests $A\oplus N$. The block for ${M}_{1}\oplus {M}_{3}$ suggests $D\oplus H$ and $E\oplus I$. The block for ${M}_{2}\oplus {M}_{3}$ suggests $L\oplus O$. These do not have a common solution, so we know that one of the less common letters occurs in at least one of the messages. But ${M}_{2}$ ends with $DOL*AR*$, and a good guess is that this should be $DOLLARS$. If so, then the XOR information tells us that ${M}_{1}$ ends in `SECRET`

, and ${M}_{3}$ ends in `TODAY`

, both of which are words. So this looks like a good guess. Our progress so far is the following:

It is time to revisit the 5th letters. We already know that they are “*space A A*” or “*A space space*.” The first possibility requires ${M}_{1}$ to have two consecutive one-letter words, which seems unlikely. The second possibility means that ${M}_{3}$ starts with the two words `$\text{I\u2013A\u2217}$`

, so we can guess this is `$\text{IAM}$`

. The XOR information tells us that ${M}_{1}$ and ${M}_{2}$ have $H$ and $E$, respectively. We now have all the letters:

Something seems to be wrong in the 6th column. These letters were deduced from the assumption that they all were common letters, and this must have been wrong. But at this point, we can make educated guesses. When we change $I$ to $H$ in ${M}_{3}$, and make the corresponding changes in ${M}_{1}$ and ${M}_{2}$ required by the XORs, we get the final answer:

These techniques can also be used when there are only two messages, but progress is usually slower. More possible combinations must be tried, and more false deductions need to be corrected during the decryption. The process can be automated. See [Dawson-Nielsen].

The use of spaces and the restriction to capital letters made the decryption in the example easier. However, even if spaces are removed and more symbols are used, decryption is usually possible, though much more tedious.

During World War II, problems with production and distribution of one-time pads forced Russian embassies to reuse some keys. This was discovered, and part of the Venona Project by the U.S. Army’s Signal Intelligence Service (the predecessor to NSA) was dedicated to deciphering these messages. Information obtained this way revealed several examples of Russian espionage, for example, in the Manhattan Project’s development of atomic bombs, in the State Department, and in the White House.