Time to exhaustively break 40-bit RC4?

[Raph Levien]

Ian Farquhar <ianf at 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