Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!rutgers!gatech!udel!burdvax!sdcrdcf!randvax!jim
From: jim@randvax.UUCP (Jim Gillogly)
Newsgroups: sci.crypt
Subject: Re: Design for a DES-breaker
Message-ID: <304@markle.randvax.UUCP>
Date: Fri, 16-Oct-87 18:49:27 EDT
Article-I.D.: markle.304
Posted: Fri Oct 16 18:49:27 1987
Date-Received: Sun, 18-Oct-87 11:52:00 EDT
References: <7449@reed.UUCP-> <1409@osiris.UUCP> <289@apr.UUCP> <17195@glacier.STANFORD.EDU> <1477@faline.bellcore.com>
Reply-To: jim@markle.UUCP (Jim Gillogly)
Organization: Banzai Institute
Lines: 41

In response to John Nagle's DES-cracking proposal Phil R. Karn writes:
>>      So that's our chip.  Each chip can try 20Mhz x 16 keys per second,
>> or 320 x 10^6 keys per second.
>
>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.
> ...
>Not that any of this really takes away from the John's valid argument
>that the DES key is too small.

Not being a hardware type, I'm not sure about the argument that a 20 MHz
clock means 20M decryptions per second, so I'll fall back on the famous
USENET "argument by appeal to authority".

In Crypto 84 (more formally, Advances in Cryptology: Proceedings of
Crypto 84, Ed. Blakley & Chaum, Springer-Verlag 1985) some Belgian scientists
(F.  Hoornaert, J.  Goubert and Y.  Desmedt) came up with a proposed
hardware architecture for fast DES operation, including pipelining.  They
assumed a 20 MHz clock rate and gave the following timing for a single
encryption:

	48 (=16 iterations) + 2 (pipeline delay) + 3 (I/O) = 53 cycles.

They expected throughput in ordinary DES operation of about 20 Mbit/sec.
They included a description of a configuration of the proposed chip that
would deal with about 1.13 x 10^6 keys/sec in a brute force key hacking
mode.  They proposed a system that would brute force a key in a
week or two, within an order of magnitude of John Nagle's proposal.  I
don't remember the costs that they estimated, but I think they expected
the chips themselves to be about $40 each in quantity.  The article is
"Efficient hardware implementation of DES; also design for exhaustive key
search machine", pp 147 ff.

Of course, it would be even more satisfying if one of us could find a
healthy key-folding algorithm and crack it elegantly...
-- 
	Jim Gillogly
	{hplabs, ihnp4}!sdcrdcf!randvax!jim
	jim@rand-unix.arpa