Re: Time to exhaustively break 40-bit RC4?

[eric@remailer.net (Eric Hughes)]

   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