DEStiny VLSI Chip UNIX password encryption on a tinyChip David Ljung and Zhenyu Liu University Of Wisconsin - Madison 1994

DEStiny chip "photo" click for full-size

Cracking DES in under 24 hours with 256 custom DES chips

Menu: What is it? | Abstract | Consequence | Papers | Comparable Projects | Contact

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..."

• Paper [rtf] [dir]
• class Progress Report [rtf] [dir]
• Project Proposal [rtf] [dir]

• 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.

• 1998: EFF DES Cracker

  Cryptography research has actually built a DES hardware cracker (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.

Contact