Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  B-Con Apr 1 '12 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 –  Samer Meggaly Apr 1 '12 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? –  Dilip Sarwate Jun 16 '12 at 11:35
1  
@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$ –  Maeher Jun 16 '12 at 11:56

2 Answers 2

up vote 26 down vote accepted

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.

share|improve this answer
    
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. –  Samer Meggaly Apr 1 '12 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. –  deed02392 Mar 13 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.

share|improve this answer

protected by Community Jun 25 '13 at 14:09

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.