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 (which I found on cryptosmith, but they keep changing their url structures, so I've added the graphics in here) of the possible problems that arise from reusing a one-time pad.

Let's say you have the image

and you encrypt it by using the binary one-time-pad (xor-ing on black and white)

.

You get the following extremely secure encryption

.

If you then encrypt a smiley face with the same one-time-pad,

you get another secure encryption

.

But if you have both and you xor them together

then you get the image

which, as you can qualitatively and intuitively see is very insecure.

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

Here, since the key is used more than one time, an attack called “crib dragging” can be used to attack the cipher-text.

The blog post Many Time Pad Attack - Crib Drag could give you a greater understanding on the implementation part:

Many Time Pad Attack – Crib Drag

The one time pad (OTP) is a type of stream cipher that is a perfectly secure method of encryption. It’s very simple to implement and is perfectly secure as long as the length of the key is greater than or equal to the length of the message. That’s its major downfall. However, it also requires that the key never be used more than once. This tutorial shows what happens when you re-use a key to encrypt more than one message. I also show how to uncover the plain-text of two messages that have been encrypted with the same key, without even knowing the key. I use a method called crib dragging.

Let’s begin with a brief description of OTP and how it works. Let’s take the following message and key:

message = "Hello World"
key = "supersecret"

If we convert both the message and key to hex strings, we get the following:

message = "48656c6c6f20576f726c64"
key = "7375706572736563726574"

If we do a simple XOR of the two hex strings we get the following cipher-text:

cipher-text = "3b101c091d53320c000910"

If we XOR the cipher-text with the key, we can recover the plain-text. That’s how OTP works. Without the key, you have no way of uncovering the plain-text.

Let’s consider what happens when you have two messages encrypted with the same key. Take the following two messages and key:

message1 = "Hello World"
message2 = "the program"
key = "supersecret"

If we convert each message and the key to hex strings, and then encrypt each message using a simple XOR with the key, we’ll get the following cipher-texts:

cipher-text1: "3b101c091d53320c000910"
cipher-text2: "071d154502010a04000419"

Let’s say that all we have is the two cipher-texts and the knowledge that they were encrypted with a supposed OTP; however, they were both encrypted with the same key. To attack this encryption and uncover the plain-text, follow the steps below.

1. Guess a word that might appear in one of the messages
2. Encode the word from step 1 to a hex string
3. XOR the two cipher-text messages
4. XOR the hex string from step 2 at each position of the XOR of the two cipher-texts (from step 3)
5. When the result from step 4 is readable text, we guess the English word and expand our crib search.
6. If the result is not readable text, we try an XOR of the crib word at the next position.

Step 1 seems difficult (guessing a word that might appear in one of the messages), but when you think about it, the word “the” is the most commonly used English word. So, we’ll start with assuming “the” is in one of the messages. After encoding “the” as a hex string, we’ll get “746865”. That takes care of steps 1 and 2. If we XOR the two cipher-texts, we’ll get the following result:

cipher-text1 XOR cipher-text2 = "3c0d094c1f523808000d09"

The next step is to XOR our crib word “746865” at each position of the XOR of the cipher-texts. What we’ll do is slide “746865” along each position of “3c0d094c1f523808000d09” and analyze the result. After the first XOR, we get the following result:

     3c0d094c1f523808000d09
XOR  746865
——————————————————————————————————
     48656c

When we convert the hex string “48656c” to ASCII, we get the following text, “Hel”. This takes us to step 5 from above. Because this looks like readable text, we can assume that the word “the” is in the first position of one message. If we didn’t get readable text, we would slide 48656c one position to the right and try again (and keep repeating until the end of 3c0d094c1f523808000d09).

Note that we don’t know which message contains the word “the”. It could be in either message1 or message2. Next, we need to guess what the word “Hel” is when fully expanded. It could be “Help”, “Hello”, etc. If we guess “Hello”, we can convert “Hello” to a hex string, we get “48656c6c6f”. We then XOR it with the XOR of the two cipher-texts (just like we did with “the”). Here’s the result:

     3c0d094c1f523808000d09
XOR  48656c6c6f
——————————————————————————————————
     7468652070

“7468652070”, when converted to ASCII, is “the p”. We then repeat the process, guessing what “the p” might be when expanded and then XOR that result with the XOR of the cipher-texts. Granted, guessing what “the p” might expand to is not super easy, but you get the idea. If we were to guess “the program”, convert it to a hex string, and XOR it with the XOR of the cipher-texts, we’ll get “Hello World”.

This is called crib dragging. My suggestion is to first try “ the ” (note the spaces before and after). Most cipher-texts that you’ll try cracking will contain that word somewhere in the text. If the result of your crib drag yields gibberish, then you can be sure “ the ” isn’t in either of the plain-text messages. So, try another commonly used English word or phrase and keep trying until the result yields something that looks like readable text. Then you can just expand your guess and keep XORing until you uncover the plain-text messages.

Answer 3

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 4

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 5

Each zero in $m_1\oplus m_2$ indicates a matching character. These are known as coincidences. The number of coincidences can possibly indicate what language they are communicating in since different languages have a different character frequency distribution. (Random data should have coincidences 1/26 of the time if using only lowercase letters, whereas English should be around 6%).

See Index of Coincidence for more information about that.

Other than that, you could XOR common words in various locations against $m_1\oplus m_2$. If the result makes sense (i.e., isn't a bunch of gibberish unprintable ASCII characters) then you found a possible match for both original plain texts at that location. With enough persistence its very possible you could extract meaningful information. You might start with a word like 'the' and go from there, and maybe score the results using an English trigram distribution.

Answer 6

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) \oplus f(b) = a \oplus 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 7

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.