Be the first on your block!
Michael Wiener 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
