<<

. 34
( 41 .)



>>

determine who was contributing and how much spare processing power
they had available.
That night, Ken Chase in Toronto received a curious e-mail message
that contained a table showing the top contributors to SGI™s e¬ort.
Although the numbers leaked would not allow for highly meaningful
comparison of the e¬ort™s total progress, the “identi¬er” column of
the “top 20 participants” table did show participation from a broad
cross-section of SGI. Participants were at SGI proper and Cray, the
famed supercomputer maker, which SGI had purchased some time ear-
lier. (Interestingly, Cray was also the manufacturer of the “$30 million
supercomputer” that Robert S. Litt from the Department of Justice
said would need over a year to crack a DES message.) Looking with
more detail, Chase saw that even within these business units, various
o¬ces were contributing cycles, as were departments including security,
marketing, and software development projects.
New Competition 237

Chase forwarded the message to the DESCHALL mailing list in
the late evening. Several hours later, Chase somewhat sheepishly com-
posed another message to the DESCHALL mailing list. It turned out
that he had received two messages about SGI™s e¬ort”the one that
he had forwarded and one with more details on the e¬ort™s status. He
overlooked the message containing the details. (Chase™s error was a
textbook demonstration of how making major changes in a comput-
ing environment tends to lead to strange changes in behavior. Chase
had just switched to the Dvorak keyboard layout, which positioned its
keys di¬erently from the QWERTY system that is most common. The
switch increased the amount of e¬ort needed to use the keyboard, since
Chase was still training his ¬ngers to go to the correct positions. Con-
sequently, Chase was typing less than he might otherwise, and would
therefore avoiding opening messages that looked like they might require
a response unless he was ready to put forth the e¬ort to type with the
Dvorak keyboard.)
Realizing what he had skipped over, Chase typed a brief explanation
and forwarded the other message from inside of SGI to the DESCHALL
mailing list.
While not detailing the scope or progress of the e¬ort, the message
did show that there was a fair bit of activity; it named the organizers
and gave compelling evidence that the organizers had made every e¬ort
to make participation within SGI as easy as possible. Much of what
they had on their internal Web site advertising the need for clients was
what we had on our web site, that is, an explanation of the contest,
the bene¬ts involved, and how to participate.
On June 5, Rocke Verser privately reported to Justin Dolske and
me that he had sent e-mail to the coordinators of SGI™s DES Challenge
e¬ort. The leaks that we had been seeing included things like the or-
ganizers™ contact information, and the name of the internal lists used
for coordinating the e¬ort. So why not try to contact them?
If there was truth to rumors about the extent to which SGI was
working through the keyspace, it could have quite a signi¬cant impact
on Verser™s “Expected Date of Completion” reports, and he wanted to
be sure that he was using the most complete information. A model that
re¬‚ected SGI data in addition to DESCHALL and SolNET would be
more accurate.
Now brought into the open, the coordinators of the SGI project were
forthcoming and revealed two important sets of statistics.
238 CHAPTER 33

The ¬rst statistic was the amount of keyspace tested. SGI had al-
ready ¬nished just over 19 percent of the total 56-bit keyspace, notable
because that was the greatest amount of keyspace covered by any of
the known e¬orts. Second place went to DESCHALL at about sixteen
percent, and third went to SolNET at just under ten percent.
The second statistic was the approximate key search rate, weighing
in at about 2.8 billion keys per second. That came in a bit ahead of the
2.1 billion keys per second tested by SolNET, but signi¬cantly behind
the 4 billion keys per second being tested by DESCHALL.
Overall, the ¬gures showed SGI was in the lead, but DESCHALL
was gaining fast and would soon pull ahead.
34
Netlag




The Internet™s growing pains continued into June of 1997. One symp-
tom was that some people could not access our keyserver from time
to time due to small network failures. The DESCHALL mailing list
became peppered with messages from participants who were having
trouble reaching the server and who wanted to know whether others
were having similar problems.
This leads us to a second “ailment” that a¬„icted the Internet™s
health at this time. Operations that used to take just a few seconds
could take minutes, or even hours, as evidenced by lag time on the
mailing list. Some people started to notice that there were delays in
getting their messages posted to the DESCHALL list, and some users
complained that it often took hours for the mail server to deliver their
messages.
As it turned out, the mail server was working just ¬ne, but sev-
eral sites had di¬culty with their domain name service (DNS) servers,
the directory service that converted people-friendly names like frii.com
to computer-friendly network address numbers like 216.17.184.30 and
back again. Partly as an anti-spam measure, mail servers were just
starting to refuse to talk to each other without being able to look up
names and numbers in the DNS correctly. As a result, sites with DNS
problems could sometimes sit idle for hours before our mail server could
communicate with theirs and let the mail exchange properly.
The combination of these two problems could make for a frustrating
experience. Someone thinks that the keyserver might be down and then
posts a message to the list asking whether the problem is local or more
widespread. Thanks to the sluggishness of di¬erent e-mail servers, an
hour or two might pass before anyone received the concerned user™s


239
240 CHAPTER 34

message. Meanwhile, whatever problem prompted the message in the
¬rst place”either a keyserver problem or an overload of tra¬c on some
ISP”had been resolved.
Naturally, people getting the “Keyserver down?” messages would
see that they could easily connect to the keyserver and quickly reply
that all was working as expected. So not only was the original query
rendered irrelevant by its delay, but it tended to prompt a ¬‚ood of
unnecessary responses.
The Internet basically worked and our project never would have
been possible without it, but four or ¬ve years of exponential growth
took a toll in the form of quality of service. Normally, no one would
notice delays in e-mail delivery, but working on a project like DES-
CHALL, where everyone was tied together by way of the Internet and
often trading time-sensitive information, would very quickly give one a
heightened sense of how cumbersome the current Internet infrastruc-
ture still was.
35
Terminal Velocity




Thursday, June 5, 9:37 P.M.
The Ohio State University, Columbus

Our project™s key testing rate depended on two factors: fast clients
and many participants running those clients. DESCHALL™s clients were
already faster than any other project™s, so it seemed to make sense that
at some point, we were going to reach a limit on just how fast we could
make the software work reliably. At that point, the only way to increase
the project™s overall key testing rate would be to get the key-testing
software running on more computers.
But having software that was faster than the programs our com-
petitors were using wasn™t good enough. Justin Dolske posted an an-
nouncement to the DESCHALL mailing list on June 5: new clients were
available, and they ran faster than ever.
Leading up to the June 5 release, Darrell Kindred improved the
performance of his bitslice software again and then adapted it so the
technique would also work on 32-bit platforms. Consequently, many
clients experienced a performance increase, ranging from ¬ve percent
to eighty-two percent.
The eighty-two percent performance increase went to the users of
Sun UltraSPARC systems. Other Sun systems, based on older vari-
eties of the SPARC processor had a forty-¬ve percent increase. Clients
for HP systems increased ¬fty-seven percent, Alpha clients increased
twenty-¬ve to forty percent, and AIX clients had a twenty percent per-
formance boost. The same software release also included a new Macin-



241
242 CHAPTER 35

tosh client”complete with a slick graphical interface and a nice ¬ve to
ten percent performance increase.
Almost immediately, the reports started to ¬‚ow in: people were see-
ing dramatic speed improvements.
Several hours after Dolske™s announcement, Rocke Verser was look-
ing at the project statistics back in Loveland. Having updated his model
for determining the expected date for a solution to the RSA DES Chal-
lenge, he put June 5™s ¬gures into the model.
What made the new model di¬erent was that it factored in three
projects, rather than only two”adding SGI to the contenders for the
solution. Using the data available on SGI™s e¬ort, Verser showed the
key testing rates for all three projects.

Recent DESCHALL keyrate: 4.125 billion keys per second
Recent SolNet keyrate: 2.125 billion keys per second
Recent SGI keyrate: 2.890 billion keys per second
Table 20. June 5 Key Testing Rate Comparisons



In addition, Verser reported how much of the keyspace each project
tested up to that point. For many participants, the report would be
the ¬rst time that they saw how far ahead SGI was.

DESCHALL keyspace complete: 16.503%
Solnet keyspace complete: 10.090%
SGI keyspace complete: 19.573%
Table 21. June 5 Keyspace Completed Comparison



Working with the same fundamental assumptions as in the previous
model”that each project was working independently, that their key
testing rates remained constant, and that nobody else was working on
the contest”some predictions could be made with Verser™s statistical
model. In particular, we could expect to ¬nd the right key in ¬fty-six
days.
On Saturday, June 7, Karl Runge looked over the statistics he gen-
erated from DESCHALL keyserver logs. As he realized that he was
looking at a report for another record day for DESCHALL, he smiled.
The previous day™s key search rate worked out to 4.4 billion keys per
second.
Terminal Velocity 243

Probability that a DESCHALL client will ¬nd the key: 51%
Probability that a SolNet client will ¬nd the key: 18%
Probability that a SGI client will ¬nd the key: 31%
Table 22. June 5 Probability of Success Comparison



Later on the same day in Reston, Virginia, Erik Fitchner, a Unix
system administrator quietly contributing his machines™ spare cycles to
DESCHALL was paying close attention to the number of keys that his
machines were testing. His 166 MHz Alpha machine started out testing
200,000 keys per second, and the ¬rst bitslice client for that platform
brought performance up to 540,000 keys per second. He couldn™t believe
his eyes as the latest client reported that it was testing 940,000 keys
per second.
Back in Toronto, Ken Chase was ¬‚oored as he looked over the
statistics for June 6. Like a race commentator watching the running
order change as the leaders head into the home stretch, he excitedly
reported the changes in the participants standings. Sun Microsystems
had dropped to ¬fteenth place, Apple Computer jumped up to third
place, and Penn State University dropped to ¬fth place. After rattling
o¬ the rest of the changes, Chase posted, “What™s going on?”
At Sun Microsystems in San Diego, software engineer John Falken-
thal read Chase™s report. Determined to have Sun regain its position
in the standings, he started up the new ultrafast client for the Ultra-
SPARC processor on the latest, fastest, hottest machine that Sun Mi-
crosystems made”the brand new “Star¬re” (Enterprise 10000) server,
which had sixty-four processors.
That one Star¬re server reported that it was processing 120 million
keys per second”the same rate that the entire DESCHALL project
sustained just about nine weeks earlier.
During the next week, I kept close tabs on our statistics. As client
improvements started to stack up, we were testing keys at a phenomenal
rate that just kept increasing. Back in April, when the project got going
in earnest, we had used press releases to get the word out. After that
time, we missed the opportunity to issue releases on our progress when
we had tested ten percent and twenty percent of the keyspace. With
twenty-¬ve percent rapidly approaching and Rocke Verser™s “expected
date of solution” calculation going from hundreds of years down to
weeks, it was now time to start thinking in less abstract terms about
what to do when we found the key. Speci¬cally, we had to be prepared
244 CHAPTER 35

to explain a lot of things to reporters and to help them to understand
why this DES Challenge contest should matter to people who didn™t
know anything about cryptography.
Although the DESCHALL project coordinators all recognized the
importance of handling the media correctly, we didn™t get to begin any
serious planning for when we found the key”a more pressing matter
was before us.


Friday, June 13, 3:31 P.M.
Loveland, Colorado

About a week after releasing the most blazing fast clients imaginable,
Rocke Verser composed a new announcement. The UltraSPARC users,
long in a strange position because their 64-bit hardware was running
a 32-bit operating system (Solaris 2.5), were about to ¬nd out that
Darrell Kindred had performed a Herculean technical task.
Like a tra¬c engineer who could ¬nd a way to maintain 64 lanes
of tra¬c on a 32-lane highway without causing any collisions, Kindred
found a way to make UltraSPARC processors perform 64-bit operations
reliably even though the operating system could only keep track of 32
bits at a time.
In addition, Verser found a way to improve the e¬ciency of the DES

<<

. 34
( 41 .)



>>