<<

. 25
( 41 .)



>>

much more quickly.
80
Nelson Minar also started
60
40 paying attention to the standings
20
of various teams of participants,
0
seeing how MIT was doing by
Apr 26
Apr 19
Apr 12
Apr 05
Mar 29
Mar 22
Mar 15




comparison to some other univer-
sities.
Around the same time, Colin
Fig. 6. Keys Tested per Day, in Trillions
Hildinger compared our most re-
cent statistics with SolNET™s.
While we had searched two-tenths of one percent of the DES keyspace
the previous day, SolNet managed to search two-and-a-half-tenths of
one percent in a nearby twenty-four hour period. Because of delays
in getting statistics calculated and published, we wouldn™t know until
the following day”May 3”how exactly we would compare. But it was
obvious that DESCHALL and SolNet were running neck and neck.

Keys Clients Domain / University
17.0 Trillion 393 uiuc.edu,
University of Illinois at Urbana-Champaign
7.3 Trillion 372 orst.edu,
Oregon State University
5.9 Trillion 191 mit.edu,
Massachusetts Institute of Technology
5.7 Trillion 203 mtu.edu,
Michigan Technological University
5.4 Trillion 187 cmu.edu,
Carnegie Mellon University
Table 10. Comparison Among Universities, May 2



Although SolNET was closing on our key testing rate, we were still
far ahead in terms of total keys tested and our clients were so much
more e¬cient than the SolNET clients. There just wasn™t any way for
Recruiting 171

either project to back down at this point”SolNET users outside of the
U.S. couldn™t get to our software, and DESCHALL participants didn™t
want to run slower key testing software. The only option was to drive
forward, turning up the heat on one another in the process.
Meanwhile, IBM™s chess-playing computer, Deep Blue, was slated
to play against the world™s highest-rated chess player, Garry Kasparov,
in another week. (Deep Blue would go on to win in a highly-contested
match, the ¬rst time that a computer ever defeated a reigning chess
champion.) Nate Boyd, from MIT™s Computer Graphics Group, sug-
gested that we try to recruit Deep Blue for cracking keys. Boyd was
joking, but in 1998 the Electronic Frontier Foundation, an online civil
liberty group would fund the development of a DES key-cracking ma-
chine called “Deep Crack,” a special-purpose computer built for the
sole purpose of cracking DES keys faster than software ever could.
Instead of trying to recruit Deep Blue, Justin Dolske tried to get
some attention for DESCHALL by submitting an article to
comp.os.linux.announce, the same newsgroup that had carried the RC5
announcement that had so recently caused a stir among DESCHALL
participants. Given that the moderators had allowed Mike Driscoll™s
article about the RC5 Bovine e¬ort to be released, Dolske thought
that interest in cryptography would be high enough to warrant some
publicity for DESCHALL. Dolske™s announcement, just like Driscoll™s
RC5-56 announcement, was simple and to the point: what the DES-
CHALL project is, why it is important, and how to join.
The newsgroup moderators didn™t seem to agree, and rejected
Dolske™s post, on the grounds that they just allowed something about
the RC5 e¬ort recently. Even more strangely, after rejecting Dolske™s
message, the same moderators allowed for another post for an RC5
e¬ort. The moderators never answered questions about their decision,
leaving some to conclude that there was some bias against DES (or in
favor of RC5) e¬orts. This little mystery remains.
I could think of no reason to reject Dolske™s announcement about
DESCHALL. DES was a real standard, even used in the Linux operat-
ing system. RC5™s use was not nearly as widespread, the 56-bit key size
was not a typical con¬guration for RC5, and there was no direct con-
nection between the Linux operating system and RC5. The decision to
reject Dolske™s post seemed completely arbitrary, and the piece might
have appeared if a di¬erent moderator happened to see the submission.
172 CHAPTER 25




After no small amount of concern about if (and when) SolNET was
going to surpass our key search speed, we started taking a harder look
at the numbers in order to get a better grasp on the progress being
made by both projects.
SolNET™s progress statistics were based on the number of clients
that checked in with the keyserver during a given half-hour period.
Some DESCHALL participants thought that all of SolNET™s clients
were checking in every half-hour and thus assumed that the statistics
re¬‚ected the combined e¬orts of the entire project. On May 4, Rocke
Verser pointed out that computers running the client software report-
ing their progress in that half-hour window were most likely reporting
more than one half-hour™s worth of work; many other clients were busy
testing keys, but did not have any results to report back to the key-
server during that time. Applying the same metric to our own progress,
Verser wrote, “In the last 60 seconds, 180 DESCHALL clients reported
122 billion keys tested. (Wow! We™re testing over 2 billion keys per
second with only 180 clients!)”
As it turned out, the keyserver numbers were really only useful for
showing how much of a load the keyservers were maintaining. SolNET™s
keyservers were taking roughly two hits per second from their clients,
whereas the DESCHALL keyserver was taking about three hits per
second from the clients.
Looking at total project speed for comparison, Verser could see that
SolNET was testing just under 2 billion keys per second, whereas DES-
CHALL was testing just over 2 billion keys per second.
Verser correctly concluded that SolNET had more clients”more
than three times as many computers running their client software”
but DESCHALL had faster clients.
Unfortunately for SolNET, their numbers turned out to be less im-
pressive then they had intially appeared. Fredrik Lindgren con¬rmed
on SolNET™s DES-Announce mailing list that some machines in Fin-
land were pretending to run SolNET clients, but actually were not.
Basically, someone examined the protocol running between client and
server in order to ¬gure out what exactly to send to a keyserver to im-
personate a client. Having ¬gured out the protocol between client and
server, the malicious client would simply send a “block ¬nished, but
key not found” message to a SolNET keyserver, without ever having
Recruiting 173

tested a single key. The goal of such an attack was to make the key-
server incorrectly record blocks as being tested, potentially preventing
the real key from being found.
This was exactly the kind of thing that everyone involved in dis-
tributed computing e¬orts worried about. No one really gets anything
out of an attack like this, but if it™s easy enough to do, some idiot
somewhere in the world is certain to try it. Lindgren and other Sol-
NET coordinators had their hands full trying to assess the damage and
building a plan for recovery, so they did not bother trying to ¬gure out
who was behind it.
Many DESCHALL participants began to ask what we were doing to
prevent this kind of attack on our systems. I raised the issue privately
with Rocke Verser and Justin Dolske; we talked about the problem and
some of the defenses that we had in place, but never directly answered
the questions presented by general participants. If the attackers were
reading DESCHALL™s lists, we didn™t want to give them any clues
about what our weak points might be.
SolNET would not be completely undone by this attack, but it was
a setback. The bogus reports came from a particular network on the
Internet, allowing for all of those reports to be discarded, ensuring that
those keys would be tested by another client later. If any legitimate
testing had been done, those would be lost, but the integrity of the
project was critical and it was better to retest a key that had been
tested once than to miss a key that was falsely reported as tested.
26
Threats




While SolNET was recovering from its attack, the DESCHALL team
turned to other issues. Having enabled the basic mechanism for search-
ing for DES keys on thousands of machines, of dozens of types, from
all over the United States and Canada, our project had become quite
visible, and it was possible that the same attackers who targeted Sol-
NET might try to foil us. We did not want just to worry about what
kinds of bad things could happen; we wanted to anticipate the most
likely threats so that we could methodically address them.


Sunday, May 4, 2:20 A.M.
University of Texas at Austin

As DESCHALL participant Seth Johnson read CNET news, he found
an article that discussed a math bug in the Intel Pentium Pro micro-
processor. The article speci¬cally described a problem that could cause
some calculations to be done incorrectly. Users wouldn™t generally no-
tice the problem; it was the kind of obscure thing that only people
performing heavily numerical scienti¬c work would ever encounter in a
meaningful way.
Ordinarily Johnson would not have been interested in the problem,
since his Macintosh did not use an Intel processor, but now that he was
participating in DESCHALL, he had cause for concern since so much of
what DESCHALL was accomplishing was on Intel processors. If the bug
a¬ected the way that DESCHALL ran on Pentium Pro processors, we
might need to throw out huge amounts of completed work to calculate
those key blocks correctly. A problem like that would be a terrible
setback”possibly setting us back more than a month.

175
176 CHAPTER 26

Since the new problem a¬ected relatively few applications, Johnson
didn™t want to create panic, but he did want to know whether this was
a serious concern for DESCHALL.
Fortunately, the integrity of the DESCHALL results was not af-
fected. As it turned out, the bug was limited to the ¬‚oating-point unit
of the microprocessor, where operations on “¬‚oating-point” numbers”
numbers with decimals like 3.141592654”would be handled.
Since computing DES keys was done by working with 56-bit bi-
nary numbers and never performing any division operations that could
leave a remainder, DESCHALL software had no need for ¬‚oating-point
operations, using only integer”“whole number””operations.
While that particular processor bug did not a¬ect DESCHALL, it
did give us cause to think about some potential setbacks. Among those
concerns were the possibility of long-term network outages making the
keyserver unreachable and our potential vulnerability to attacks from
malicious clients reporting bogus results back to the keyserver.
In general, a network outage wasn™t likely to be a big problem.
A DESCHALL client would work through the keys assigned by the
keyserver. Once it was ¬nished, it would attempt to report an update to
the keyserver and to request a new block of keys to test. If the keyserver
could not be reached, the client would simply resend its request at a
later time. If some of the clients have to wait for a few minutes, this
isn™t a big problem, but if the keyserver is o¬„ine for a longer period of
time, the impact grows quite a bit.
Assume for the purposes of illustration that the typical DESCHALL
client needs to talk to the keyserver every other hour. Also assume that
the other participating clients were started at evenly-distributed points
throughout any two-hour window. A network outage of ¬fteen minutes
would mean that the keyserver would be unavailable to respond to
clients during a time when one-eighth of the total number of clients
needed to check in. A thirty-minute outage would idle one-quarter of
our clients for some period of time. After two hours, virtually the en-
tire project would be at a standstill, with almost all clients waiting to
connect to the keyserver. Given our key testing rate at the beginning
of May, that would mean that 7.2 trillion keys per hour would not be
tested.
In reality, clients would not be started to evenly, but the assumptions
above demonstrate a critical point of the actual project: with less than
Threats 177

a half-day of unavailability, the world™s fastest distributed computer
would grind to a halt.
The concern about malicious clients reporting bad results back to
the server was one that came up on the Coderpunks mailing list, an
o¬shoot of the Cypherpunks list. While Cypherpunks dealt with polit-
ical, economic, and cultural issues as well as technical concerns about
cryptography, Coderpunks focused speci¬cally on the implementation
of cryptosystems. Many Coderpunks readers were watching all of the
RSA Secret Key Challenge contest projects, and more than a few were
participating in one of the projects.
After a discussion of various ways to deal with the problem, Coder-
punks subscribers concluded that the only sure way was to verify each
of the test results. Trying to ¬nd the right key among 256 was hard
enough. Checking each key twice was less appealing. However, if the
author of a malicious client was smart enough, there was no other sure
way of knowing that we were dealing with good results.
DESCHALL clients did have some safety features built in, though,
and thus was not wholly vulnerable. Although we did not reveal this
in detail to the DESCHALL mailing list, DESCHALL client devel-
opers knew that DESCHALL clients weren™t going to be too easy to
spoof. “Half-matches,” (see Chapter 13) for example, were reported,
and some number of half-matches would be expected over a set of a
certain size, so if Rocke Verser noticed a change in the expected half-
matches, that could indicate that someone was reporting bogus results
to the keyserver. Still, in spite of the precautions that we had taken, a
determined attacker would be nearly impossible to stop. We really were
just hoping that we could make it more di¬cult than it was worth.
Another problem that could arise would be if a client could somehow
prevent a “key found” message from being reported back to the server.
The client could, for example, get a key block, disconnect from the
network, and test the keys o¬„ine. Normally, if the client found the key,
it would send a message back to the keyserver. A malicious participant
might prevent his client from giving the “key found” message to the

<<

. 25
( 41 .)



>>