Foreword by

WHITFIELD DIFFIE

to

Cracking DES: Secrets of Encryption
Research, Wiretap Politics, and Chip Design

by

the Electronic Frontier Foundation

July 1998

In 1974 the Stanford computer science community ate at Loui's. [1] 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.

My thoughts went as follows:

NSA doesn't want a strong cryptosystem as a national standard, because it is afraid of not being able to read the messages.

On the other hand, if NSA endorses a weak cryptographic system and is discovered, it will get a terrible black eye.

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.

When the Proposed Data Encryption Standard was released on the 17th of March 1975 [2], 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. [3]

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." [4] 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.

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. [5] 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.

The year 1993 brought a watershed. Michael Wiener of Bell-Northern Research designed the most solid paper machine yet. [6] 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.

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. [7] 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.

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.

At the 1997 annual RSA cryptographic trade show in San Francisco, a prize was announced for cracking a DES cryptogram [8]. 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.

At the 1998 RSA show, the prize was offered again. This time the prize was claimed in 39 days [9] 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.

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.

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.

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.

---

Footnotes

[1] Louis Kao's Hsi-Nan restaurant in Town and Country Village, Palo Alto.
[2] 40 Federal Register 12067
[3] Whitfield Diffie and Martin E. Hellman. "Exhaustive cryptanalysis of the NBS data encryption standard". Computer, 10(6):74-84, June 1977.
[4] R. R. Jueneman, The Data Encryption Standard vs. Exhaustive Search: Practicalities and Politics. 5 Feb 1981.
[5] Yvo Desmedt, "An Exhaustive Key Search Machine Breaking One Million DES Keys", presented at Eurocrypt 1987. Chapter 9 of this book (Cracking DES). Jean-Jacques Quisquater and Yvo G. Desmedt, "Chinese Lotto as an Exhaustive Code-Breaking Machine", Computer, 24(11):14-22, November 1991.
[6] Michael Wiener, "Efficient DES Key Search", presented at the rump session of Crypto '93. Reprinted in Practical Cryptography for Data Internetworks, W. Stallings, editor, IEEE Computer Society Press, pp. 31-79 (1996). Currently available at
http://www.eff.org/pub/Crypto/Crypto_misc/Technical/des_key_search.ps.gz
[7] 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 http://www.bsa.org/policy/encryption/cryptographers_c.html
[8] http://www.rsa.com/rsalabs/97challenge/
[9] June 17, 1997, See the announcements at http://www.rsa.com/des/ and http://www.frii.com/~rcv/deschall.htm (February 24, 1998), http://www.wired.com/news/news/technology/story/10544.html and http://www.distributed.net

---

Please send any questions or comments to webmaster@eff.org

Return to     Welcome Page