Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!uwvax!uwmacc!uwmcsd1!leah!itsgw!nysernic!rutgers!bellcore!faline!karn
From: karn@faline.bellcore.com (Phil R. Karn)
Newsgroups: sci.crypt
Subject: Re: Design for a DES-breaker
Message-ID: <1477@faline.bellcore.com>
Date: Wed, 14-Oct-87 21:15:49 EDT
Article-I.D.: faline.1477
Posted: Wed Oct 14 21:15:49 1987
Date-Received: Sat, 17-Oct-87 05:16:15 EDT
References: <7449@reed.UUCP-> <1409@osiris.UUCP> <289@apr.UUCP> <17195@glacier.STANFORD.EDU>
Organization: Bell Communications Research, Inc
Lines: 35
Keywords: NSA, DES
Summary: just a minute...

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

I do not know how much chip real estate a DES engine takes, but John's
figures seem a tad optimistic when compared to existing technology.

Typical commercial DES chips, e.g., the AMD 9518/Z8068, do NOT pipeline
their calculations.  The 9518 has one set of S and P boxes and iterates
16 times. Including overhead, it takes a total of 18 clock cycles to do
one complete encryption or decryption.  Key loading isn't particularly
fast either. The designers probably considered a low pin count to be
more important than making the chip especially useful for key cracking.

Pipelining the DES engine would clearly increase its area at least 16
times, since not only do you need 16 copies of the S and P boxes but
also 16 key registers. You also need a way to extract the proper subkey
in parallel at each of the 16 stages.  John further hypothesizes that
each chip would contain sixteen of these complete DES engines, for a
total complexity increase of at least 256x over existing DES chips.  I
don't know if the RAM comparison is valid, at least inside the chip,
since a DES engine is much less regular than a RAM. True, the 9518 is a
few years old, implemented in N-MOS technology, and not specifically
designed for key cracking. Still, I don't know if a complexity increase
of 256x combined with a speed increase of 5x is reasonable in 1987 CMOS.
Perhaps somebody can comment on this.

Not that any of this really takes away from the John's valid argument
that the DES key is too small. An extra factor of x16 or even x256
really isn't all that much protection given inexorable improvements in
technology.  Cracking DES through brute force is still out of range of a
plug-in card for your PC, but certainly not out of the capability of the
NSA with custom VLSI and much more computer room floor space than John
allowed for his machine.

Phil