Newsgroups: sci.crypt Path: cactus.org!news.dell.com!swrinde!pipex!uunet!news.sprintlink.net!crash! + straits From: straits@crash.cts.com (Stewart Strait) Subject: Re: Doing Better than XOR in RC4-like Algorithms Organization: CTS Network Services (CTSNET), San Diego, CA Date: Tue, 15 Nov 1994 06:55:54 GMT Message-ID:X-Newsreader: TIN [version 1.2 PL2] References: <3a7llc$kej@netaxs.com> Sender: news@crash.cts.com (news subsystem) Nntp-Posting-Host: crash.cts.com Lines: 24 Steve O'Neill (soneill@unix3.netaxs.com) wrote: : Unless I'm mistaken, this makes the cryptanalysis easier, but 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. I believe you're mistaken. An unknown plaintext attack is to consider short pieces, say 8 to 24 bits long, of the ciphertext. For each value of plaintext 1, compute plaintext2=plaintext 1 XOR ciphertext. Now find the product of the assumed normal frequencies of the two plaintexts. Make a table of the plaintext pairs with highest frequency products. Go on to the next short piece. After you finish a few tens of bytes, try to string together some of the plaintext pairs into sensible text (in both plaintexts). If the redundancy of both plaintexts is typical, that is, much over 50%, and the attacker's model captures the bulk of the redundancy, this should work. There will be short sections of text left in doubt because of momentary low redundancy. With mod 26 addition instead of XOR the problem you discuss becomes routine hobbyist stuff if a single word of known plaintext is given, without its position in the message. XOR should not make things much different. You may want to look under 'running key' in the index of _Cryptanalysis_, by Helen Gaines (Dover) (p. 143 in my copy).