From: tcmay@netcom.com (Timothy C. May)
Date: Sat, 16 Apr 94 18:44:25 PDT
To: cypherpunks@toad.com
Subject: Table of Key Lengths and Brute Force Cracking Times
Message-ID: <199404170145.SAA28011@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



Here are some numbers from Bruce Schneier's article in the April 1994
"Dr. Dobb's." The article is a review of the "Cambridge Algorithms
Workshop," where Bruce also presented a paper on Blowfish.

These estimates are in a slightly different form than what "Applied
Cryptography" has (on pp. 130-135), and incorporate (apparently) the
Michael Wiener DES-busting estimates from last summer.

First, some typical key lengths for block ciphers, as reported by
Schneier:

Algorithm		Key	Block	Problems/Comments

DES			56	64	key too small
Triple DES (3DES)	112	64	slow
Khufu (Merkle/Xerox)	64	64	patented, key too small
FEAL 32			64	64	patented, key too small
LOKI-91			64	64	weaknesses, key too small
REDOC II		160	80	patented
REDOC III		variab. 64	patented
IDEA (Europe)		128	64	patented
RC2 (RSADSI)		variab. 64	proprietary
Skipjack (NIST/NSA)	80	64	secret algorithm
GOST (FSU, Russia)	256	64	not completely specified
MMB			128	128	insecure

The "problems" reported are exactly as reported by Schneier. No
mention of RC4, which may in "exportable" versions may be as short as
40-45 bits.

Second, some estimates of brute-force cracking time:

Key Length	Time for a $1M		Time for a $1B ($1000M)
		Machine to Break	Machine to Break

40		0.2 second		0.0002 sec
56		3.5 hours (Wiener)	13 sec
64		37 days			54 minutes
80		2000 years		6.7 years (2 years?)
100		7 billion years		7 million years
128		10^18 			10^15 years
192		10^37 years		10^34 years
256		10^56 years		10^53 years


Note that a billion dollar cipher-busting machine is not out of the
question. Norm Hardy once described to us the $100M "Harvest" machine
(also described by Bamford). NSA has its won on-site wafer fab
facility (built by National Semiconductor several years back).

A single Space Shuttle launch costs around a billion dollars (NASA
says $0.6B, GAO says $1.5B), and many of the launches are just put up
reconnaisance and SIGINT satellites, so spending $500M to $1B on
special computers to crunch the data seems plausible. (However, it's
hard for NSA to make plans for what key length they'll have to target.
It's also not clear that enough non-financial users have been using
DES to make it "necessary" for such large expenditures....a single
machine that can crack a DES-encrypted message in, say, 1-10 hours may
be enough for their current needs. All of this is just speculation.)

For logistical and other reasons, I would expect they may have
_several_ smaller machines. Just as effective, of course,
cumulatively.

Obviously a billion dollars worth of hardware will not be dedicated
for a couple of years to crack a single 80-bit cipher.

Anyway, you all can fool with these numbers and draw your own
conclusions.

Ron Rivest did some similar calculations for RSA modulus sizes and
came to similar conclusions (e.g., 1200-bit modulus will withstand
even attacks by billion-dollar machines for several more decades).

--Tim May

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."