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