Re: Cracking RC4/40 for massive wiretapps

Wait a minute: RC4 is an OFB cipher.  The previous plaintext has no 
effect on the ciphertext.  Hence, an attacker with shitloads of 
storage capacity can generate some initial output for each key and 
test each pre-stored key against ciphertext for possible hits.  Using 
'flaws' in the key schedule (esp. if the key is based on a password 
rather than a hash of a password) one could search for 'more likely 
keys' first.

Rob
---
No-frills sig. Befriend my mail filter by sending a message with the subject "send help"
Key-ID: 5D3F2E99 1996/04/22 wlkngowl@unix.asb.com (root@magneto)
Send a message with the subject "send pgp-key" for a copy of my key.

RC4 is a stream cypher, so it produces a random stream which is XOR'd
with the plaintext to produce the cyphertext (and vice versa).  With the
old SSL there were spots of known plaintext, but I don't know if that is
the case now.  If you do have some, then you can recover the output of
the cypher.

5 bytes (40 bits) of output should generally determine the key.  So you
could build a massive lookup table indexed by the output which produces
the key.  This would have 2^40 entries (indexed by output values) each
of which was 5 bytes long (key values).  This would take approximately
5K gigabyte disks plus some PC's to attach them to.  Total cost, one to
a few million dollars, perhaps a bit less if you get them wholesale!
(The task of constructing the table is left as an exercise for the
reader.)

Then given that you know output you can quickly find the key.  No
search is involved, you just go to the PC which holds the range of
output values you are interested in, and do a single disk access.

Note that the known plaintext doesn't have to be contiguous, any five
bytes will do.  With fewer known bytes you can do a similar thing but
have a list of possible keys which can generate that set of output
bytes.

Hal

When I wrote my previous message about the use of lookup tables, I forgot
about the use of salt, extra key bits which vary per message and are sent
in the clear.  That defeats the table lookup approach for searching for
messages which were encrypted with a given key.  There are really 128 key
bits per message, with 40 of them kept secret.

Hal