Cryptanalysis: XOR of two plaintext files

Question

I have a file which contains the result of two XORed plaintext files. How do I attack this file in order to decrypt either of the plaintext files? I have searched quite a bit, but could not find any answers. Thanks!

EDIT:

Well, I also have the two ciphertexts which i XORed to get the XOR of the two plaintexts. The reason I ask this question, is because, according to Bruce Schneier, pg. 198, Applied Cryptography, 1996 "...she can XOR them together and get two plaintext messages XORed with each other. This is easy to break, and then she can XOR one of the plaintexts with the ciphertext to get the keystream." (This is in relation to a simple stream cipher) But beyond that he provided no explanation. Which is why I asked here. Forgive my ignorance.

Also, the algorithm used is a simple one, and a symmetric key is used whose length is 3.

FURTHER EDIT:

I forgot to add: Im assuming that a simple stream cipher was used for encryption.

If you can accomplish it without knowing anything about either of the two files to start with, I'm sure there's a job waiting for you at the NSA or similar orgs. — Marc B
"How do I attack this file in order to decrypt either of the plaintext files?" - one nice thing about XOR crypto is that once you've decrypted one of the plaintexts, you'll have no problem decrypting the other one. — Michael Burr
By definition of XOR, you transform 2 bites of information into 1 bit of information. So you loose half the information. You can't hope to obtain both the files out of the XOR. — Cristian Vrabie
@Cristian Vrabie: Sure you can, as long as there's sufficient redundancy in the two original files. English text, for example, has more than enough redundancy for this to be feasible. — caf

Michael Burr Michael Burr · Accepted Answer · 2011-04-14T22:31:15

I'm no cryptanalyst, but if you know something about the characteristics of the files you might have a chance.

For example, lets assume that you know that both original plaintexts:

contain plain ASCII English text
are articles about sports (or whatever)

Given those 2 pieces of information, one approach you might take is to scan through the ciphertext 'decrypting' using words that you might expect to be in them, such as "football", "player", "score", etc. Perform the decryption using "football" at position 0 of the ciphertext, then at position 1, then 2 and so on.

If the result of decrypting a sequence of bytes appears to be a word or word fragment, then you have a good chance that you've found plaintext from both files. That may give you a clue as to some surrounding plaintext, and you can see if that results in a sensible decryption. And so on.

Repeat this process with other words/phrases/fragments that you might expect to be in the plaintexts.

In response to your question's edit: what Schneier is talking about is that if someone has 2 ciphertexts that have been XOR encrypted using the same key, XORing those ciphertexts will 'cancel out' the keystream, since:

(A ^ k) - ciphertext of A
(B ^ k) - ciphertext of B

(A ^ k) ^ (B ^ k) - the two ciphertexts XOR'ed together which simplifies to:

A ^ B ^ k ^ k - which continues to simplify to
A ^ B ^ 0
A ^ B

So now, the attacker has a new ciphertext that's composed only of the two plaintexts. If the attacker knows one of the plaintexts (say the attacker has legitimate access to A, but not B), that can be used to recover the other plaintext:

A ^ (A ^ B)
(A ^ A) ^ B
0 ^ B
B

Now the attacker has the plaintext for B.

It's actually worse than this - if the attacker has A and the ciphertext for A then he can recover the keystream already.

But, the guessing approach I gave above is a variant of the above with the attacker using (hopefully good) guesses instead of a known plaintext. Obviously it's not as easy, but it's the same concept, and it can be done without starting with known plaintext. Now the attacker has a ciphertext that 'tells' him when he's correctly guessed some plaintext (because it results in other plaintext from the decryption). So even if the key used in the original XOR operation is random gibberish, an attacker can use the file that has that random gibberish 'removed' to gain information when he's making educated guesses.

Cryptanalysis: XOR of two plaintext files

5 Answers