Cracking RC4/40 for massive wiretapps
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!
Bill Stewart <stewarts@ix.netcom.com> writes:
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 known plaintext attack on pure RC4 this would work marvelously, should get close to linear speed up I think as the greatest overhead is the key setup. This was discussed some during the netscape SSL break, it didn't apply to 40 bit SSL because it was really 128 bit, just with 88 bits disclosed, so the 88 bits functioned as a salt. But it applies just fine to pure RC4-40, ... or even to ECB DES... This is interesting as applied to DES, does anyone have any banking or funds transfer protocols handy which use DES in ECB mode :-) Perhaps we could get DES down to a manageable number of bits, together with the argument that the attacker wouldn't care who's money he stole.
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.
Thinking of software attacks and RC4-40, if you were attacking pure RC4-40, you would collect your 16k known-plaintext / ciphertext pairs, xor them, and sort the xored texts and store them in some kind of dictionary lookup structure . Then you'd do the key schedule, then traverse the btree with each byte that the RC4_encrypt_byte would have xored with the text being encrypted. As soon as you took a branch which didn't exist in the btree you'd move on to the next key and keyschedule. [hacking interlude] I got bored so I hacked up a test of this of the overheads of lookups, using bsearch under linux I get lookups / sec against number of known plaintexts: known plaintext/ ciphertext actual avg time to pairs lookups/s keys/s keys/s find a key ======================================================== 16k 71k 23k 376M 24 mins 8k 77k 24k 193M 48 mins 4k 91k 25k 101M 1.5 hrs 2k 100k 25k 52M 2.9 hrs 1k 125k 27k 27M 5.6 hrs 1 - 34k 34k 187 days The tests were done on an AMD 486 dx/4 120 (a 120Mhz i486 clone), the keys/s for pure rc4-40 are from a hand optimised assembly version which I'd been playing with. `actual keys' is the keys from the search space of 2^40. `lookups/s' is the number of bsearches per second for the given sized pre-xored table. (Known plaintext xored with ciphertext allows the check for correct key to be done with memcmp). `keys/s' is the number of keys tested at once * the actual keys/s `avg time..' is the expected time before find a key. So based on one machine, if you had 1000 known plaintexts, you would get a key in around 5 hours. Multiply by 100 machines, some faster some slower and it gets interesting. Our only problem now is to find someone dumb enough to use pure RC4-40, Adam -- #!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj $/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1 lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)
In article <199608010603.XAA19276@toad.com>, Bill Stewart <stewarts@ix.netcom.com> wrote:
When we discussed using FPGA machines to crack RC4/40 last year, someone calculated the cost of cracking a message at 8 cents
That was the keylength paper. I think their estimate is way off. But that's ok-- I do so like the ring of ``8-cent encryption'', even if I think the derivation is technically dubious :-)
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,
Not with SSL. SSL uses a random 88-bit salt which is different for every session. This attack doesn't work. Fun to think about, though, eh? :-) [ Unsalted 40-bit RC4 is super-dangerous, and there are all sorts of nasty games one can play with it. That's why you should avoid it. ]
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.
Same deal. Keep those ideas flowing-- one of 'em is bound to work. -- Dave Wagner
participants (3)
-
Adam Back -
Bill Stewart -
daw＠cs.berkeley.edu