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
participants (2)
-
Deranged Mutant -
Hal