Path: cactus.org!news.dell.com!swrinde!howland.reston.ans.net!Germany.EU.net! + news.dfn.de!gs.dfn.de!gwdu03.gwdg.de!slucks From: slucks@gwdu03.gwdg.de (Stefan Lucks ) Subject: XOR of plaintexts was: Doing Better than XOR in RC4-like Algorithms Message-ID:Organization: GWDG, Goettingen References: <3a7llc$kej@netaxs.com> Date: Tue, 15 Nov 1994 08:13:21 GMT Lines: 53 soneill@unix3.netaxs.com (Steve O'Neill) writes: >In article > farid@netcom.com (Farid F. El-Wailly) writes: >>If the same key is used to encrypt two files then cryptanalysis is >>trivial due to the nature of the exclusive-or. You can cancel out >>the random sequence by XORing the two cyphertexts together. >Unless I'm mistaken, this makes the cryptanalysis easier, but not trivial. I agree: The cryptanalysis of two xored plaintexts is not trivial. >When you XOR the two ciphertexts together, what you wind up with is the XOR >of _both_ plaintexts, which, unless you know one of them, doesn't help you >very much. Known or chosen plaintext attacks can use this effect, but, in >the general case, it won't do anything to simplify the analysis. It seems to be difficult to decrypt both plaintexts completely. But if you know the topics, the plaintexts deal with--or at least the language they are written in--you are able to discover large fractions of the plaintexts. You start with some text-fractions, which you expect to find in at least one of the plaintexts. These are called probable words. In the case of any English texts this might include " the ", " this ", " does ", ... (the spaces help to increase the size of the probable words). At each character position decrypt your text with the given probable words. You can expect to find a small number of pairs (P,W)=(character position, probable word), where the text at position P decoded with W looks like a fraction F of an English text. For F you try to guess some following characters F1 and some preceeding characters F0. I.e. if F is "do an", one choice for F0 might be "to "; reasonable choices for F1 might be " a", " e", " i", " o", " u", "y ", or "ything". Use F0 and F1 to decode your ciphertext at the appropriate positions. If what you find does look like English text, you probably have guessed right. Then guess again and repeat until you can't make any more reasonable guesses. This attack works the better, the longer the probable words are. Therefore it is good to know the topics of at least one of the plaintexts. I.e. if the plaintext(s) deal with cryptography, you can try long probable words like "cipher", " ciphertext", " plaintext", " cryptanalysis", ... Natural languages like English (French, German, ...) are so redundant, that one can find out large fractions of the plaintexts when given only the xor of two plaintexts. If the plaintexts are (or one of them is) compressed, things become more difficult. Stefan -- Stefan Lucks Institut f"ur Numerische und Angewandte Mathematik, Lotzestra\3e 16-18, 37083 G"ottingen, Germany e-mail: lucks@namu01.gwdg.de (oder slucks@gwdu03.gwdg.de) Wer einem Computer Unsinn erz"ahlt, mu\3 damit rechnen.