From: Andrew Roos <andrewr@vironix.co.za>
Date: Thu, 28 Sep 95 07:28:45 PDT
To: cypherpunks@toad.com
Subject: Cryptanalysis of RC4 - Preliminary Results
Message-ID: <9509281628.aa25754@herman.vironix.co.za>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

Hi c'punks & sci.cryptites


About a week ago I posted a message about weak keys in RC4. This is 
an update on the results of my continued 4am sessions with RC4 and 
shows that certain weak keys lead to an almost-feasible known 
plaintext attack on the cipher (well, about as feasible as the 
differential attack on DES, shall we say).

The attack is based on two particularly interesting three-byte key 
prefixes which have a high probability of producing PRNG sequences
which start with a known two-byte sequence. The prefixes are:

1.  Keys starting with "00 00 FD" which have a 14% probability of 
    generating sequences which start "00 00".

2.  Keys starting with "03 FD FC" which have a 5% probability of
    generating sequences which start "FF 03".

Note that the expected frequency of any two-byte output sequence is 
1 in 65536 or about 0.0015%, so these key prefixes are highly 
unusual. I won't go into the reasons why in this post, since it 
follows the same reasoning as my last post, but these prefixes are
special in that they have a high probability of initializing the RC4 
state table in such a way that the first two generated bytes depend 
only on the first three entries in the state table.

This observation is the basis for a simple known-plaintext attack
which reduces the effective key space which you need to search to
have a 50% probability of discovering a key by about 11.2 bits. The 
down side is that you need "quite a few" known plaintexts to make the 
attack feasible. 

It works as follows:

1.  Collect a large number of known plaintexts (and hence known 
    generator sequences).

2.  Discard generator sequences which do not start with "00 00" or 
    "FF 03".

3.  For generator streams starting "00 00", search all keys which
    begin with "00 00 FD".

4.  For generator streams staring "FF 03", search all keys which
    begin with "03 FD FC".

5.  Keep going until you find a key :-)

Clearly this attack will only discover a small fraction of the keys.
However since most generator sequences are discarded without being 
searched, and for those which are searched the search is 2^24 smaller 
than would be required to search the entire keyspace, the number of 
trials required to determine a key is significantly lower than for 
brute force alone.

Enough of an intro, here are the relevant results. Forgive my 
simplistic approach to maths, I'm a philosopher-come-software 
developer, not a mathematician. I've run the relevant simulations 
with 40-bit, 64-bit, 80-bit and 128-bit key lengths, and with two
different PRNGs. For the sake of consistency with my earlier paper 
I'll use the figures gathered for 80-bit keys (this seems to be RSA's
preferred key length for RC4), but there are no significant 
differences for other key lengths. The PRNG used for these tests was 
L'Ecuyer's 32-bit combined linear congruential generator as described 
in "Applied Cryptography" p. 349.

(a) Out of one million trials, keys starting with "00 00 FD" 
    generated sequences starting "00 00" 138217 times, and keys 
    starting with "03 FD FC" generated output sequences starting "FF 
    03" 50490 times.

(b) Out of ten million trials, arbitrary pseudo-random keys generated
    sequences starting with "00 00" 446 times, and sequences starting
    with "FF 03" 146 times. (Note the abnormally high incidence of 
    "00 00"; the expected mean is 152.8).

Suppose we have the output stream generated by a randomly chosen key.
The chance that it will start with either "00 00" or "FF 03", and 
that we will therefore search it, is:

    (446 + 146) / 1e7 = 5.92e-5

The chance that it starts with "00 00" and was generated by a key 
starting with "00 00 FD", or that it starts with "FF 03" and was 
generated by a key starting "03 FD FC" - i.e. the chance that we will
search it and be rewarded for our efforts - is:

    (138217 + 50490)/(1e6 * 2^24) = 1.12e-8

The total number of plaintexts required for a 50% chance that we will
discover one of the keys is:

    log(0.5)/log(1 - 1.12e-8) = 61 900 000

Well I did say "quite a few" plaintexts would be necessary :-) 

And the number of plaintexts which you expect to search in order to 
find the "right" one is:

    61 900 000 * 5.92e-5 = 3665

Since the total key length is 80 bits, and we are "guessing" 24 of 
these, each search requires 2^56 trials. Hence the total number of 
trials for a 50% chance of discovering a key is:

    3665 * 2^56 = 2.64e20 = 2 ^ 67.8

Since brute search alone would require 2^79 trials for a 50% chance 
of determining the key, this reduces the number of trials by 2^11.2.

The results are essentially identical for all the key lengths I have
tried, and in each case reduce effective key length by about 11.2 
bits. So, for example, a 64-bit key would normally require 2^63 
trials for 50% chance of solution; this attack reduces the number of
trials to 2^51.8 at the cost of requiring 62 million known plaintexts.

I'm still running simulations to check my maths, and although initial
results are encouraging, I don't have enough data for it to be
statistically relevant yet (generating all these sets of 62 million 
known streams takes time...) So consider this preliminary (again),
and I'll post the results of my simulations when I have enough 
data.


Andrew

________________________________________________________________
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


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2i

iQCVAwUBMGrlfmatuqa4OR+lAQF1eQP+IBBmSztAYUpq1q/BjzvYDCbb+Ns0Gi1S
u9wTaZOCl32fdp7NSUEQBX39nVJkQZginug56BZXzijRvOx6fl4+z7dmW9jwtE5E
YNCOhx+/fHX4psszMyEUTrnza7MYDc4HXlgv743LOD/xvEyU0D5OGgB5fg+lyhAK
6xQ/Zy8JpE8=
=BdMn
-----END PGP SIGNATURE-----