Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!decwrl!labrea!glacier!jbn
From: jbn@glacier.STANFORD.EDU (John B. Nagle)
Newsgroups: sci.crypt
Subject: Design for a DES-breaker
Message-ID: <17195@glacier.STANFORD.EDU>
Date: Tue, 13-Oct-87 13:53:55 EDT
Article-I.D.: glacier.17195
Posted: Tue Oct 13 13:53:55 1987
Date-Received: Thu, 15-Oct-87 20:34:41 EDT
References: <7449@reed.UUCP-> <1409@osiris.UUCP> <289@apr.UUCP>
Reply-To: jbn@glacier.UUCP (John B. Nagle)
Organization: Stanford University
Lines: 109
Keywords: NSA, DES


     It's been 10 years since 1977, so let's rough out the design of a
brute-force DES cracker, designed to try all 2^56 possible keys for
a known-plaintext attack.  No cryptoanalytic cleverness here, just
current commercial electronics technology.

THE CHIP

     We will need a custom VLSI chip.  Our unit will contain a pipelined
DES encryptor able to perform one encryption of 64 bits into 64 bits using
a 56 bit key, registers to hold the known plaintext and cyphertext,
comparators to detect a match between the plaintext and the output of the
encryptor, and counter logic to advance the key on each unsuccesful try.
The unit halts when a comparison is succesful, indicating that the correct
key has been found.

     The chip thus explores a portion of the keyspace by itself, without
any need for communication with the outside world while running.  Only
during startup, testing, and checking for stops is communication necessary,
and the bandwidth required is quite modest.  So inter-unit communication 
is very low.  Let's use an 8-bit bus to connect the units.  Each unit
will have device registers, like an I/O device, and will be controlled
by writing values into these device registers and queried by reading
from them.

     Let's assume VLSI technology at the M68020 level; current technology,
air-cooled parts, 20Mhz clock.  Conservatively we can fit 16 units
on a chip; maybe we could do better, but let's assume 16.

     Let's package the chip in a 28-pin dual-inline package.  The wide 28-pin
package should have enough room for our chip, and it's a standard size
that can be fabricated cheaply; packaging can take place on standard
low-cost packaging lines used for RAM chips.

     We'll give the chip a pinout very similar to that of a standard
byte-wide static RAM.  Thus, we can treat it electrically like a memory
device, and address the device registers as memory.

     The chip will not generate interrupts, since it looks like a RAM.
But it will have a device register which indicates whether any unit
has stopped with a match.  This register must be polled periodically
to see if a solution has been found.

     So that's our chip.  Each chip can try 20Mhz x 16 keys per second,
or 320 x 10^6 keys per second.

THE BOARD

     Since our chip looks like a RAM chip, our board will look like a
memory board, a large array of densely packed sockets and some modest
interface electronics to the rest of the world.  Let's assume Eurocard
packaging, with 9U-high extra-deep cards, similar to those used in SUN
machines.  We can fit 128 chips on such a board, and still have room for
some interface electronics.  For the sake of convenience, let's make
our board look like a memory board on a VMEbus, using the 16-bit
VMEbus interface.  The board is a pure bus slave, and does not generate
interrupts; it must be polled to determine when a find has been made.

     So our board is about 15 inches square, and can try 128 x 320
x 10^6 keys a second, or 4 x 10^10 keys per second.  There are about
7.2 x 10^16 possible DES keys, so one board can break a key in about
2 x 10^6 seconds, or about 500 hours.  On the average, one would find
the key after searching half the keyspace, so 250 hours, or about 10
days, is a reasonable estimate for a one-board system.

THE SYSTEM

      A practical system needs to be a bit larger.  A 20-slot Eurocard
cage, with 19 slots of custom cards and some standard 68000-based VME
processor and memory card in the last slot for control, would be
a useful configuration.  Equipped with fans and power supplies of
suitable size, and a 3 1/2" disk drive to provide some storage for
the control machine, the entire system should fit in a 48-inch rack.
At least two async ports should be provided, one for a control terminal
to sit on top of the rack, and one for connection to a larger system.
Software would be quite modest; some simple M68000 operating system
without memory protection, such as M-DOS, or even CP/M 68K, would
be sufficient.  Alternatively, one could use a "PC-on a VME card"
board and run MS-DOS, which would simplify software development.

      One job of the software is to test all the units periodically.
Since each unit is independently addressable, and each can be started
on a test problem separately, the test system simply loads up each unit
with a known test problem which should result in a stop within a few
seconds, and checks back after an interval to see if the unit properly
found the solution.  Any unit which fails is reported and not used again.

      Failures during operation can be handled gracefully without difficulty.
During runs, the system should stop all units every ten minutes or so, save the
current key values they are working on, check them against what they were
loaded with, mark as dead any units with incorrect values, and run the
test sets, again marking any failed units as down.  Units still up
are reloaded with their key values and restarted.  The aborted
searches are rerun later on other units of the array.  Unit failure
is thus not a serious problem. 

CONCLUSION

     A DES-breaking machine of modest size and complexity is well within
the current state of the art.  While it would be necessary to develop 
one specialized VLSI chip, everything else is available off-the-shelf
in commercial-grade electronics.  The VLSI chip required is well within
the capabilities of many fabricators and would not require any exotic
technology.  Development costs are difficult to estimate, but should
comparable to those of developing a new and complex graphics board for
a commercial microcomputer.  Total manufacturing costs for a complete
system should not exceed $250K in quantities of 10.

					John Nagle