Cracking RC4/40 for massive wiretapps

[Bill Stewart <stewarts@ix.netcom.com>]

At 11:13 AM 7/30/96 -0700, frantz@netcom.com (Bill Frantz) mused paranoidly:
>I combine the above with Whit Diffie's observation that, while crypto users
>are interested in the security of *each* message, organizations which
>monitor communications want to read *every* message.  A TLA interested in
>monitoring communications would need to crack RC4-40 much faster than
>1/week.

When we discussed using FPGA machines to crack RC4/40 last year,
someone calculated the cost of cracking a message at 8 cents
if you're doing enough to amortize your machine, and Eric had designed
a system that should be able to crack it in about 15 minutes for $25-50K.
The two basic search approaches are to take a cyphertext and decrypt it
trying many keys to see if you get a likely plaintext, or to take known
plaintext and encrypt with many keys to see if you match the cyphertext.

But those designs are for one-at-a-time cracks.  An interesting question
is whether you can speed up performance substantially by cracking
multiple messages at once.  For instance, if you've got known plaintext,
such as a standard header format saying "FooVoice" or "BEGIN DSA-SIGNED..",
you can try many keys and compare them with _many_ cyphertexts,
which may not slow down the FPGA very much.  Also, even for
unknown-plaintext, since key scheduling is a relatively slow part of RC4/40,
you can split the key-schedule and the block-encryption phases, feeding
one keyschedule output to multiple decrypt-and-compare sessions in parallel.
So the cost per victim of cracking many sessions may be much lower.

>Now expensive specialized cracking equipment can certainly speed up the
>process, but there may be a better way.  If cryptanalysis of RC4 yields
>techniques which make the process much easier, then it is the ideal cypher
>to certify for export.
>The paranoid conclusion is that there is a significant weakness in RC4.

Just keeping the key length down to 40 bits on a fast cypher is a good start.

#			Thanks;  Bill
# Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com
# <A HREF="http://idiom.com/~wcs"> 
#			Dispel Authority!