1994-12-13 - Time to exhaustively break 40-bit RC4?

Header Data

From: raph@netcom.com (Raph Levien)
To: cypherpunks@toad.com
Message Hash: 3ce0c782b6cb9e53dfab0ada93795eaac00275a35f8443828f552295ebca7994
Message ID: <199412122330.PAA29185@netcom20.netcom.com>
Reply To: N/A
UTC Datetime: 1994-12-13 00:01:07 UTC
Raw Date: Mon, 12 Dec 94 16:01:07 PST

Raw message

From: raph@netcom.com (Raph Levien)
Date: Mon, 12 Dec 94 16:01:07 PST
To: cypherpunks@toad.com
Subject: Time to exhaustively break 40-bit RC4?
Message-ID: <199412122330.PAA29185@netcom20.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


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





Thread