Cracking DES in under 24 hours with 256 custom DES chips
DEStiny VLSI Chip
UNIX password encryption on a tinyChip
David Ljung and Zhenyu Liu
University Of Wisconsin - Madison
DEStiny chip "photo"
click for full-size
What is it? |
Comparable Projects |
What is it?
The DEStiny chip is a hardware implementation of the UNIX crypt() function
(see `man 3 crypt`,
or take a look at the behavioral model
crypt.c or the spec [fips 46-2]
It was inspired by the fact that crypt has not been implemented in hardware
(at least publicly) before. The speedup was tremendous, which gave strength
to one of the points of the paper, that UNIX password encryption is no longer
safe. Examples are given in the paper of possible cost structures that can
crack passwords in a reasonable amount of time. The papers we wrote for
the class are below.
To disprove statements such as this:
The Threat of the DES Chip|
Chips to perform the DES encryption are already commercially
available and they are very fast. The use of such a chip speeds
up the process of password hunting by three orders of magnitude.
To avert this possibility, one of the internal tables of the DES
algorithm (in particular, the so-called E-table) is changed in a
way that depends on the 12-bit random number. The E-table is
inseparably wired into the DES chip, so that the commercial chip
cannot be used. Obviously, the bad guy could have his own chip
designed and built, but the cost would be unthinkable."
- "Password Security: A Case History" by Morris and Thompson (1979)
I wanted to demonstrate that DES was no longer strong enough.
And I enjoy a challenge. ("the cost would be unthinkable"?? :)
A custom VLSI encryption chip is described. The
chip is designed in 2.0 um CMOS technology with two levels of
metalization and 5.0 V power requirements. The active die size is 1800
x 1820 um and contains 5800 transistors. The chip provides a
hardware implementation of the UNIX crypt() algorithm. It requires
400 cycles at 17 ns per cycle to complete the calculation, plus 8
cycles for simultaneous input and output. This achieves an entire
encryption in under 7 us, an entire two orders of magnitude than
previously possible (using software).
"..For example, assuming that a password is constructed of
only alphanumeric characters (as the majority are), then
a single DEStiny chip could find any 8 character password
in 228 days. This is now plausible, as compared to 9 years
through software. Exploiting parallelism, a bank of 256
DEStiny chips can crack any such password in less than 1 day,
with the average time being 11 hours..."
The original documents were on an old pre-OSX Macintosh. I've converted
them to rtf, and made an attempt to convert to latex (though it seems the
images were lost - I don't know if they're still in the rtf or not).
You can get the rtf from this list, or go to the directory for each paper
and get the latex files and/or .dvi output.
- 1993: (design only) - approx 75 times slower:
Just found this out, thanks to the PGP documentation:
(perhaps we should have done a better job of publishing our results :)
The Federal Data Encryption Standard (DES) used to be a good
algorithm for most commercial applications. But the Government never
did trust the DES to protect its own classified data, because the DES
key length is only 56 bits, short enough for a brute force attack.
Also, the full 16-round DES has been attacked with some success by
Biham and Shamir using differential cryptanalysis, and by Matsui
using linear cryptanalysis.
The most devastating practical attack on the DES was described at the
Crypto '93 conference, where Michael Wiener of Bell Northern Research
presented a paper on how to crack the DES with a special machine. He
has fully designed and tested a chip that guesses 50 million DES keys
per second until it finds the right one. Although he has refrained
from building the real chips so far, he can get these chips
manufactured for $10.50 each, and can build 57000 of them into a
special machine for $1 million that can try every DES key in 7 hours,
averaging a solution in 3.5 hours. $1 million can be hidden in the
budget of many companies. For $10 million, it takes 21 minutes to
crack, and for $100 million, just two minutes. With any major
government's budget for examining DES traffic, it can be cracked in
seconds. This means that straight 56-bit DES is now effectively dead
for purposes of serious data security applications.
EFF DES Cracker
has actually built a DES
(and in fact, can crack DES ciphered plain text).
It used 1856 custom chips controlled by a PC and would take 9 days at most
to crack a password. Still slower than ours by, but to be fair they probably
had more control builtin to the chips which we did not have space for.
David Ljung Madison