31 views

Skip to first unread message

Sep 28, 1995, 3:00:00 AM9/28/95

to

-----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 <and...@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-----

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu