Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!nbires!vianet!devine
From: devine@vianet.UUCP (Bob Devine)
Newsgroups: sci.crypt
Subject: Re: Design for a DES-breaker
Message-ID: <247@vianet.UUCP>
Date: Thu, 15-Oct-87 22:44:00 EDT
Article-I.D.: vianet.247
Posted: Thu Oct 15 22:44:00 1987
Date-Received: Sat, 17-Oct-87 10:51:02 EDT
References: <7449@reed.UUCP-> <1409@osiris.UUCP> <289@apr.UUCP> <17195@glacier.STANFORD.EDU>
Organization: Western Digital, Boulder Tech Ctr
Lines: 48
Keywords: NSA, DES
Summary: using off-the shelf chips...

In article <17195@glacier.STANFORD.EDU>, jbn@glacier.STANFORD.EDU (John B. Nagle) writes:
>      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.
> 
> Each chip can try 20Mhz x 16 keys per second, or 320 x 10^6 keys per second.
> [...]
> our board 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. (10 days)
> [...]
> Total manufacturing costs for a system should not exceed $250K in
> quantities of 10.

  I'm no EE, but, I doubt that you could come up with a chip that can
calculate a new DES value per clock-cycle even with a lot of pipelining.
And putting 16 processing units on a single chip sounds to me like it
will be Rev Z before all bugs are worked out.  Yes it might be possible
but not for the price you gave.  [But then, that's why we give the CIA
billions of bucks every year...]

  An off-the-shelf approach would be to take an existing DES chip (our
parent company has a 6 MHz chip for under $20) and gang them on a board
with some controller and fast memory.  Using a large number, say 1K,
of processors for a system, it looks like the key search would take:

1. each chip calculates and compares = 7.2 * 10^16 keys / 1K chips
                                     ~=  5 * 10^13 keys / chip
2. assume "average" number of searches needed ~= 2 * 10^13 keys/chip
3. each calc/comp iteration takes (reasonable guess?) 100 microseconds
   [if someone wants, I can get the exact figure]

4. Time until average solution = 2 * 10^13  *  10^-4 seconds
                               = 2 * 10^9 seconds
                               ~= 60 years

  So, unless someone sees a problem with my calculations, a DES cracker
would need about 1000 such systems to bring the time down into the
range of months.  I'd guess that the cost per system is approximately
$20K for the DES chips plus $30K for the "glue" chips for $50K per box.

  To speed this up an obvious path to choose is a faster DES chip. 
There may be some on the market now it's just that I had the press
release for the WD20C03 chip in my file.

Bob Devine
[ BTW, 7.2 * 10^16 == 72 quadrillion ]