Time to exhaustively break 40-bit RC4?

The SSL documents say that exhaustively searching 40 bits of RC4
keyspace takes 64 MIPS-years. When I brought this figure up at the
cpunks meeting, it was roundly derided. However, I think it might be a
sound estimate.

The key schedule operation in RC4 does 256 "swap" operations. Let's
say it takes four instructions to do each swap. So, it's 2000
instructions per key. A one-MIPS processor can search 500 keys a
second. There are about 30 million seconds in a year, so that's 15
billion keys a year. 40 bits is a trillion keys, so it works out to 66
years, which is well within the Pentium-style accuracy of the
calculations I've done.

Am I missing something here?

On the second floor of Soda Hall are about 100 HP Snake
workstatations. I think they're about 100 MIPS each. During the winter
break, they will be sitting mostly unused. If the math checks out,
they should be able to search keyspace in two and a half days. Anyone
wanna do some cracking?

Raph

Raph Levien says:
> The SSL documents say that exhaustively searching 40 bits of RC4
> keyspace takes 64 MIPS-years. When I brought this figure up at the
> cpunks meeting, it was roundly derided. However, I think it might be a
> sound estimate.

Its not a question of deriding the estimate...

> If the math checks out, they should be able to search keyspace in
> two and a half days.

...its a question of deriding the security of any system that takes so
little time to crack, and thats assuming there are no better attacks
than brute force (yet to be determined). With optimization, you can do
even better than that. With a little bit of hardware (not very much)
you can crack open a 40 bit keyspace with the effort normally reserved
for opening your bathroom door in the morning.

Perry

On Dec 12,  7:31pm, Perry E. Metzger wrote:
> ...its a question of deriding the security of any system that takes so
> little time to crack, and thats assuming there are no better attacks
> than brute force (yet to be determined). With optimization, you can do
> even better than that. With a little bit of hardware (not very much)
> you can crack open a 40 bit keyspace with the effort normally reserved
> for opening your bathroom door in the morning.

Actually, it's a bit more than a "little bit of hardware".  One of the
interesting realisations of pondering VLSI crackers was how much chip
real-estate storing 2048 bits of laregly static internal state required,
disregarding the size of a 2048 bit bus (remember "transistors are cheap,
wires are expensive".)   All transfers would have to be multi-cycle
operations, which adds complexity due to the need to time and synchronise
these transfers.

It's by no means impossible, but the design of such a device is
certainly not a trivial exercise in engineering, and I would never call
the result a "little piece of hardware".

							Ian.

On Dec 12,  3:30pm, Raph Levien wrote:
> The key schedule operation in RC4 does 256 "swap" operations. Let's
> say it takes four instructions to do each swap. So, it's 2000
> instructions per key. A one-MIPS processor can search 500 keys a
> second. There are about 30 million seconds in a year, so that's 15
> billion keys a year. 40 bits is a trillion keys, so it works out to 66
> years, which is well within the Pentium-style accuracy of the
> calculations I've done.

No, because as you're doing an exhaustive keysearch, you can "pipeline"
the key generation process in software.  Each key requires 256 swaps,
certainly, but there are only two swaps difference between the key
for "0000000000" and "0000000001" (assuming a 40 bit key).  If you
recursively generate keys, then you can generate successive keys
like this:

1. Copy the keystate from iteration n-1 (keep the partial keystates
   on a stack).
2. Do the swap for this portion of the key, and for 255 out of 256
   keys, you will have a new one in 2 swaps.

(In reality, it would be faster to undo the last swap rather than copying
the key, and keeping the swaps on a stack rather than the keystate on
a stack.  These are implementation issues I haven't given a huge amount
of thought to as yet.)

Unless there is some hidden complexity which I have overlooked - in which
case I will be delighted to stand corrected - this will produce a key
fast enough to allow an average workstation to search the 40-bit keyspace
using a known plaintext attack in a couple of hours or less.  If this is
the case, 40-bit RC4 might as well be crypt(1), and 48-bit RC4 looks
pretty shakey too.

I was planning to code this over the xmas break, dependent on whatever
other commitments fall on me during that period.  I realised it was possible
a couple of months ago after pondering ways of parallelising the RC4 key
generation process in hardware.

						Ian.

From: "Ian Farquhar" <ianf@sydney.sgi.com>

   No, because as you're doing an exhaustive keysearch, you can "pipeline"
   the key generation process in software.  Each key requires 256 swaps,
   certainly, but there are only two swaps difference between the key
   for "0000000000" and "0000000001" (assuming a 40 bit key).  

Not by my count.  The key data length for a forty bit key is only 5.
That means that each byte of the key data is used about fifty times in
key setup (256/5).  Those initial changes in the internal key
permutation table then propagate under iteration.

Now I haven't looked very closely at how to optimize this search, and
it's not even clear that it's possible.  There are 256! possible
permutations for the internal key, which is a lot more than 2^40
possible (external) keys.  It's quite possible that the internal keys
are just not particularly close to each other.  Close here, say, is
the minimum number of swaps needed to take one key to another.

It's possible that some arrangement other than incrementing the key
yields internal key correlations that speed up software internal key
generation.

Eric

Ian Farquhar <ianf@sydney.sgi.com> wrote:
> No, because as you're doing an exhaustive keysearch, you can "pipeline"
> the key generation process in software.  Each key requires 256 swaps,
> certainly, but there are only two swaps difference between the key
> for "0000000000" and "0000000001" (assuming a 40 bit key).  If you
> recursively generate keys, then you can generate successive keys
> like this:

This doesn't quite work. As I understand it, the RC4 key scheduling
algorithm repeats the key to fill 256 bytes. For a 128-bit key, this
is 16 times. Thus, you can only win on the last repeat. Perry also
mentioned some "optimizations" but I believe RC4 is resistant to this
sort of thing. The inner loop is about as simple as you're going to
get it.

Oh, just to clarify one point. 40-bit RC4 in fact uses a 128 bit key,
it's just that 88 bits of the key are sent in the clear.

Your idea does help in searching the 128-bit keyspace. Unfortunately,
it reduces the time needed from about 10^45 to 10^43 operations. Mazel
Tov.

Raph

-----BEGIN PGP SIGNED MESSAGE-----

"Ian Farquhar" <ianf@sydney.sgi.com> writes:

>No, because as you're doing an exhaustive keysearch, you can "pipeline"
>the key generation process in software.  Each key requires 256 swaps,
>certainly, but there are only two swaps difference between the key
>for "0000000000" and "0000000001" (assuming a 40 bit key).  If you
>recursively generate keys, then you can generate successive keys
>like this:

This is not true, for a few reasons.  First, keys are replicated
(reused over and over) until 256*8=2048 bits have been used.  So
a 40-bit key would get reused about 50 times.  Second, the key
feeds into a PRNG which is mixed in with the swapping, so once you
swap with a different one you will swap differently from then on.

And third (and this is the one I find most interesting), SSL does not
just use a 40-bit key for the export versions.  They use a 128-bit key,
but they require 128-40=88 bits to be sent in the clear.  So the
potential keyspace is much bigger than 2^40.  This will make certain
attacks (primarily those involving pre-calculation, which actually
doesn't apply to your pipeline I guess) impossible.  I thought it was
interesting that this "128 minus 88" bit key qualified for the export
approval.  This suggests that NSA has no better attack than brute force
(nothing relying on cryptographic weaknesses of 40 bit keys, for
example).

Hal

-----BEGIN PGP SIGNATURE-----
Version: 2.6

iQBVAwUBLuz/VBnMLJtOy9MBAQFMQwIAgo6XwroajnfYmRzSasstBSTKFGVeGI5U
Kbg4VBG9FU9qFJaZ6hDpFbfZhvSc8OPnK0COWuZsdEZDcl1QDuwELA==
=JCls
-----END PGP SIGNATURE-----

I notice in the Netscape SSL spec the 40-bit export-approved RC4
key generation is a little more complicated than I would have thought.
First a 128 bit "master key" is chosen and 88 bits are revealed, leaving
40 bits secret.  Then the RC4 session key is generated as the MD5 hash of
this master key plus about 32 bytes of publically known but random
information.  I'm not clear whether the 128-bit output of the MD5 hash is
then used as the RC4 key, or whether only 40 bits are used (and if so,
whether there are any public bits in the key besides these 40).

If the former, then this extra hash step should really slow down
exhaustive search of the key space.  If the latter, then it is not clear
why the master key is key-size restricted at all since it is not likely
to be used in searching the key space.  Maybe someone from Netscape could
clear up how this is done.

Hal

From: Hal <hfinney@shell.portal.com>

   I notice in the Netscape SSL spec the 40-bit export-approved RC4
   key generation is a little more complicated than I would have thought.

[The RC4 key is a hash of the external key. Are 40 or 128 bits of this
hash used?]

   If the former, then this extra hash step should really slow down
   exhaustive search of the key space.  If the latter, then it is not clear
   why the master key is key-size restricted at all since it is not likely
   to be used in searching the key space.  

It doesn't really matter, from a crack designer's point of view.  It
all depends on what keyspace you're actually searching.  You can
search either the external key (40 bit) or the internal key (larger).
Clearly you have to search the external keyspace.

In order to search the external keyspace, you have to simulate the
whole algorithm, which in this case is not _just_ RC4 but also
preliminary key setup phase.  It's just another part of the algorithm.
To make the distinction precise, what you're searching is not 40-bit
RC4 but rather 40-bit RC4-as-used-in-SSL.  The compound algorithm is
not identical to the underlying algorithm.

This is one of the design problems in Weiner's DES-cracking machine
(designed and unbuilt), that it can only crack DES as such and not
minor modifications to it.  The machine uses a little polynomial
generator (similar to using CRC) to be able to partition the keyspace
among processors and to keep the pipelines full.  This is a hard-wired
generator.

The architectural improvement needed in a practical machine would be
an interconnect for key candidate sequencing.  This would add to the
cost of the machine, but only by, say, 20% at most.  It would be
expensive as interconnects go because the bandwidth is so high.

Suppose an RC4 cracker existed with the above interconnect.  In order
to crack RC4-SSL, you'd need a second simulator that did all the
hashing and spat keys out its interconnect.  Such a front end would
have to be designed for every particular configuration used.

Eric

On Dec 17,  1:49pm, Hal wrote:
> Subject: Re: Time to exhaustively break 40-bit RC4?
> I notice in the Netscape SSL spec the 40-bit export-approved RC4
> key generation is a little more complicated than I would have thought.
> First a 128 bit "master key" is chosen and 88 bits are revealed, leaving
> 40 bits secret.  Then the RC4 session key is generated as the MD5 hash of
> this master key plus about 32 bytes of publically known but random
> information.  I'm not clear whether the 128-bit output of the MD5 hash is
> then used as the RC4 key, or whether only 40 bits are used (and if so,
> whether there are any public bits in the key besides these 40).

128 bits are used. I have cleaned up the spec language to make this more
obvious.

> If the former, then this extra hash step should really slow down
> exhaustive search of the key space.  If the latter, then it is not clear
> why the master key is key-size restricted at all since it is not likely
> to be used in searching the key space.  Maybe someone from Netscape could
> clear up how this is done.

Hopefully it will slow down exhaustive key search.

Hope this helps, and thanks again for the comments.


-- 
---------------------------------------------------------------------
Kipp E.B. Hickman          Netscape Communications Corp.
kipp@mcom.com              http://www.mcom.com/people/kipp/index.html