Taking advantage of one-time pad key reuse?

Question

Suppose Alice wants to send encryptions (under a one-time pad) of $m_1$ and $m_2$ to Bob over a public channel. Alice and Bob have a shared key $k$; however, both messages are the same length as the key $k$. Since Alice is extraordinary lazy (and doesn't know about stream ciphers), she decides to just reuse the key.

Alice sends ciphertexts $c_1 = m_1 \oplus k$ and $c_2 = m_2 \oplus k$ to Bob through a public channel. Unfortunately, Eve intercepts both of these ciphertexts and calculates $c_1 \oplus c_2 = m_1 \oplus m_2$.

What can Eve do with $m_1 \oplus m_2$?

Intuitively, it makes sense that Alice and Bob would not want $m_1 \oplus m_2$ to fall into Eve's hands, but how exactly should Eve continue with her attack?

Answer 1

There is a great graphical representation of the possible problems that arise from reusing a one-time pad. Reusing the same key multiple times is called giving the encryption 'depth' - and it is intuitive that the more depth given, the more likely it is that information about the plaintext is contained within the encrypted text.

The process of 'peeling away' layered texts has been studied, as ir01 mentions, and those methods improve with more layers.

Answer 2

There are two methods, named statistical analysis or Frequency analysis and pattern matching.
Note that in statistical analysis Eve should compute frequencies for $aLetter \oplus aLetter$ using some tool like this. A real historical example using frequency analysis is the VENONA project.

EDIT: Having statistical analysis of $aLetter \oplus aLetter$ like this says:
If a character has distribution $X$, the two characters behind $c_1 \oplus c_2$ with probability $P$ are $c_1$, $c_2$.

Answer 3

A recent (2006) paper that describes a method is "A natural language approach to automated cryptanalysis of two-time pads". The abstract:

While keystream reuse in stream ciphers and one-time pads has been a well known problem for several decades, the risk to real systems has been underappreciated. Previous techniques have relied on being able to accurately guess words and phrases that appear in one of the plaintext messages, making it far easier to claim that “an attacker would never be able to do that.” In this paper, we show how an adversary can automatically recover messages encrypted under the same keystream if only the type of each message is known (e.g. an HTML page in English). Our method, which is related to HMMs, recovers the most probable plaintext of this type by using a statistical language model and a dynamic programming algorithm. It produces up to 99% accuracy on realistic data and can process ciphertexts at 200ms per byte on a $2,000 PC. To further demonstrate the practical effectiveness of the method, we show that our tool can recover documents encrypted by Microsoft Word 2002

Answer 4

The thing here is:

When you just XOR the cyphertexts with each other, what you get is in fact the XOR result of both cleartexts.

f(a) ⊕ f(b) = a ⊕ b

And after that point, all that's left is to use statistical analysis, as ir01 has mentioned.

In fact, the early cell phones used to implement a somewhat similar encryption scheme. They had a one byte (if my memory serves me well) key which was used to XOR the voice in blocks. Thus, an attacker could just XOR the voice message by itself phase shifted by one byte, and get the clear voice communication phase shifted and XOR'd by itself. Which is indeed very easy to crack. Even easier to crack than the XOR result of two separate cleartexts.

Also, as Tangurena mentioned, the Soviet message traffic was decrypted due to the fact that one-time-pads had been re-used. See the Wikipedia article on the VENONA Project.

Plus, here's an article with a little more insight to the practical side of the subject: Automated Cryptanalysis of Plaintext XORs of Waveform Encoded Speech

Answer 5

If you have $m_1 \oplus m_2$, you can learn about the underlying message format.

It is possible to determine patterns in the underlying plaintext and use these patterns to extract data from the ciphertext.