. 1
( 41 .)



>>

BRUTE FORCE
CRACKING THE DATA ENCRYPTION STANDARD




Matt Curtin
INTERHACK CORPORATION




Copernicus Books
AN IMPRINT OF SPRINGER SCIENCE+BUSINESS MEDIA
© 2005 Matt Curtin

All rights reserved. No part of this publication may be reproduced, stored in
a retrieval system, or transmitted, in any form or by any means, electronic,
mechanical, photocopying, recording, or otherwise, without the prior written
permission of the publisher.

Published in the United States by Copernicus Books,
an imprint of Springer Science+Business Media.

Copernicus Books
Springer
233 Spring Street
New York, NY 10013

www.springeronline.com

Library of Congress Cataloging-in-Publication Data
Curtin, Matt.
Brute force : Cracking the data encryption standard / Matt Curtin.
p. cm.
Includes bibliographical references and index.
ISBN 0-387-20109-2 (alk. paper)
1. Computer security. 2. Data encryption (Computer science) I.Title.
QA76.9.A25C873 2005
005.8 2”dc22
2004058919



Manufactured in the United States of America.
Printed on acid-free paper.



987654321



ISBN 0-387-20109-2 SPIN 10958636
Contents


Foreword by John Gilmore v
viii
Preface
x
Acknowledgments

1 Working Late 1
2 Keeping Secrets 3
3 Data Encryption Standard 11
4 Key Length 23
5 Discovery 37
6 RSA Crypto Challenges 41
7 Congress Takes Note 49
8 Supercomputer 57
9 Organizing DESCHALL 63
10 Needle in a Haystack 75
11 Spreading the Word 77
12 The Race Is On 85
13 Clients 91
14 Architecture 97
15 Progress 113
16 Trouble 121
17 Milestones 127
18 Gateways 135
19 Network 139
20 Download 141
21 Short Circuit 151
22 DESCHALL Community 159
23 Proposal 163
24 In the Lead 165
25 Recruiting 169
26 Threats 175
27 Overdrive 189
28 Distributed 199
29 An Obstacle 207
30 Export 213
31 Getting Word Out 215
32 Salvos in the Crypto Wars 229
33 New Competition 235
34 Netlag 239
35 Terminal Velocity 241
36 Duct Tape 249
37 Showdown in the Senate 255
38 Strong Cryptography Makes
the World a Safer Place 259
39 Aftermath 267
40 Staying the Course 271
41 In Retrospect 275

283
Notes
287
Index
Foreword


A big battle over privacy was fought in the 1970s, 80s, and 90s, and most
people didn™t even know it was happening.
The U.S. government deliberately restricted the ways in which people
could protect their own privacy. They did this with laws, with regulations,
and by threatening prominent activists like Ron Rivest and Phil
Zimmermann with censorship and prosecution. Most of it was unconsti-
tutional, though they got away with it for decades. But most importantly,
they restricted our privacy by keeping us ignorant and by lying to us.
A good way to keep information private is to safeguard it with encryp-
tion, a mathematical technology that scrambles information. You set it up
so that the only people who have the “key” to unscramble it are the peo-
ple that the owner intends to give access to. The government wanted to
keep a monopoly on information about encryption. This would let the gov-
ernment hide information from its citizens (and from foreigners), but its
own citizens (and foreigners) could not hide information from the gov-
ernment. The government had already threatened prominent academic
researchers, tried to cut off National Science Foundation funding for
research in encryption, and had built a “voluntary” censorship system for
research papers.
It seemed to some people that freedom to do research, freedom to
publish the results, and privacy were fundamental values of society that
were more important than any particular government desires. The early
academic researchers of cryptography, like David Chaum, Ron Rivest, and
Whitfield Diffie, were such people. The Cypherpunks, who came along a
few decades later, were also such people. I co-founded the Cypherpunks,
an open group who educated ourselves and each other about encryption,
and encouraged each other to write encryption software for free public
use. Our goal was to re-establish the freedoms that the government had
silently taken away, do the research, and publish the results, to transform
society™s expectations about privacy.
Part of the lies and ignorance created by the government was about a
system called DES”the Data Encryption Standard. The government
claimed that it was secure and private. Independent researchers claimed
that it was too easy for governments to break into the privacy of DES. But
mere claims were not enough to stop it, and the government succeeded
in getting almost everyone to use DES worldwide. Banks used it to secure


v
billions of dollars of money transfers. Satellite TV companies used it to
keep their transmissions to their customers private. Computer security
products used it. ATMs used it to guard the phone line that connects
them to their bank and tells them when to deliver cash.
DES was deliberately designed by the U.S. government to be flawed.
The government could read what was encrypted by DES, merely by
spending enough money to build a machine that would break it. And the
amount of money that it took went down every year, both as technology
evolved, and as the designer learned more about how to build such
machines. All that knowledge was hidden in the same secretive govern-
ment agencies who deliberately weakened DES.
As personal computers and chip technology rapidly became cheaper
and faster, ordinary people working together could rival the machine-
building power of the government. This book is the story of how they
proved the government was lying, twenty years after the lie, and by doing
so, energized the public to take its privacy into its own hands. The end
result was not only that government policy about encryption and privacy
was changed. Also, the process of building networks of people and
machines to do calculations by “brute force” taught us a lot about collab-
oration, about social structures in volunteer groups, about how the world
is changed by the broad distribution of consumer products that compute.
And about how to break down certain kinds of intractable problems into
small pieces, such that many people can do a piece and thus contribute
to the solution.
The panicky public reaction to the attack of 9/11 was unable to upset
the balance of relatively sane encryption policy that it had taken decades
to set right. However, the abdication of responsibility that took hold of
both the Congress and the bulk of the public has let a corrupt adminis-
tration get away with murder”literally, in the case of hundreds of thou-
sands of civilians in Iraq. Civil rights and moral standards as basic as the
prohibition on torture, the freedom to move around in your own country,
and the universal condemnation of unprovoked attacks on other coun-
tries have all fallen by the wayside.
Yet computers and networks have shown even more interesting ways
for millions of people to collaborate to solve big intractable problems like
this. As I write this, thousands of people are working for a few days from
their homes, phoning up strangers to encourage them to go out and vote
in the upcoming U.S. election. A computer network, programmed by a




vi
small number of people, has collected and connected both the callers and
the people who they should call.
We will continue to be surprised by the capabilities that human soci-
eties have, when thousands of people network through their computers
to accomplish a common purpose.

John Gilmore
Electronic Frontier Foundation
October 31, 2004




vii
Preface


In the past fifty years, society has undergone a radical shift in the storage
and processing of information, away from the physical and toward elec-
tronic representation. Important information is no longer written on a
sheet of paper and stored in a locked file cabinet or safe. Information nec-
essary to care for our health, our finances, and the institutions, public and
private, that support society is now stored electronically, in little ones and
zeroes. Encryption technology”the mathematical system used to protect
electronic information”was developed to protect all of those data from
prying eyes.
In the late 1970s, the U.S. government decided to create a national
data encryption standard in order to bring order to a market that had gen-
erated a multitude of competing and rarely complimentary encryption
products. The standard the government settled on called the data encryp-
tion standard or DES was immediately criticized for being too weak by
many security and computer experts. For years the critics demanded
stronger cryptography and for years the government ignored their
requests.
In 1997 a security company, RSA, answered DES™s critics. They
launched a contest, challenging cryptographers and computer enthusi-
asts to show the government just how weak DES was. Brute Force tells
the story of DES: how it was established, challenged, and ultimately
defeated. But more than the longevity of DES or the definition of the
standard was at stake.
Even while technologists argued over how strong the cryptographic
standard had to be, lawmakers in the United States were busy debating
the government™s role in the regulation of cryptography. At the heart of
the debate was whether or not the government would permit American
companies to export products that they couldn™t break overseas, and
whether private citizens would be permitted to use cryptography that
would shield their information from the eyes of government. Libertarians,
cryptographers, and security experts wanted to be able to use and export
the most robust encryption possible. While some in Congress supported
this view, many other members of the government, including the Clinton
administration, were wary of strong encryption, fearing it would fall into
the hands of criminals and terrorists. Brute Force tells the story of the
legislative battle over DES as well.


viii
Although cryptographic specialists will likely be familiar with parts of
this story and be eager to learn what happened behind the scenes, this is
not only a story for technologists. What happened in 1997 affects people
everywhere, even today, and will do so for years to come. So long as we
store and transmit private information on computers, we will need to pro-
tect it from those who would try to steal it.
Events of this story fall into one of three major topics: the technology
of secret writing, the story of how people who never knew each other
came together to defeat the global standard for secret writing, and the
wrangling over public policy on cryptography. The story is told not by
recounting events in a strictly chronological order but as chains of events
that place different parts of the story into context and allow the reader to
see how these events finally came crashing together, changing the face of
information management forever.



. 1
( 41 .)



>>