4.3 Multiple Use of a One-Time Pad – Introduction to Cryptography with Coding Theory, 3rd Edition

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 M1, M2, M3 and the key is K. The ciphertexts C1, C2, C3 are computed as MiK=Ci. Eve computes

C1C2=(M1K)(M2K)=M1M2.

Similarly, she obtains M1M3=C1C3 and M2M3=C2C3. The key K has disappeared, and Eve’s task is to deduce M1, M2, M3 from knowledge of M1M2, M1M3, M2M3. 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

A=1000001, B=1000010, , Z=1011010,  space =0100000

(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

M1M2=000000000011001100100000110111000010011110111100111000011100100001110000010010001111001001100101110000111M1M3=000000111001011100001000010111000010011011110010100100111100101111001100100010001100001011000001000001101M2M3=000000111010010000101000100000000000000101001110011100100000001110111100110000000011000010100100110001010.

Note that the first block of M1M2 is 0000000. This means that the first letter of M1 is the same as the first letter of M2. 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 M1M2 is 1100100 and the third block of M1M3 is 1100001. These can happen only from space1000100 and space1000001, respectively. It follows easily that M1 has “space” as its third entry, M2 has 1000100=H as its third entry, and M3 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: M1M2 and M1M3 tell us that there is “space” XORed with A, and M2M3 tells us that the 5th entries of M2 and M3 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 ET=10001011010100 than from KZ=10010111011010. The most common letters in English are E, T, A, O, I, N, S, H, R, D, 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 AH and from EL, so we guess that the 11th block of M1M2 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:

0000001DE, HI, RS0000011LO0000100AE, HL0000101AD, IL0001000AI, DL0001001AH, EL0001100DH, EI0001111AN0010001ET0010011AR0010110DR, ES0010111DS, ER0011000LT0011011HS, IR, OT0011110LR

Let’s look at the next-to-last block of each XOR. In M1M2, we have 0010111, which could come from DS or ER. In M1M3, we have 0000100, which could come from AE or HL. In M2M3, we have 0010011, which could come from AR. The only combination consistent with these guesses is E, R, A for the next-to-last letters of M1, M2, M3, 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):

M1=ERASEREM2=IDLYDOLARM3=AIERETDA

The first letter of M3 is a one-letter word. The XOR block 0000001 gives us the possibilities D, E, H, I, R, S,  so we guess M3 starts with I. The XORs tell us that M1 and M2 start with H.

Now let’s look at the 12th letters. The block 0001111 for M1M2 suggests AN. The block for M1M3 suggests DH and EI. The block for M2M3 suggests LO. 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 M2 ends with DOL*AR*, and a good guess is that this should be DOLLARS. If so, then the XOR information tells us that M1 ends in SECRET, and M3 ends in TODAY, both of which are words. So this looks like a good guess. Our progress so far is the following:

M1=HERASECRETM2=HIDLYDOLLARSM3=IAIERETODAY

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 M1 to have two consecutive one-letter words, which seems unlikely. The second possibility means that M3 starts with the two words I–A∗, so we can guess this is I AM. The XOR information tells us that M1 and M2 have H and E, respectively. We now have all the letters:

M1=HEHARASECRETM2=HIDELYDOLLARSM3=IAMIERETODAY

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 M3, and make the corresponding changes in M1 and M2 required by the XORs, we get the final answer:

M1=HEHASASECRETM2=HIDEMYDOLLARSM3=IAMHERETODAY.

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.