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).