<<

. 19
( 41 .)



>>

idle, all day long, waiting for the beginning of a project that would not
start until June.
“It probably also voids our warranty with HP to run programs like
this because it is an undue strain on the processor.”
Harris could not believe his ears: he knew perfectly well that whether
the computer was sitting idle or performing the world™s biggest com-
putation was irrelevant to the processor. For each cycle, the processor
would simply perform an operation. If it had no operation at all to
perform, it would perform a “no-op,” an operation that means “no op-
eration” and simply keeps the processor occupied until the next cycle
starts.
The lab manager continued, “Processors like these are only ˜rated™ a
couple of thousand cycles per minute”going over that is not something
we™re about to attempt without studying the e¬ects beforehand.”
Wisely, Harris set aside the urge to engage in an act of violence.
A processor of 166 MHz was indeed ˜rated™”for 166 million cycles per
second”and nothing that could be done in software could change that.
DESCHALL had some amazing software, but the clients weren™t magic;
our client just couldn™t make a processor run at a higher speed.
“Tell them that if they can make a nice client that doesn™t run the
processor too hard, we™d be happy to help.”
Harris knew that not much could be done with someone who was
both nice enough to look at the problem and to o¬er help if some
accommodations could be made but clueless enough to think that the
processors could ˜wear out.™ He walked away, shaking his head. At least
he could run the client on the computer in his dorm room.
Trouble 125

Friday, April 18, 6:13 p.m.
Northwestern University, Evanston, Illinois

Yale was not be the only university to ban DESCHALL clients. Com-
puter science student Vijay S. Gadad reported that his department at
NWU wasn™t interested in working on the DESCHALL project, as they
couldn™t see “why they should be helping RSA.”
Apparently, some administrators were under the impression that
this project was somehow helpful to a private, for-pro¬t company, and
that their resources should not be used. Upon learning that RSA was
actually giving prize money, administrators further objected on the
grounds that students would be participating in the e¬ort for personal
pro¬t. Administrators would often not listen to the explanation that
the university itself would actually get the money.
Many DESCHALL participants reported that they also had di¬-
culty getting system administrators and operational sta¬ to understand
that the software was actually quite friendly to the system. Many would
just see the system devoting a lot of time to a single program and
assume that it was somehow hurting something. But nothing topped
Harris™ experience with the sta¬ who thought that an idle CPU cycle
is somehow less demanding than a “busy” one.
Some participants were quick to heap scorn upon the lab managers
who obviously had no understanding of how computers worked. For me,
these stories were an eye-opening experience”I assumed that everyone
who worked with computers every day simply knew how they worked.
The DESCHALL project was providing an excellent opportunity for
participants who didn™t know how computers worked to learn. But
more importantly, we had DES keys to test, and we needed to get to get
more people involved. We could allow ourselves to become downhearted
if we only looked ahead at how much work yet remained. Watching a
few milestones go by would help us to stay motivated.
17
Milestones




Thursday, April 17
Loveland, Colorado

DESCHALL reached a signi¬cant milestone when we ¬nished testing
the ¬rst one percent of the keyspace. Seven hundred twenty-one trillion
down, a few quadrillion to go.
To draw attention to the achievement, we issued our second press
release. After quickly describing the project for readers who had not
yet learned about DESCHALL, we wrote:

According to Rocke Verser, a contract programmer and consul-
tant, who developed the specialized software in his spare time,
“There are over 2500 computers now working cooperatively on
the challenge.”
Using a technique called “brute-force,” computers partici-
pating in the challenge are simply trying every possible key.
“There are over 72 quadrillion keys. A number,” Verser quips,
“about 15,000 times larger than the de¬cit.”
But the DESCHALL group is racing through the keys at an
incredible pace. The group is now trying over 50 trillion keys
per day”or more than 600 million keys per second.
Perhaps even more impressive, the number of computers par-
ticipating, and the rate at which they are trying keys has been
doubling every eight to eleven days for the past two months.
If the number of participants continues to double every ten
days, it should take about two months to ¬nd the key. If no


127
128 CHAPTER 17

other participants joined the e¬ort, it should take about two
years to ¬nd the key.
Word of this cooperative e¬ort has spread primarily by word
of mouth and the Internet equivalents”IRC, newsgroups, and
mailing lists.
No one knows where the growth of this type of cooperative
computing e¬ort will peak.
“Members of the DESCHALL team will be in a festive mood,
Friday,” Verser predicts. “About supper time” on Friday [April
18], DESCHALL computers will have tested one percent of the
total set of 72 quadrillion keys.

As our machines continued to test keys, we put the notice up on the
Web site and participants began to distribute it to their local media
outlets. We passed the milestones as expected.


Monday, April 21, 9:39 A.M.
Megasoft Online, Columbus, Ohio

One of my DESCHALL clients ¬nished testing a block of keys and sent
a message to the keyserver that it was ¬nished and was ready to receive
another block. After a few minutes went by, the client attempted to
send the message again, still without response. Working on something
else, I did not immediately notice that the client was having trouble.
About an hour after the client started waiting for more work to do, I
returned to my e-mail.
Several participants sent messages to the DESCHALL mailing list
to see whether others were having di¬culty reaching the keyserver. I
checked my clients and saw one waiting. I quickly started a network
utility called traceroute, which would show response times between my
system and every hop along the way to the keyserver. With traceroute
output, I would be able to tell whether my systems could reach the
keyserver, or if not, just how close I could get.
The results showed that not only was the keyserver unavailable,
but a whole section of a network that connected the keyserver to the
Internet were o¬„ine. I picked up the phone and dialed Rocke Verser™s
home number.
Milestones 129

Monday, April 21, 7:40 A.M.
Loveland, Colorado

After a long night of developing new DESCHALL clients, compiling
project statistics, managing server logs, and coordinating the e¬orts of
other client developers, Verser was sound asleep when the phone rang.
He picked up the phone to hear me announce that the keyserver
and its network was o¬„ine. After thanking me for calling, he went
to the keyserver in his home o¬ce and saw something that he did
not frequently see: the modem connecting his home o¬ce network to
the Internet was o¬„ine and not correcting itself. Although using a
modem, Verser did not use it as standard dial-up customers did; he
had dedicated service. The modem never disconnected unless there was
a problem, and if that happened, his system would recognize it and
immediately reconnect.
After some quick work, Verser restored the connection, and the key-
server became visible to the Internet. Messages, including the one from
my client that had been waiting, started to ¬‚ow in once again. The
outage, which lasted for approximately three hours, was long enough
for only a few participants to notice. Certainly the problem could have
been much, much worse.
Verser watched to ensure the system was working properly, typed
an e-mail message to project coordinators describing the problem and
his assessment of its impact, and went back to bed.




Less than one week after passing our ¬rst major milestone (completion
of the ¬rst one percent of the keyspace), we passed another: we ¬nished
testing 1 quadrillion keys on Tuesday, April 22. But for the remainder
of that week, our growth rate began to slow. Although still growing at
a fast pace, graphs of our progress started to show that the exponential
curve wasn™t holding.
Michael J. Gebis from Purdue looked at the DESCHALL “keys
tested per day” statistics on April 24 and noted that the number of keys
tested was starting to resemble a sigmoid curve. In a sigmoid (basically
S-shaped curve), the ¬rst part looks exponential, but then the curve
130 CHAPTER 17

becomes linear until it reaches
90
a peak and then it levels out. 80
He suggested that it was possi- 70
60
ble that we had passed our ex- 50
ponential growth spurt, and we 40
30
might see only linear growth in
20
the future. Although the predic- 10
tion was disappointing consider- 0




Apr 19
Apr 12
Apr 05
Mar 29
Mar 22
Mar 15
ing the progress made over the
previous weekend, no one look-
ing at the data could seriously
advance a more optimistic argu- Fig. 5. DESCHALL Keys Tested Per Day,
March 14“April 24 (in Trillions)
ment.


Thursday, April 24, 3:57 P.M.
Lawrence Livermore National Laboratory, California

Concern over the reduction in our growth rate led some participants on
the mailing list to raise questions about competing projects “wasting”
time and e¬ort. Karl Runge, our resident statistician, started crunching
some numbers to get some sense of how long it would take to ¬nd the
right key with two DES Challenge projects. He compared the average
search time for two cooperating servers to the average search time for
two non-cooperating servers.
DESCHALL™s overall computing power had grown tremendously
in the past six weeks. From March 14 to April 23, our growth rate
followed an exponential curve, even if the developments of the past
few days made it appear to be unsustainable. At the beginning of that
curve, we estimated that it would take us roughly seventy-¬ve years
to ¬nd DES keys on average, and by April 24, the ¬gure had dropped
to under fourteen months. Runge found that the average search time
would be sixty-seven days (from March 14) for two cooperating servers.
For two independent servers, average search time would be only about
two days longer. This had a lot to do with the number of keys being
tested toward the end of the project, which was the highest part of the
end of the exponential curve.
Having two cooperating projects would make more sense in the case
of linear growth, since it would spread the key testing out over a larger
period of time. With cooperating keyservers following the linear growth
Milestones 131

that was apparent from April 11 to April 23, the time to ¬nd the key
would be 109 days (from March 14) on average. Non-cooperating servers
starting on March 14 would ¬nd the right key 121 days later on average.
The diference was not very large. Obviously, a prolonged e¬ort with
a lower growth rate over time would bene¬t from using multiple, coop-
erating keyservers. However in our case it was clear that it didn™t really
make sense for us to join forces with another group. Runge observed
that after all the math was done, he had learned what his two children
had been telling him for years: it doesn™t pay to cooperate.
We didn™t have to wait long for Runge™s words to prove themselves.
Within a few days, DESCHALL went on to set many new records. On
Friday, April 25, the project maintained a key testing rate of over 1
billion per second for an entire 24-hour period. On Saturday, April 26,
we tested more than 100 trillion keys in a day for the ¬rst time. At that
rate, our key testing rate was such that if simply sustained, we would
reach the halfway mark in under one year.
By Sunday, April 27, we had tested two percent of the entire
keyspace. Testing the ¬rst one percent of the keyspace took us ninety
days by RSA™s count. Testing the second percent had taken a mere ten
days.
By the end of April, DESCHALL had transformed from a sin-
gle person in Colorado with some fast DES key-testing software to
a fully-functional virtual organization, with development, project man-
agement, communications, and recruitment functions being addressed
by volunteers. Still more people started to take note and we began hear-
ing from people who could not participate but wanted to encourage us,
or whose participation would be limited.
The most visible gap in our client o¬erings was for Macintosh ma-
chines. We had been getting a great deal of help from the enthusiastic
OS/2 crowd. Especially since we began to report statistics showing how
many keys were being tested per platform. We were pretty sure that
we could get a big boost from the availability of a Macintosh client,
who were also known to advocate their favorite computing platform
with zeal. Many writers in the mainstream computing media had writ-
ten o¬ the Mac and OS/2 as irrelevant, ¬guring that “everyone” used
Windows. The users of these marginalized systems often sought oppor-
tunities to contradict the myth of Windows ubiquity, and any study or

<<

. 19
( 41 .)



>>