From: gnu (John Gilmore)
Date: Thu, 9 Sep 93 16:17:27 PDT
To: pem-dev@tis.com
Subject: Crack DES in 3.5 hours for only $1,500,000!
Message-ID: <9309092314.AA15000@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


Be the first on your block!

Michael Wiener <weiner@bnr.ca> produced a complete design for a DES
key search machine, which he presented in the "rump session" at Crypto '93
last month.  He designed a single custom chip which can do 50 million
test encryptions per second, and the boards and racks and frames into
which it fits.  The full design has about 60,000 copies of the chip,
solves DES in 3.5 hours, and is fully described in the paper.  Here is
an excerpt from his conclusions:	

    It is possible to build a $1 million machine that can attack DES and
    recover a key in an average time of 3.5 hours.  The machine uses a
    known plaintext to exhaustively search through the DES key space and
    could be developed for $500000 in about 10 months.  Because a great
    deal of detail has gone into the design of the key search machine, we
    can have high confidence in the assessment of its cost and speed.
    The key search design presented here is one to two orders of magnitude
    faster than other recently proposed designs.

    Even cryptosystems with 64-bit keys may be vulnerable.  If DES were
    modified to use 64-bit keys, there would be 2**8 times as many keys to
    search through, and a $10 million machine would take an average of 3.7
    days to find a key.

    It is possible to build a key search machine that can support a range
    of modes of DES with little penalty in run-time.  A $1 million machine
    would take 8 hours on average to find a key used in 1-bit CFB mode
    and 4 hours on average for any of ECB, CBC, 64-bit OFB, 64-bit CFB, or
    8-bit CFB mode.

    This work shows that exhaustive DES key search is alarmingly
    economical.  If it ever was true that attacking DES was only within
    the reach of large governments, it is clearly no longer true.  A
    fairly painless way to improve security dramatically is to switch to
    triple-DES.

The paper was written as a warning to DES users (bankers) and their
customers (depositors).  DES is used to protect electronic money
transfers among banks all over the world.  Several billion dollars per
day are moved in this way.  Within a day of finishing the machine, a
criminal could easily pay back the $1.5M in capital.  In the second
day, they'd have the capital required to build a second machine, and
in the third day a positive cash flow would begin.  Banks can do 
nothing to stop this -- if they shut down their comm links, they go
out of business; if they keep moving money over them, intruders suck
money out at will.  I recommend not keeping your money in banks...

Most organizations who would build such a machine (national
governments and other forms of organized crime) have probably already
constructed many similar machines.  This paper will not help them.  It
is intended to help people who thought that DES was secure.

The full paper is available in PostScript via ftp from:

	ftp.eff.org:/pub/crypto/des_key_search.ps
	cpsr.org:/cpsr/crypto/des/des_key_search.ps

cpsr.org also makes it available via their Gopher service.

CPSR.org is on a slow link; use the ftp.eff.org archive if possible.
(The file will appear there shortly; apologies for any delay.)

	John Gilmore
	Electronic Frontier Foundation


Feel free to hack this up and send me back revised copy...

	John