# How does one attack a two-time pad (i.e. one time pad with key reuse)?

My question might appear the same as the question Taking advantage of one-time pad key reuse?, but actually I did read all the answers and none of them helped me with the details I need.

I am new to cryptography and my problem is with two time pad attacks on OTP. The problem I had in my course was that I have 10 ciphertexts encrypted with the same key $K$. I am then given another ciphertext that I should decrypt.

I know that XOR-ing two ciphers gives me the XOR of their original messages.

My question is what is the correct thing to do after that?

I tried to take 3 ciphertexts $C_1, C_2$ and $C_3$.

Then get $S_1 = C_1 \oplus C_2 \oplus$' ', also get $S_2 = C_1 \oplus C_3 \oplus$ ' '.

After that I compared all corresponding characters in $S_1$ and $S_2$, and if $S_1[i] = S_2[i]$ then I calculate $S_1[i] \oplus C_2[i]$ to get $K[i]$.

I tried this on paper before coding and it worked, but I might be missing something.

Is this the right approach? Why does it work?

• If string1[i] == string2[i], that only means that C2[i] == C3[i] (and thus M2[i] == M3[i]). You can check that fact without doing any of those XOR operations. And XORing string1 by C2 gives you back C1 XOR "space", which, at a glance, doesn't seem to be related to key[i]. I haven't looked at that EC assignment for the class in any detail yet, but I think you're supposed to use the fact that XORing by "space" only changes the case of the original character. You might use that fact to analyze the XOR or two plaintext messages, which you obtain by XORing their two respective ciphertexts. Apr 1, 2012 at 1:35
• Yes, your totally right. I was mistaken with that part, but it is my very first trial in cryptography. I got it now Apr 1, 2012 at 20:21
• Does "the class" include a disclaimer that the method needs to have $m_1 \neq m_2$ in order for the method to work? Jun 16, 2012 at 11:35
• @DilipSarwate: If $m_1=m_2$ then the key has still only been used once. Therefore it is implicitly clear that $m_1\neq m_2$ Jun 16, 2012 at 11:56
• With so many (10) extra ciphertexts, techniques like crib dragging or statistical analysis are not required. The only assumption you need is that the plain text consists of mostly lower case letters ([a-z]) and spaces. When a space (0x20) is xor'd with a lower case letter it becomes upper case. Pick any $C$ and xor it with every other $C$. For any position $i$ where most of the results are capital letters you can guess that $M[i]$ is a space. After doing this for a few more $C$'s you can guess the rest like on "Wheel of Fortune". Jan 17 at 4:33

Well, the classical answer to "what is the correct thing to do after you have the XOR of the two original messages" is crib-dragging.

That is, you take a guess of a common phrase that may appear in one of the plaintexts (the classical example against ASCII english is the 5 letter " the "), and exclusive-or that against the XOR of the two original messages in various locations. If one of the plaintexts had the text of the crib (" the " in our example), then the result of the exclusive-or is what the other plaintext had in that position; if neither plaintext had that, it's likely that the result of the exclusive-or is just gibberish. And, once you have a plausible short section, you can extend it (for example, if you know that one of the plaintexts is " na**", you can go through the dictionary of all words that start with "na", use those as cribs, and see which makes the other plaintext make sense).

In addition, you can often deduce things directly from the bit pattern. For example, if the messages are in ASCII, then one thing to note that bit 6 of letters is set, but bit 6 of spaces, numbers and (most) punctuation is clear; because spaces are far more common than numbers and punctuation, then that will give you a good guess of where spaces occur in the texts (albeit without telling you which message a specific space appears in).

Now, if you have 11 messages all encrypted with the same pad (an "11-time pad"), things get even easier. Obviously, you can grab a crib across one message, and check it against the other 10; if it makes all 10 make sense, then it is almost certainly accurate. Even better, by using the observation that you can distinguish spaces from letters (again, by comparing bit 6), you can find where all the spaces appear in the messages; these all act like 1 character cribs, probably revealing virtually all the text of all the messages.

• Thanks, a lot i solved the problem. I started with ' the ' as you said and got 'robab' which i guessed would be 'probably'. I kept doing this with some guesses until i solved the whole message. Thanks again. Apr 1, 2012 at 20:23
• Furthermore, consider contents of more common files - sometimes a bunch of binary files are XORd with the same OTP. Some header patterns make determining the key super easy if you know the type, for example some image type has a long string of null bytes. Mar 13, 2014 at 8:22

In general, knowledge of $m_1 \oplus m_2$ is not enough to uniquely determine $m_1$ and $m_2$, even if both are known to be, say, English text. For a simple example, $$\text{"one one"} \oplus \text{"two two"} = \text{"one two"} \oplus \text{"two one"}.$$

However, in practice it may be possible to obtain fairly good guesses for $m_1$ and $m_2$; the typical methods are similar to those used for breaking classical ciphers, and rely on the fact that there's a lot of redundancy in English text (and in many other types of data).

For example, one might start by guessing that at least one of the messages is likely to contain the word "the", probably surrounded by spaces. So one can take the five-character string " the ", XOR it with every five-character substring of $m_1 \oplus m_2$ and look for results that look like English (either by eye or by computer using statistical analysis).

Now, let's say that one of the five-character substrings thus obtained is, say, "messa". Now we (or a computer) could guess that the next two characters are likely to be "ge" (or perhaps "gi"). We can now XOR that with the next two characters of $m_1 \oplus m_2$ and see if the result fits naturally after " the "; if the result is, say, "la", we might tentatively assume our guess to have been right; if it's "q%", we probably guessed wrong. We can proceed in this manner to confirm and extend our guess further, and perhaps eventually to connect separate guessed fragments together until we have a reasonable guess of all, or at least most, of the content of the two messages.

I just came across this question and was surprised that no one referenced the paper: A Natural Language Approach to Automated Cryptanalysis of Two-time Pads by Mason et al. at ACM CCS 2006. This shows how to solve this problem in an automated and intelligent way.

• Please don't just drop a link / a reference as an answer but rather try to at least summarize the contents ( / the general idea) of the linked ressource. Jan 31, 2016 at 10:49
• Said paper was already referenced in an answer to the question linked in the OP. This question is more specific to a particular homework question, where the expected approach is based on finding spaces. May 12, 2016 at 7:58