In stream cipher, how can an attacker get m1 m2 if he knows (m1 xor m2)?

Question

We know that in stream cipher c = m xor G(k). And if the key was used more than once, the attacker can get

• c1 = m1 xor G(k)
• c2 = m2 xor G(k)

Then he knows c1 xor c2 = m1 xor G(k) xor m2 xor G(k) = m1 xor m2.

So with the knowledge of (m1 xor m2), how can the attacker get to know m1 m2?

Answer 1

As you say: c1 xor c2 = m1 xor m2 if k is the same.

In this equation you must know m1 or m2 to recover the other.

In real life, note that m1 or m2 are not pseudo random string like G(k). They may be predictable or easy to guess the content. For example, m1 and m2 are both an English sentence or m1 and m2 are both a header of some protocols.

Answer 2

I'll give a very simplified example. Suppose the messages are only 1 bit and independently chosen from the following distribution:

P(m=0) = .4
P(m=1) = .6

Then, we can calculate the joint distribution of two messages m1 and m2:

P(m1=1, m2=1) = .36
P(m1=1, m2=0) = P(m1=0, m2=1) = .24
P(m1=0, m2=0) = .16

Then, consider x = m1 xor m2. We have:

P(x=0) = P(m1=1, m2=1) + P(m1=0, m2=0) = .52
P(x=1) = .48

P(x=0|m1=1) = P(m2=1) = 0.6
P(x=0|m1=0) = P(m2=0) = 0.4
P(x=1|m1=1) = P(m2=0) = 0.4
P(x=1|m1=0) = P(m2=1) = 0.6

Thus, we can calculate the posterior distribution of m1 given x using Bayes' theorem:

P(m1=1|x=0) = P(x=0|m1=1) * P(m1=1) / P(x=0) = .6 * .6 / .52 = 9/13 (.692)
P(m1=0|x=0) = P(x=0|m1=0) * P(m1=0) / P(x=0) = .4 * .4 / .52 = 4/13 (.308)

P(m1=1|x=1) = P(x=1|m1=1) * P(m1=1) / P(x=1) = .4 * .6 / .48 = .5
P(m1=0|x=1) = P(x=1|m1=0) * P(m1=0) / P(x=1) = .6 * .4 / .48 = .5

In other words, if x=0, we adjust our initial 60%/40% estimate to say it is even more likely that the message was 1. If x=1, we adjust our initial estimate to say both messages are equally likely. In both cases, the new estimate is better than the initial 60%/40% estimate.

We don't have enough information to say for sure what the plaintext is, but some information has been gained (which doesn't happen if the key is used only once).

If the initial distribution had been 50%/50%, then the conditional probabilities would still come out as 50%/50%, so the fact that the initial distribution is skewed is important.

The same technique can also be used if more messages are known, for example:

x1 = m1 xor m2
x2 = m1 xor m3

P(m1=1|x1=0, x2=0) = P(x1=0, x2=0|m1=1) * P(m1=1) / P(x1=0, x2=0) = (.6 * .6) * .6 / .28 = 27/35 (.771)

If we have a large number of independent messages, and thus a large number of x variables, we can say that x will probably take one of 0 and 1 about 60% of the time and the other about 40% of the time. If x favors 0, then probably m1=1 and vice versa.

For English text, a simple method of estimation would be to simply use an English letter frequency table as the initial distribution, and then apply this method to each letter. However, there are better models of English that would be more complicated to apply. For example, one could take a model of English where each letter has a different frequency distribution depending on the preceding letter(s) (ie a Markov chain). By iterating the single-letter method using these conditional probabilities, one could sample from the Markov chain to discover likely plaintexts. Or, with a bit more effort, one could calculate a list of the most likely messages under this model (but note that 'greedily' taking the most likely letter at each stage would not necessarily give the most likely message overall).