<<

. 38
( 41 .)



>>

scape™s server products with strong cryptography enabled.
“The ability to export our products with strong encryption enables
Netscape to provide its customers worldwide with client and server
software that can improve the security of their information and appli-
cations,” said Taher Elgamal, chief scientist at Netscape in the press
release announcing the change. “This approval is another example of
Netscape™s leadership in the privacy and security arenas and is espe-
cially important due to the recent breaking of 56-bit DES by the DES-
CHALL group last week.”
On the same day, Microsoft announced that it got the same ap-
proval that Netscape did. In consequence, Microsoft would build 128-
bit cryptography into its Internet Explorer 4.0, Money 98, and Internet
Information Server products.
On June 27, Senate Majority Leader Trent Lott made a speech on
the ¬‚oor of the Senate, addressing the cryptography debate and the
Commerce Committee™s consideration of the Pro-CODE and McCain-
Kerrey bills earlier in the month. As feared by proponents of unfettered
cryptography, the McCain-Kerrey bill passed by voice vote in commit-
tee with very few changes, essentially gutting Pro-CODE and leaving
the McCain-Kerrey Secure Public Networks Act as the main cryptog-
raphy bill before the senate.
Senator Lott said,

Mr. President, the demand for strong information security will
not abate. Individuals, industry, and governments need the best
information security technology to protect their information.
The Administration™s policy and the McCain-Kerrey bill al-
low export of 56-bit encryption, with key recovery requirements.
How secure is 56-bit encryption? That question was answered
the day before the Senate Commerce Committee acted. Re-
sponding to a challenge, a secret message encoded with 56-bit
encryption was decoded in a brute force supercomputing e¬ort
known as the “DESCHALL E¬ort.” The message that was de-
coded said “Strong cryptography makes the world a safer place.”
Now that 56-bit encryption has been cracked by individu-
als working together over the Internet, information protected
by that technology is vulnerable. The need to allow stronger
security to protect information is more acute than ever.
270 CHAPTER 39

Conrad Burns, the Senator for Montana who was co-sponsor of the
Pro-CODE legislation followed Senator Lott™s address. Having heard
law enforcement™s concerns about child pornographers using cryptog-
raphy that could circumvent investigators™ ability to intercept suspects™
online messages all throughout the debate, Senator Burns made an in-
teresting observation. He said:

As I sat through the markup last week, it occurred to me that we
had allowed the issue of encryption to be framed as the issue of
child pornography or gambling. I want to be sure that all parties
understand that the reform of encryption security standards is
not related to these issues.
I have often said that encryption is simply like putting a
stamp on an envelope rather than sending a postcard because
you don™t want others to read your mail. Encryption is simply
about people protecting their private information, about compa-
nies and governments protecting their information, from medical
records to tax returns to intellectual property from unautho-
rized access. Hackers, espionage agents, and those just wanting
to cause mischief must be restrained from access to private in-
formation over the Internet.
When used correctly, encryption can enable citizens in re-
mote locations to have access to the same information, the same
technology, the same quality of health care, that citizens of our
largest cities have. Perhaps most importantly, it is about en-
suring that American companies have the tools they need to
continue to develop and provide the leading technology in the
global marketplace. Without this leadership, our national secu-
rity and sovereignty will surely be threatened.
40
Staying the Course




Wednesday, June 18
Chicago, Illinois

Adam L. Beberg and some like-minded volunteers had been working
on creating a central site for Internet computing projects. Among the
projects that caught their interest was the next of the RSA Secret Key
Challenges, 56-bit RC5, often abbreviated as RC5-56.20
Beberg™s distributed.net had started on the RC5-56 contest more
than a month earlier (see page 201) but did not actively recruit from
among the DES Challenge participants.
Happy to see the DES challenge solved, Beberg changed gears,
openly and actively inviting veterans of the DES Challenge contest
to his RC5-56 e¬ort. “This time, we™re all on the same team. DES-
CHALL, SolNET, [and] even SGI is invited,” he wrote in his invitation
posted to the DESCHALL mailing list.
Like Ian Goldberg (which defeated RC5-40 in three and a half
hours), Germano Caronni (who defeated RC5-48 in 313 hours), and
Rocke Verser™s DESCHALL (who defeated DES in 140 days), the dis-
tributed.net group searched for a secret key needed to unlock an en-
crypted message.
On October 20, 1997, 265 days after RSA announced the contest, the
distributed.net team located the secret key needed to read the contest
message: “It™s time to move to a longer key length.”
RSA Data Security announced additional key-searching contests at
its annual conference on January 13, 1998. The “DES Challenge II”
was a pair of contests, just like the DES Challenge that DESCHALL

271
272 CHAPTER 40

answered the year before”with an important di¬erence. The amount
of the cash prize varied, depending on the amount of time needed to
crack the message: if the winner found the key in one quarter (or less) of
the time needed by the previous winner, the prize would be $10,000. A
$5000 prize would go to a winner ¬nding the key in up to half of the time
of the previous winner; a $1000 prize would go to the winner ¬nding the
key in up to three-quarters of the time needed by the previous winner.
On February 24, 1998, distributed.net DES Challenge II (DES-II-1)
project coordinator David McNett announced that DES had once again
fallen to a brute-force search. The message “Many hands make light
work” was decrypted”not in the 140 days that it took DESCHALL to
¬nd the key, but in a mere thirty-nine days. Especially interesting was
the fact that rather than searching only one quarter of the keyspace, as
DESCHALL had, the distributed.net DES-II-1 answer came only after
search more than ninety percent of the keyspace.
On July 13, RSA launched the second DES Challenge II contest
(DES-II-2). Again, distributed.net turned its attention to the contest.
With the additional computing power that became available in the
six months that had passed, and the fact that almost certainly less of
the total keyspace would need to be searched, the previous record was
certain to be beaten again.
Fifty-six hours after the start of the contest, DES-II-2 was solved,
not by distributed.net but by the Electronic Frontier Foundation
(EFF), a non-pro¬t civil liberty advocacy group, in conjunction with
Cryptography Research, a ¬rm headed by cryptographer Paul Kocher.
With funding from EFF and the support of civil libertarian, EFF
board member, and cypherpunk John Gilmore, Paul Kocher and his
team at Cryptography Research designed and implemented “Deep
Crack,” a custom-built machine created for the speci¬c purpose of
cracking DES keys. Proving the assertions made by private-sector
cryptographers true, Deep Crack showed that customized hardware”
coming in at a cost of roughly $250,000”could crack cryptographic
keys dramatically faster than any software.
Finally, in December 1998, RSA announced another contest to crack
a DES message: DES Challenge III, to begin on January 18, 1999. The
¬rst to crack the message would receive a prize of $10,000 if doing the
job was completed in under twenty-four hours, $5000 if it took under
forty-eight hours, and $1000 if it took ¬fty-six hours. Anything longer
would get no cash prize.
Staying the Course 273

Twenty-two hours and ¬fteen minutes after the beginning of the
contest, the message “See you in Rome ([at the] second AES Confer-
ence, March 22“23, 1999)” was extracted from the challenge ciphertext.
The method was once again brute force, this time with distributed.net
and Deep Crack working cooperatively and achieving a key search rate
of 245 billion keys per second when the correct key was found.
The secret message in the DES Challenge III had special signi¬cance
for cryptographers: the second AES Conference to be held in March
1999 was part of NIST™s e¬ort to ¬nd a replacement for DES, which had
reigned as the U.S. government standard for more than twenty years.
The e¬ort to de¬ne AES, the Advanced Encryption Standard, had been
announced in the January 2, 1997 issue of The Federal Register. That
article carried a note of particular interest. “It is NIST™s view that
a multi-year transition period will be necessary to move toward any
new encryption standard and that DES will continue to be of su¬cient
strength for many applications.”
Now more than two years after the announcement of the AES ef-
fort, it was clear that a multi-year period for the de¬nition of a new
standard would be needed. Also clear was the insu¬ciency of DES for
any commercial or governmental application.
41
In Retrospect




Understanding an event™s signi¬cance is usually pretty di¬cult at the
time. Putting it into historical perspective and looking at how it in-
¬‚uenced other events, though, can help a great deal. Since June 1997,
there has been plenty of time to think about what we accomplished.
Could the Internet be the basis of a future computing platform”
“the supercomputer for everyman” as Rocke Verser called it? Many
people believe so.
Since the mid-1990s, and continuing through today, there are several
kinds of projects that are attempting to harness this kind of computa-
tional power.
Other projects related to cryptography include key cracking projects,
such as the distributed.net Bovine e¬ort formed during the height of
DESCHALL and started in earnest after the ¬rst fall of DES. That
project has since solved RSA™s ¬rst DES Challenge II and the DES
Challenge III, as well as RSA™s 56-bit and 64-bit bit RC5 Secret Key
Challenges.
Finding large prime numbers is another example of a large comput-
ing project. The largest such project on the Internet is still running,
the Great Internet Mersenne Prime Search (GIMPS), coordinated by
George Woltman. (That project is being run from www.mersenne.org.)
We have shown time and again that the kind of computing power
that can be harnessed using the Internet to coordinate many processors
is phenomenal. Not all large computing problems are well-suited for this
approach, but for a great many that are”problems that are actually
made up of many small and independent problems”the possibilities
are endless.



275
276 CHAPTER 41

While the social and technical issues that DESCHALL and projects
like it have addressed are of interest, ultimately, DESCHALL is a story
about cryptography.
Even at the time, no one who understood cryptography and comput-
ing was surprised by what DESCHALL accomplished. That DES keys
could be broken by brute force was understood from the beginning”
even if the feasibility of such attacks was up for debate. We understand
that exhaustive key search is an e¬ective means of defeating any sym-
metric cryptosystem, save the Vernam Cipher, which is better known
as the One-Time Pad.
Like the rest of security, cryptography is a tool that allows the de-
fender to change the variables in the game against the attacker. At its
most fundamental level, cryptography is simply a matter of economics.
The whole idea is to make the target harder to reach for an attacker
than the attacker thinks it™s worth.
Make an attacker spend one million dollars to steal one million dol-
lars, and you have taken away his economic incentive. The same fun-
damental principle is true even when the attacker™s motivation is not
money. Whatever it is that the attacker wants, if he has to spend too
much of whatever he has to achieve it, he™s better o¬ simply following
the policy that de¬nes expected use and behavior.
We were able to demonstrate to the world what all of us already
knew by calculation: 56-bit ciphers just aren™t secure against dedi-
cated attackers. Even with no better attack than brute force avail-
able, attackers without special equipment would be able to break the
messages quickly enough to be worthwhile against information whose
value extended beyond a few months. Subsequent breaks of DES mes-
sages demonstrated that the curve continued. At the end Deep Crack
demonstrated that with a relatively modest initial investment (of, say,
$250,000), a machine could be designed and implemented to break DES
keys in a matter of hours.
Some might be inclined to argue that the cost of breaking DES keys
at this point had become $250,000 and one day. I do not share this
view. The amount of time needed to break DES-encrypted messages
with such a system would indeed be one day, but $250,000 was not the
cost for breaking the message”that was the cost for getting into the
message-breaking business. Designing and building Deep Crack was a
one-time expense.
In Retrospect 277

Had EFF wanted, it could well start a key recovery business: by
deploying the key-cracking system so that it would crack one message
after another, continuously working around the clock and throughout
the year, the entire cost of the hardware design and implementation
could be covered in a single year by charging $685 to crack a DES
message. The cost could drop further by processing enough volume to
require a second Deep Crack system”the majority of the cost was in
design (which would not need to be undertaken again), rather than
in implementation (the only cost incurred in bringing a second Deep
Crack online).
With this kind of startup fee and pricing schedule, even a small
company could get into this business”as could any modestly-funded
criminal or terrorist organization.
Considering how long medical records, credit card numbers, census
data, and other kinds of information need to remain con¬dential, min-
imally attackers were shown to be a real threat to the security of this
information. Funded attackers were barely slowed down by the defense
of cryptosystems with 56-bit keys.
In reality, ¬nding a replacement for DES was no more critical be-
cause of the RSA DES challenges. The security of DES was the same
as it had always been and its susceptibility to brute-force attacks was
in line with what we had predicted. But as a result of Peter Trei™s
October 1996 challenge to the Cypherpunks and RSA Data Security™s
support, thousands of cryptographers, programmers, civil libertarians,
and hobbyists took the time to demonstrate for the public the critical
need to heed our warnings.

<<

. 38
( 41 .)



>>