<<

. 18
( 41 .)



>>

If DES Violation Group managed to ¬nd the key, they would get the
prize money that RSA put on the table. Even so, RSA™s DES Challenge
was a bit like a scavenger hunt where after there was a winner, a prize
would be shared with everyone: any team ¬nding the right key would
hasten the development of a stronger standard to replace DES”a prize
for everyone”but we were all hoping to be the one that found the key.
Interestingly, DES Violation Group, like DESCHALL, was based in
North America and made the same decision that we did”to restrict the
distribution of clients to the U.S. and Canada. Also like DESCHALL,
DES Violation Group used the North American Cryptography Archive
to distribute its client software without violating U.S. cryptographic
export policy.
Of the U.S.-based systems for participating in the DES Challenge,
DESCHALL was most e¬ective in its publicity, because, among other
factors, the tremendous speed of our clients and our participants™ zeal
in recruiting their colleagues and friends to join the project. Unfortu-
nately, the fact that there were clients in the archive for DES Violation
Group (with names beginning with “des”) and clients for DESCHALL
(starting with “deschall”) was confusing. That confusion led some peo-
ple who heard about DESCHALL to go to the site to download the
Progress 117

client and pick up the ¬rst DES Challenge client in the alphabetical
list”which was for the DES Violation Group.


Friday, April 11, 1:56 A.M.
Rensselaer Polytechnic Institute, Troy, New York

RPI student Bill Moller understood why groups in the U.S. were not
trying to get people from outside of the country to help on their e¬orts.
He could also see why cryptographers in the U.S. and Canada were not
especially interested in just sitting back and waiting for a group from
Europe or somewhere else to prove the point that they have been trying
to make for years”that 56-bit keys are just too small and are subject to
brute-force attacks. What Moller did not understand is why there were
multiple U.S.-based projects working on the same goal. Presumably, the
people working on both of these projects were under no legal restriction
that would prevent them from working together.
Moller posted his concerns to the DESCHALL mailing list. In par-
ticular, he wanted to know just why two U.S.-based groups were com-
peting instead of working with each other. Apparently he ¬gured that,
say, 1000 users working together on one coordinated e¬ort would ¬nd
the key faster than 1000 users spread across two or three competing
projects.
Answers to Moller™s question proved interesting. Some pointed out
that only DESCHALL supported their platform. (This was something
we heard over and over again throughout the course of the project,
particularly from the users of operating systems like OS/2. Although
relatively small in number, these users were advocates, able to draw
large numbers of others to the project.)
Some participants pointed out that having multiple groups working
on the same problem was good insurance, so that if a group had a
problem with its software, or for some other reason failed to ¬nd the
correct key, the other groups could pick up the slack. Still others high-
lighted the possibility of rogue clients falsely reporting that they had
tested certain keys, so having one project test keys that other projects
had presumably tested wasn™t always necessarily a bad idea. In fact,
Peter Trei™s uncoordinated DESKR software was developed speci¬cally
to deal with these kinds of problems.
Rocke Verser suggested that if competition were a problem (and
he didn™t say that it was), the question of why we were “competing”
118 CHAPTER 15

should be directed to DES Violation Group, rather than DESCHALL.
The DESCHALL keyserver had been online since January and clients
were available to the public since February. We didn™t really know where
DES Violation Group came from or the people behind it, but it seemed
to emerge some time after DESCHALL was already up and running.
Despite the confusion about clients from two groups being dis-
tributed from the same archive, DESCHALL continued to widen its
lead over DES Violation Group. The European DES-Challenge group
that spun o¬ from Germano Caronni™s 48-bit RC5 crack had been writ-
ten o¬ by even most of its organizers, who had since joined the SolNET
e¬ort.
DESCHALL was the fastest DES Challenge contestant, and was
getting faster almost every day. The basic statistical information we
did report”number of keys tested per day and total number of keys
tested to date”was enough to show our lead, but many participants
wanted to see more details. Much of this desire was probably inspired
by some competing projects, which really did have extensive statistical
reporting mechanisms on their project Web sites, showing breakdowns
per domain, creating line graphs of various participants™ e¬ort. DES
Violation Group in particular had extremely impressive graphical re-
ports that looked much like the charts generated to support analysis of
stocks and bonds. Oregon State™s Adam Haberlach quipped that DES
Violation Group was probably using more CPU time for computing
stats than they did for testing keys.
Although DESCHALL had by far the most primitive statistical re-
ports of any coordinated e¬ort, we were taking the need for better
reporting seriously. Justin Dolske created a program on April 4 that
would take the previous night™s raw data”as posted on Verser™s project
status Web page”and create graphs that would show our progress,
showing keys tested per day, and total keys tested. These graphs
charted the progress of the project as a whole. Participants liked to
see how the project was doing overall, but they wanted more. They
really wanted to see how their organizations were doing individually.
Dolske continued to work on ways to present DESCHALL statistics
graphically, hoping to ¬nd a way to let participants see their own con-
tributions over time. On April 21, Dolske announced his work and that
he was looking for people to test his dynamic graph-generating software
that came to be known as “Graph-O-Matic.” Rather than seeing only
the progress of the entire project, Graph-O-Matic was a web-based util-
Progress 119

ity which provided data for any domain whose progress you wanted to
check, and receive back graphs showing the progress of those domains
only.
The day before Graph-O-Matic opened for testing, Karl Runge from
Lawrence Livermore National Laboratory posted a note of his own to
the DESCHALL mailing list about some of the work that he had been
doing in looking at the project statistics. He had been using the re-
ported statistics to generate some graphs that could be used for analysis
that would help us understand what to expect in the days and weeks
ahead. By mid-April, our key testing rate really began to pick up”
doubling every seven to eight days for the past month. Runge showed
our progress on a graph plotted atop a mathematically proper exponen-
tial curve showing that participants who called our growth exponential
were not exaggerating.
Using the graphs to show past progress and to project future rates,
we could see that despite the tremendous amount of work that re-
mained, there was light at the end of the tunnel. In fact, if we could
sustain our exponential growth, we would have have half of the keys
tested after eighty-seven days of work (only ¬fteen days away!), and
the entire keyspace tested in ninety-six days, about the end of the ¬rst
week of June.
Runge himself called attention to a problem with using his projec-
tions to show when we would ¬nish testing half or all of the keyspace.
On April 18, we just ¬nished the milestone of having tested one percent
of the total DES keyspace. As any statistician will con¬rm, taking per-
formance for the ¬rst one percent of a project like this and using it to
predict the next 49 (or 99!) percent would be stretching the data. The
model for analysis was ¬ne”but we were just too early in the project
to have enough data to show things like how the project would react if
it ran into any trouble.
After a month of exponential growth, we were starting to get things
moving. We needed to sustain the growth in order to continue pulling
ahead of the competition.
16
Trouble




Saturday, April 12, 11:42 P.M.
Rutgers University, Piscataway, New Jersey

At Rutgers, like universities all over the country, the semester was start-
ing to wind down. While the year had not o¬cially drawn to a close,
in the minds of students and probably more than a few of their profes-
sors, it was e¬ectively ¬nished. Student Scott McIntyre started think-
ing about summer vacation”going back home, visiting old friends, and
spending time with family. As he thought about what summer would
bring, he realized that many students who were participating in DES-
CHALL might not be able to be involved in the project over the sum-
mer, particularly if they didn™t have ready access to the Internet or
large numbers of more powerful computers.
McIntyre decided to post his observation that, in another month
or so, students were going to be heading home for the summer, and
predicted a likely decrease in DESCHALL™s performance. The message
set the mailing list abuzz and the group quickly started to look at our
top key testers. (The top thirteen key testers for the day are shown
in Table 6.) Ten of the top thirteen contributors were universities and
another was a high school. If all of the students running clients on
those sites were leaving for the summer, they would take a lot of our
computing power with them.
Mailing list participants debated the severity of the problem. Some,
including Drew Hamilton of Strategy Management Laboratory Corp.
reasoned that it wouldn™t make any di¬erence, since students were going
to be running the software on their own systems, and it didn™t make

121
122 CHAPTER 16

Keys tested Clients Contributor
4.26 Trillion 275 Oregon State University, Corvallis
3.31 Trillion 117 Rensselaer Polytechnic Institute, Troy, New York
1.98 Trillion 1 DESCHALL U2T/T2U Proxy Users (Aggregate)
1.64 Trillion 91 Michigan Technological University, Houghton
1.48 Trillion 197 Ohio State University, Columbus
1.36 Trillion 61 Rochester Institute of Technology, New York
1.17 Trillion 164 Brigham Young University, Provo, Utah
1.06 Trillion 39 Worcester Polytechnic Institute, Massachusetts
0.77 Trillion 14 Apsylog Development, Nanterre, France
0.77 Trillion 27 Duke University, Durham, North Carolina
0.72 Trillion 27 Michigan State University, East Lansing
0.71 Trillion 11 University of California, Davis
0.71 Trillion 28 Thomas Je¬erson High School for Science and Tech-
nology, Alexandria, Virginia
Table 6. Top Thirteen Key Testers for April 12




any di¬erence whether those systems were plugged into the university
network or not.
Others, including Brian Osman, a student helping to coordinate
DESCHALL participation at RPI (Rensselaer Polytechnic Institute),
pointed out how much of the total key testing was being done on
student-owned machines that would almost certainly need to use in-
convenient dial-up connections and compete for time on the telephone
line with other family members. Without easy Internet access, many
of those systems would probably not be running the clients that they
would if they were sitting in the dorms wired for constant high-speed
access delivered through permanent local area networks.
Being among the optimists, I suggested several things that would
help us to be able to continue to test keys at a phenomenal rate. First,
we needed to develop optimized clients for architectures other than
those based on Intel™s 80486, Pentium, and Pentium Pro processors.
Those kinds of systems from providers like Sun Microsystems, Silicon
Graphics, Inc. (SGI), and Digital Equipment Corporation (known gen-
erally as DEC) were plentiful in research and academic laboratories.
Even with the comparatively few graduate and summer students who
would still be using them, university computer labs would be doing
much less “real work” than they did the rest of the year, leaving more
processing power available for testing keys. Getting client software more
heavily optimized for these systems, many of which were already run-
ning DESCHALL clients, could greatly improve their e¬ciency. If those
Trouble 123

systems™ clients could be made to be as e¬cient as the Intel clients”
which would mean performing the optimization work manually”they
would be dramatically faster than the Intel systems.
Second, we could raise awareness among other computer users who
would not only run the client but would also get others to run the
client. Internet Service Providers (ISPs) might be a good way to get
many others interested. Many ISPs created little online communities
for their users, and if we could convince ISPs to encourage their users
to run the DESCHALL clients, we might be able to fan a few ¬‚ames
of friendly rivalry among local and regional ISPs that we managed to
stoke among universities. Perhaps ISP system administrators would
take to checking the DESCHALL project statistics day after day, try-
ing to get their networks higher in the rankings. We had not seriously
attempted to recruit ISPs up to this point, but the idea seemed rea-
sonable enough and in any case was worth considering as a source of
potential computing power.
Finally, once DESCHALL gained the ability to work nicely with
¬rewalls, corporate environments, and others whose systems were pre-
viously unable to participate would be able to join in the e¬ort. Justin
Dolske had written the code at this point. Rocke Verser and I were test-
ing the software and working with Dolske to make the proxies ready for
production. We were less than a week away from making the ¬rewall-
friendly proxies available. The way I saw it, we had plenty of opportu-
nities to get new participants running the clients, so even if we did lose
the academic contribution, we could keep growing.
Dolske didn™t think that we needed to worry about losing the uni-
versities over the summer. Since he was a grad student and would not
be leaving for the summer, he would continue to run the client at Ohio
State. He suggested that school contributors simply ¬nd grad students
who would be around all summer and recruit them to keep the clients
running.
Besides, the statistical analysis Karl Runge just performed showed
that if we could maintain our exponential growth over the next ¬f-
teen to twenty days, we™d almost certainly ¬nd the key before summer
got underway. The summer vacation problem could prove to be, well,
academic.
124 CHAPTER 16

Wednesday, April 16
Yale University, New Haven, Connecticut

“Well, these are the newest computers we have and we don™t want to
wear out the processors.”
Computer science student Jensen Harris was glaring in disbelief at
the computer lab manager. With the blessing of the lab™s manager,
Harris had been running the DESCHALL client on ¬fteen Linux work-
stations for the past day. Each of these systems was an HP with a 166
MHz Pentium processor. After watching how the process ran, the lab
managers decided to stop them and to tell Harris that he was not al-
lowed to use the systems for DESCHALL. The systems sat completely

<<

. 18
( 41 .)



>>