RE: Cryptanalysis of RC4 - Preliminary Results (Repeat)

[Andrew Roos <AndrewR@beetle.vironix.co.za>]

Hi Bill

You could check for the full three-byte prefix, which further reduces the   
number of keys you have to discard. Although all keys beginning "00 00"   
are weak in the sense of my original post, they do not appear to be as   
exploitable as the prefixes which generate two-byte probable sequences.

I also recommend generating and discarding some initial sequence bytes,   
since the generation process mixes up the state table further. An extra   
"round" through the state table (i.e. generating 256 bytes) _appears_ to   
confuse things significantly, since by the time you've generated the   
initial state table from the key, Index Y is a function of all bytes of   
the key, so the second time around it's hard to figure out the impact of   
the byte swaps. But I wouldn't trust this without a significant amount of   
analysis: as always in this field, appearances can be dangerously   
deceptive.

Of course, this defense is not possible with protocols like SSL where you   
have to follow the spec - or better still, PCT which conveniently moves   
the MAC to the *end* of the record, exposing the initial stream...

Andrew

 ----------
From:  stewarts[SMTP:stewarts@ix.netcom.com]
Sent:  29 September 1995 10:16
To:  Andrew Roos
Cc:  cypherpunks
Subject:  Re: Cryptanalysis of RC4 - Preliminary Results (Repeat)

It sounds like any application using RC4 with random session keys
should start by testing session keys and rejecting any that
start with 00 00 or 03 FD; it means doing 2**-15 more random key
generations, and reducing the brute-force space by 2**-15,
but it's a pretty small reduction.
________________________________________________________________
Andrew Roos <andrewr@vironix.co.za>

// C++ programmers have class (but not much inheritance)

PGP Fingerprint: F6 D4 04 6E 4E 16 80 59 3A F2 27 94 8B 9F 40 26
Full key at ftp://ftp.vironix.co.za/PGP-keys/AndrewRoos