<<

. 8
( 41 .)



>>

tion for researchers to be able to perform a “partial known-plaintext
attack,” a very realistic sort of attack, where a cryptanalyst knows a
little bit of the decrypted message. As the cryptanalyst ¬nds possible
RSA Crypto Challenges 43

breaks, he checks his work against what known plaintext is available to
see whether the break is real.


October 1996
Process Software Corporation, Framingham, Massachusetts

Cryptographer Peter Trei was known not only for development of cryp-
tographic software, but for his public discussion of cryptography, its
uses, and the impact that it could have on the lives of its users. Many
read Trei™s posts to the Cypherpunks mailing list with interest. “Can
we kill single DES?” was a compelling question. Knowing that breaking
a message protected by a cryptosystem as deeply entrenched as DES
would cause a stir, Trei wisely argued that any e¬orts to defeat DES
must be oriented toward a legitimate target.
In response to his message to Cypherpunks, Trei received private
mail from “the R in RSA,” Ron Rivest, suggesting that he contact
Jim Bidzos, the president of RSA Data Security, Inc. Even respected
cryptographers can sometimes be mistaken for kooks”not everyone
knows where to draw the ¬ne line between genius and insanity, so Trei
hesitated before ¬nally writing Bidzos. When he ¬nally wrote Bidzos,
Trei suggested some sort of sponsored contest, along the lines of the
Factoring Challenges that RSA had been doing over the years.
Jim Bidzos responded to Peter Trei™s suggestion quickly and enthu-
siastically. People from RSA Data Security began to work with Trei on
constructing a legitimate attack”a sponsored public contest, following
the model of RSA™s Factoring Challenges”on the global standard for
data encryption.


January 1997
Megasoft Online, Columbus, Ohio

In the eleven years since my discovery of The Codebreakers, I continued
my study of cryptography and information security. After developing
expertise in operating systems and network implementation, I worked
on software security in the ¬nancial services industry. After working on
computer and network security at AT&T Bell Laboratories, I landed
at an early Internet start-up company called Megasoft Online. My job
there involved security for our “Web Transporter” product, which man-
aged software distribution and installation safely”all over the Internet,
44 CHAPTER 6

without the need to use ¬‚oppy disks or CD-ROMs. That meant using
cryptography and I was happy to put my experience to good use.
Like many professional and amateur cryptographers, I received an
e-mail from Trei in January of 1997 in which he updated the crypto-
graphic community on his progress in getting a DES message cracked.
He told us about RSA™s support and announced his DES Key Recovery
program, DESKR.
DESKR was written for more recent releases of the Windows oper-
ating system, such as Windows NT and Windows 95. Most individual
computer users would be able to run DESKR. Windows 3.11”the older
version of Windows that ran atop of Microsoft™s text-based DOS”was
waning in popularity to the point that it seemed pointless to go through
the extra e¬ort to get the software to work on it. Cryptographer Steve
Gibbons adapted DESKR to work on two Unix-based systems more
frequently found in server systems in data centers, computers run-
ning the Ultrix operating system from Digital Equipment Corporation
(DEC, which later merged with Compaq, which itself later merged with
Hewlett-Packard) and from IBM.
Trei sent me a copy of DESKR, including Gibbons™ adaptations.
Since I wanted to run DESKR, I made additional modi¬cations to
the software to run on the systems that I had”a process known as
“porting””and send the changes back to Trei. My adaptations enabled
DESKR to run on Linux, IRIX (the Unix variant from Silicon Graphics,
Inc., known simply as SGI), Solaris 2 (the most recent Unix ¬‚avor from
Sun Microsystems, Inc.), SunOS 4 (Sun™s older Unix), and various BSD
Unix platforms.
DESKR was ready for some ten di¬erent types of computers by the
end of the month, when RSA Data Security launched its contest to
crack a DES-encrypted message.


January 28, 1997, 9:00 A.M.
Sixth Annual RSA Data Security Conference, San Francisco

RSA president Jim Bidzos o¬cially launched the “1997 Secret Key
Challenge,” a series of contests designed to test how quickly messages
encrypted with various key lengths can be broken by brute force. RSA™s
popular annual conference was a perfect springboard from which to
launch the contest. A press release was issued and some members of
the media were there for the conference. Thirteen contests were an-
RSA Crypto Challenges 45

nounced, challenging participants to break messages encrypted with
RSA™s popular variable-strength cipher, RC5. The ¬rst contest was a
$1000 prize for breaking a message protected by 40-bit RC5, a $5000
prize for the 48-bit RC5 contest, and a purse of $10,000 went to anyone
for decrypting the message in the other contests which ranged from
56-bit to 128-bit con¬gurations of the RC5 cipher.
RC5 wasn™t the only target of the Secret Key Challenge. In addition
to the twelve RC5 contests, a contest to crack a DES-encrypted message
was included. Its prize was set at $10,000.


12:30 P.M.
University of California, Berkeley

UC Berkeley graduate student and cryptographer Ian Goldberg read
the output from his program, designed to ¬nd a solution to RSA™s 40-
bit challenge. Running on the Network of Workstations (NOW) at UC
Berkeley, Goldberg™s program pooled together the unused processing
power of about 250 workstations, testing approximately 28 million keys
per second.
Goldberg grinned as he read the message on his screen.

The unknown message is: This is why you should use a longer
key.

Just three and a half hours after the launch of RSA™s Secret Key
Challenges, the 40-bit contest was over.


February 10, 6:52 P.M.
Swiss Federal Institute of Technology (ETH), Zurich

Germano Caronni, a graduate student working on a Ph.D. in commu-
nications and security, was distributing software for use by individu-
als on their own machines to try to ¬nd the solution to RSA™s 48-bit
challenge. Once started on a participant™s machine, Caronni™s software
would make a connection to his keyserver”a computer that would tell
the computer which keys to try. Once the computer got the message
that said where to start and where to stop searching, it would begin
working. If the computer did not ¬nd the key by the time it had tried
the entire set (or “block”) given to it by the keyserver, the computer
46 CHAPTER 6

would report back to the server that it had tried all of the keys in the
range that it had been given and ask for another range.
Germano Caronni happily saw his system report to him:

The unknown message is: The magic words are Security Dy-
namics and RSA.

Just over thirteen days after the start of the contest, Caronni™s
project found the winning key. Caronni felt a sense of vindication,
¬nding the solution, after having been beat to the right key by Ian
Goldberg on the 40-bit RC5 contest.
Caronni won $5000, which he donated to the non-pro¬t Project
Gutenberg, an organization creating, maintaining, and distributing
electronic texts of books whose copyrights have expired.




I could feel a real sense of excitement building within the cryptographic
community. Like hundreds of others, I ran Caronni™s key-cracking soft-
ware on a dozen or more computers to which I had access, trying
to bring the project to a successful conclusion as quickly as possible.
Though I had helped to make Peter Trei™s DESKR software available
to more computer types, I decided not to work on the DES Challenge
until the easier 40-bit and 48-bit RC5 Challenges were answered.
Now it was obvious knew that these systems were weak and could
be broken at no cost with a small investment of time. Once the 48-bit
challenge had been answered, cryptanalysts returned their attention to
the U.S. Government standard of nineteen years, DES.
By working to break a message encrypted with DES, cryptanalysts
were doing much more than answering a contest call or engaging in a
theoretical exercise. DES was the standard in virtually every industry
in virtually every nation. It had been criticized from the beginning as
being weak against a determined adversary because of its small key
size. The time for theoretical designs, postulations, and estimates was
over. It was time to show the world that it was possible to break a
DES-encrypted message.
No one seriously believed that that attacking DES by brute force
would be easy. Though ¬nding the right key would just be a matter of
time, the risk that presented itself was that if a cryptographic attack
RSA Crypto Challenges 47

took too long to ¬nd the right key, we strong-cryptography advocates
might undermine the very point we needed to make. If the project that
found the key for the DES challenge proceeded at the speed of the
40-bit challenge, the search would take twenty-six years. If the project
proceeded at the speed of the 48-bit challenge, the search would take
nine years. Finding the right DES key could be the largest computation
ever performed, and if we were going to succeed, we were going to need
a lot of computing horsepower to share the burden.
Once the 48-bit challenge group ¬nished celebrating its success,
those of us who worked on the Caronni project moved quickly on to
breaking DES, renaming the project DES-Challenge. We set up mailing
lists. We discussed the architecture”the design for getting key-cracking
software running on thousands of machines to coordinate”used by
Caronni at length, its virtues, and how we might need to augment it
in order to answer the challenge successfully in a reasonable amount of
time. Graphic logos were made for people to put on Web sites to raise
awareness and to recruit “clients” (individual processors running the
DES key cracking software). We talked about how to build the DES
cracking software and how to get all of the clients working with each
other.
I wrote to Nicholas Petreley at the trade magazine Infoworld and
described the work we were engaged in as well as why we believed that
participating in the DES-cracking contest was so important. Based on
the success of the 40-bit and 48-bit challenges, I estimated that DES
keys could be broken in three to four months of e¬ort by a dedicated
attacker with no special equipment. My estimate, more optimistic than
the one Peter Trei had proposed several months earlier, was based on
the number of people who were interested in proving that small keys
were inherently unsafe keys.
We weren™t the only ones estimating how long it would take.
7
Congress Takes Note




March 20, 1997
Capitol Hill, Washington, DC

Howard Coble, a sixty-six year-old representative from North Carolina
leaned forward to speak into his microphone. Coble, chairman of the
House Judiciary Subcommittee on Courts and Intellectual Property,
called the meeting to order.
The 105th Congress was debating several bills regarding crypto-
graphic policy. The House was considering a bill called the “Security
and Freedom Through Encryption (SAFE) Act,” the primary purpose
of which was to relax control over cryptographic technology used in the
U.S. and by U.S. citizens abroad. A similar bill called Pro-CODE was
working its way through the Senate.
Law enforcement o¬cials widely thought that restrictions on crypto-
graphic products and access to cryptographic keys were vital weapons
against crime”both online and o¬„ine. O¬cials feared that cryptogra-
phy that the government cannot break would cause them to lose their
struggle against terrorists, drug tra¬ckers, and child pornographers”
the three most oft-cited criminal elements in these debates. Since the
SAFE Act and Pro-CODE bills would largely eliminate governmental
regulation over cryptography, the Clinton administration opposed these
bills.
Government regulation of cryptography prevented U.S. companies
from exporting their security products to customers in other coun-
tries. These vendors opposed continued regulation, arguing that they
were unable to compete in a global marketplace against foreign compa-

49
50 CHAPTER 7

nies that were not subject to similar restrictions. Additional opposition
to cryptographic restrictions came from civil libertarians who worried
that the eventuality of such regulation would be a police state in which
the freedom of U.S. citizens would take second place to government
interests. Computer scientists and engineers argued that the systems
requiring government access to keys would actually reduce overall secu-
rity, since failing to protect medical, ¬nancial, and personal information
with cryptography would make criminals better able to steal such in-
formation.
This debate over the liberation of cryptography started in the early
1990s and came to be known simply as the Crypto Wars.
Laying groundwork for the discussion to follow, Coble said,

Today the subcommittee is conducting a hearing on H.R. 695,
the Security and Freedom Through Encryption (SAFE) Act,
commonly known as the SAFE Act. H.R. 695 addresses the
complex and important issue of encryption.
Encryption, as you perhaps know, is the process of encoding
data or communications in a form that only the intended recip-
ient can understand. Once the exclusive domain of the national
security agencies, encryption has become increasingly important
to persons and companies in the private sector concerned with
the security of the information they transmit.
The encryption debate encompasses two main issues. The
¬rst is whether there should be any restriction on the domes-
tic use and sale of encryption technology and, in particular,
whether domestic users may place their keys in escrow with the
government or some neutral third party. This requirement would
provide a mechanism which would allow law enforcement and

<<

. 8
( 41 .)



>>