foreword.html
3eeb5c1f5b2317b2f73e159e0e5f910285a5faf090374793b35528808a85e1be<!DOCTYPE HTML PUBLIC "html.dtd">
<HTML><HEAD>
<TITLE>Whitfield Diffie's Foreword to EFF's "Cracking DES" Book</TITLE></HEAD>
<BODY BGCOLOR="#ffffff" VLINK="#03066A" TEXT="#000000" LINK="#0000ee" ALINK="#FF0000">
<A NAME="top"> </A>
<UL><UL>
<H3>Foreword by</H3>
<H1>WHITFIELD DIFFIE</H1>
<H4>to</H4>
<H2><A HREF="http://www.oreilly.com/catalog/crackdes">Cracking DES: Secrets of Encryption
<BR>Research, Wiretap Politics, and Chip Design</A></H2>
<H4>by</H4>
<H2><A HREF="http://www.eff.org/">the Electronic Frontier Foundation</A></H2>
<H4>July 1998<BR></H4>
</UL></UL>
<BR>
<P>
In 1974 the Stanford computer science community ate at Loui's. [<A HREF="#1">1</A>] As
I sat eating one evening in the fall, Butler Lampson approached me,
and in the course of inquiring what I was doing, remarked that the IBM
Lucifer system was about to be made a national standard. I hadn't
known it, and it set me thinking.
</P>
<P>
My thoughts went as follows:
</P>
<BLOCKQUOTE><P>
NSA doesn't want a strong cryptosystem as a national standard,
because it is afraid of not being able to read the messages.
</P>
<P>
On the other hand, if NSA endorses a weak cryptographic system and
is discovered, it will get a terrible black eye.
</P></BLOCKQUOTE>
<P>
Hints that Butler was correct began to appear and I spent quite a lot
of time thinking about this problem over the next few months. It led
me to think about trap-door cryptosystems and perhaps ultimately
public-key cryptography.
</P>
<P>
When the Proposed Data Encryption Standard was released on the 17th of
March 1975 [<A HREF="#2">2</A>], I thought I saw what they had done. The basic system might
be ok, but the keyspace was on the small side. It would be hard to
search, but not impossible. My first estimate was that a machine
could be built for $650M that would break DES in a week. I discussed
the idea with Marty Hellman and he took it on with a vengance. Before
we were through, the estimated cost had fallen to $20M and the time
had declined to a day. [<A HREF="#3">3</A>]
</P>
<P>
Our paper started a game in the cryptographic community and many
papers on searching through DES keys have since been written. About
three years after the publication of our paper, Robert Jueneman ---
then at Satellite Business Systems in McLean, Virginia --- wrote "The
Data Encryption Standard vs. Exhaustive Search." [<A HREF="#4">4</A>] This opus was
substantially more optimistic about the chances for DES breaking. It
predicted that by 1985 a half-million dollar investment would get you
a DES key every hour and that by 1995, $10 million similarly spent
would reduce that time to two seconds, an estimate remarkably close to
one made fifteen years later.
</P>
<P>
A decade later, Yvo Desmedt and Jean-Jaques Quisquater made two
contibutions, one whimsical, one serious. Using a related "birthday
problem" sort of approach, they proposed a machine for attacking many
cryptographic problems at a time. [<A HREF="#5">5</A>] Their whimsical suggestion took
advantage of the fact that the population of China was about the
square root of the size of the DES key space.
</P>
<P>
The year 1993 brought a watershed. Michael Wiener of Bell-Northern
Research designed the most solid paper machine yet. [<A HREF="#6">6</A>] It would not
be too far off to describe it as a Northern Telecom DMS100 telephone
switch, specialized to attacking DES. What made the paper noteworthy
was that it used standard Northern Telecom design techniques from the
chips to the boards to the cabinets. It anticipated an investment of
under a million dollars for a machine that would recover a key every
three hours. A provocative aside was the observation that the required
budget could be hidden in a director's budget at BNR.
</P>
<P>
Finally, in 1996, an estimate was prepared by not one or two
cryptographers but by a group later, and not entirely sympathetically,
called the magnificent seven. [<A HREF="#7">7</A>] This estimate outlined three basic
approaches loosely correlated with three levels of resources. At the
cheap end was scrounging up time on computers you didn't need to own.
In the middle was using programmable logic arrays, possibly PLA
machines built for some other purpose such as chip simulation. The
high end was the latest refinement of the custom chip approach.
</P>
<P>
Exhaustive key search is a surprising problem to have enjoyed such
popularity. To most people who have considered the probem, it is
obvious that a search through 2รถ56 possibilites is doable if somewhat
tedious. If it a is mystery why so many of them, myself included, have
worked to refine and solidify their estimates, it is an even greater
mystery that in the late 1990s, some people have actually begun to
carry out key searches.
</P>
<P>
At the 1997 annual RSA cryptographic trade show in San Francisco, a
prize was announced for cracking a DES cryptogram [<A HREF="#8">8</A>]. The prize was
claimed in five months by a loose consortium using computers scattered
around the Internet. It was the most dramatic success so far for an
approach earlier applied to factoring and to breaking cryptograms in
systems with 40-bit keys.
</P>
<P>
At the 1998 RSA show, the prize was offered again. This time the prize
was claimed in 39 days [<A HREF="#9">9</A>] a result that actually represents a greater
improvement than it appears to. The first key was found after a search
of only 25% of the key space; the second was not recovered until the
85% mark. Had the second team been looking for the first key, they
would have found it in a month.
</P>
<P>
These efforts used the magnificent seven's first approach. No
application of the second has yet come to light. This book skips
directly to the third. It describes a computer built out of custom
chips. A machine that 'anyone' can build; from the plans it presents
--- a machine that can extract DES keys in days at reasonable prices,
or hours at high prices. With the appearance of this book and the
machine it represents, the game changes forever. It is not a question
of whether DES keys can be extracted by exhaustive search; it is a
question of how cheaply they can be extracted and for what purposes.
</P>
<P>
Using a network of general purpose machines that you do not own or
control is a perfectly fine way of winning cryptanalytic contests, but
it is not a viable way of doing production cryptanalysis. For that,
you have to be able to keep your activities to yourself. You need to
be able to run on a piece of hardware that you can protect from
unwanted scrutiny. This is such a machine. It is difficult to know how
many messages have been encrypted with DES in the more than two
decades that it has been a standard. Even more difficult is knowing
how many of those messages are of enduing interest and how many have
already been captured or remain potentially accessible on disks or
tapes, but the number, no matter precisely how the question is framed
must be large. All of these messages must now be considered to be
vulnerable.
</P>
<P>
The vulnerability does not end there, however, for cryptosystems have
nine lives. The most convincing argument that DES is insecure would
not outweigh the vast investment in DES equipment that has accumulated
throughout the world. People will continue using DES whatever its
shortcomings, convincing themselves that it is adequate for their
needs. And DES, with its glaring vulnerabilities, will go on
pretending to protect information for decades to come.
</P>
<HR>
<H4>Footnotes</H4>
<P>
<A NAME="1">[1]</A> Louis Kao's Hsi-Nan restaurant in Town and Country Village,
Palo Alto.<BR>
<A NAME="2">[2]</A> 40 <I>Federal Register</I> 12067<BR>
<A NAME="3">[3]</A> Whitfield Diffie and Martin E. Hellman. "Exhaustive
cryptanalysis
of the NBS data encryption standard". <I>Computer</I>, 10(6):74-84, June
1977.
<BR><A NAME="4">[4]</A> R. R. Jueneman, <I>The Data Encryption Standard
vs.
Exhaustive Search:
Practicalities and Politics</I>. 5 Feb 1981.
<BR><A NAME="5">[5]</A> Yvo Desmedt, "An Exhaustive Key Search Machine
Breaking One Million
DES Keys", presented at Eurocrypt 1987. Chapter 9 of this book
(<I>Cracking DES</I>).
Jean-Jacques Quisquater and Yvo G. Desmedt, "Chinese Lotto as an
Exhaustive Code-Breaking Machine", <I>Computer</I>, 24(11):14-22, November
1991.
<BR><A NAME="6">[6]</A> Michael Wiener, "Efficient DES Key Search",
presented at the rump
session of Crypto '93. Reprinted in <I>Practical Cryptography for Data
Internetworks</I>, W. Stallings, editor, IEEE Computer Society Press, pp.
31-79 (1996). Currently available at
<BR><A HREF="http://www.eff.org/pub/Crypto/Anonymity/Digital_money/Crypto_misc/Technical/des_key_search.ps.gz">http://www.eff.org/pub/Crypto/Crypto_misc/Technical/des_key_search.ps.gz</A>
<BR><A NAME="7">[7]</A> Matt Blaze, Whitfield Diffie, Ronald L. Rivest,
Bruce Schneier,
Tsutomu Shimomura, Eric Thompson, and Michael Wiener. "Minimal key
lengths for symmetric ciphers to provide adequate commercial
security: A report by an ad hoc group of cryptographers and computer
scientists", January 1996. Available at
<A HREF="http://www.bsa.org/policy/encryption/cryptographers_c.html">http://www.bsa.org/policy/encryption/cryptographers_c.html</A>
<BR><A NAME="8">[8]</A> <A HREF="http://www.rsa.com/rsalabs/97challenge/">http://www.rsa.com/rsalabs/97challenge/</A>
<BR><A NAME="9">[9]</A> June 17, 1997, See the announcements at <A HREF="http://www.rsa.com/des/">http://www.rsa.com/des/</A> and
<A HREF="http://www.frii.com/~rcv/deschall.htm">http://www.frii.com/~rcv/deschall.htm</A> (February 24, 1998),
<A HREF="http://www.wired.com/news/news/technology/story/10544.html">http://www.wired.com/news/news/technology/story/10544.html</A> and
<A HREF="http://www.distributed.net/">http://www.distributed.net</A>
</P>
</BODY></HTML>
© 2022 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed