getting time on the processor, even when the user was running other
Getting Word Out 221
programs that needed the systemā™s processor. The end result was that
users noticed a performance degradation when DESCHALL was run-
ning, which was something that we explicitly advertised would not
Schleicher wanted to know whether the IRIX clients were faulty, or
whether there was some problem with the way that the IRIX operating
system was handling process scheduling. On the mailing list, we started
to discuss how DESCHALL worked with process schedulers and to look
into an answer for Schleicherā™s question.
The way that we were preventing the DESCHALL client from im-
pacting system users was dependent on the āpriorityā value that we
used when starting the software. This feature allows the process sched-
uler to understand when it has more than one program that wants the
processor, which one should go ļ¬rst.
Most computer programs spend a lot of time in idle loops. That
means that theyā™re literally just sitting there, waiting for something
(like input from the user) to happen. For example, a word processor
will need to perform many functions: it will need to be able to accept
input from the keyboard, ļ¬gure out how to place the text, and draw
the letters on the screen. Taxing as this might seem, the computer has
much more processing power than what is needed for that particular
job. The result is that other programs can run for tiny slice of time
(the cycles, or ticks) between a userā™s keystrokes.
A problem could develop if, for example, the user were trying to
use the word processor while sending a fax at the same time. If the fax
program gets just as much time on the processor as the word processor,
the user would wind up waiting for the fax program to yield its time so
the word processor could receive and process all of the input the user
gave it. To address this problem, modern operating systems have what
is known as a process scheduler, a part of the operating system that
will look at all of the programs that want to run and then decide which
program will get to run for each cycle of the processorā™s time.
At this point itā™s important to note that not all of the programs run-
ning on a given computer have the same priority. Programs that users
work with interactively need to be very responsive and thus cannot
jockey with other programs for time on the processor.
Other kinds of programs do not have such tight time constraints.
Performing a large scientiļ¬c calculation, for example, can take days
or weeks. Whether it takes an extra ten seconds or ten minutes will
222 CHAPTER 31
make no diļ¬erence to the user. The user perception makes this kind
of program dramatically diļ¬erent from a word processor, which could
not make a user wait for a second before displaying a typed letter on
The Unix family of operating systems has a basic facility for han-
dling these issues. Each process runs at what is known as a nice level.
That nice level is a number that represents priority on a scale between
ā’20 (the highest priority) and 20 (the lowest priority). Programs have
a nice level of 0 by default.
Nice levels help divvy up the systemā™s processing power appropri-
ately, since it allows more interactive programs to run at a higher prior-
ity than things that can go about their business without much concern
over whether the job is taking thirty or thirty-ļ¬ve hours.
In theory, very low priority processes would be things that you
wouldnā™t want to have running at all unless absolutely nothing else
would run. This was the kind of priority that we intended to attach to
DESCHALL clients. In practice, this turned out to be a litle bit harder
than we originally thought. During the course of the project, we started
to discover some minor diļ¬erences in the way that various operating
systemsā”even diļ¬erent operating systems that came from the same set
of source code before they divergedā”would handle process scheduling.
Darrell Kindred at Carnegie Mellon University was running DES-
CHALL on a variety of machinesā”some of which were running IRIXā”
so he took particular interest in Schleicherā™s question. Kindred noticed
that the other Unix systems were behaving as expected, so he started
to zero in on the way that IRIX speciļ¬cally handled process scheduling.
What he saw is that IRIX oļ¬ered a much greater level of control over
just how to share system processor.
IRIX provided a new commandā”npriā”which set a programā™s pri-
ority, not in terms of the standard Unix nice value, but in terms of
IRIXā™s granular pri value.
After having done this investigation, Kindred decided to start DES-
CHALL clients with a pri value of 150, which he understood to mean
that any other process asking for time on the processor would get it.
This solution was a much easier way to run DESCHALL than the nice
command would allow.
Kindred always liked to know what was really happening in the
computer. After posting his observations about IRIXā™s handling of pro-
cess priority, he started to look at other Unix systems around the lab
Getting Word Out 223
he worked in. He set about performing a series of tests during which
he would start programs with very low priority set by nice, and then
would run another program that wanted a lot of time on the processor
to see just how much time the operating system would grant to the
low-priority process. (Among the systems that he went about testing
were an older SunOS 4 system, the newer Solaris, known also as SunOS
5, Hewlett-Packardā™s HP-UX, IBMā™s Unix implementation called AIX,
NetBSD, and Linux.)
Something especially interestingā”and rather frustratingā”was that
AIX did not provide the granular control over processes that IRIX did,
and neither did a nice of 19 set the process priority to the low level that
one might expect. Some investigation led to the discovery that under
AIX, it was possible to do better than what nice was allowing.
Four hours after starting to look at the problem, Kindred posted
again to the DESCHALL mailing list, summarizing his ļ¬ndings, and
including the source code to a new program that he had written for
AIX, which he called verynice.
At last, we had deļ¬nitive answers to how we could ensure that DES-
CHALL clients would not interfere with normal system operations, even
on operating systems that had non-standard ways of setting system
priority. Schleicher simply used npri, and AIX users could use Kin-
dredā™s verynice program. Other Unix implementations correctly han-
dled the schedulingā”not giving DESCHALL any time unless nothing
else needed the processor.
Friday, May 23 was a frustrating day overall as we tried to under-
stand why the DESCHALL key testing rate had slowed, saw students
abandon their mailboxes, had DESCHALL clients banned from entire
university buildings, and tried to track down strange platform-speciļ¬c
process scheduling problems. But across the Atlantic, things were much,
SolNET had been keeping hard on our heels. As a project, they were
testing over 2 billion keys per second, compared to our 3.6 billion.
Besides having so many systems running its clients, SolNET had been
improving the speed of its clients. Though never as fast as DESCHALL
224 CHAPTER 31
clients, SolNET clients were getting faster, thanks in part to the work
that SolNET did on its own bitslicing clients.
While DESCHALL participants discussed process scheduling in
minute detail, the coordinators of SolNET were managing a real crisis.
Analysis revealed that some of the clients that were already released
were not testing all of the keyspace that they had been assigned. After
removing the problematic clients from the distribution points, Fredrik
Lindgren got the job of alerting SolNET users to the problem.
āWeā™ve found an ugly bug in the 32-bit bitslice clients,ā wrote Lind-
gren to the SolNET mailing list. āThis will require everybody to up-
grade their clients since we have to shut out all broken 1.11 clients.
Sorry for this screwup.ā
Saturday, May 24, 11:58 A.M.
MIT, Boston, Massachusetts
Nelson Minar sighed as he read Lindgrenā™s message. None of the par-
ticipants really wanted to see any of the projects suļ¬er any serious
setbacks, even if they were our competitors.
After looking over the SolNET project statistics page, he posted his
reaction to the DESCHALL mailing list.
Since the announcement [SolNETā™s] keyrate has dropped from
their recent 2 billion keys per second to 738 million keys per
second. . .
Itā™s worth taking a step back and learning from SolNETā™s re-
cent mishap. Is anyone on this list actively following SolNETā™s
development? What exactly was the bug? Can someone com-
ment on their quality control versus ours?
Minar asked good questions. Something that Rocke Verser took very
seriously was the process of client development, control over the process
of integration of source code, and testing of the clients before their
release. Not knowing SolNETā™s development process, though, we could
only speculate what might have happened there.
The costs of a bug in this type of computation are very high.
I donā™t want this or my earlier e-mail comparing keyrates
to sound like Iā™m denegrating SolNET. They are doing an ex-
cellent job of cracking DES [keys]. Our eļ¬orts are compatible,
Getting Word Out 225
any competition between DESCHALL and SolNET should be
SolNET should be commended for their organization and
openness. They have great mailing list archives, including an
open development list. They are giving out source code for their
clients (albeit with a small piece missingā”you canā™t actually
use the client to run on their keyservers). Making inforomation
available makes it much easier to understand what is going on
when a problem is discovered.
Saturday, May 24, 2:26 P.M.
Sun Microsystems, San Diego, California
Even while DESCHALL participants puzzled over SolNETā™s setback,
we received some welcome news. Someone at Sun Microsystems had
come on board. For the past two days, software engineer John Falken-
thal had been running around trying to get everything that he needed
to participate in DESCHALL.
Since Sun used ļ¬rewalls to limit the connectivity between its inter-
nal networks and the Internet, Falkenthal needed to get Justin Dolskeā™s
U2T software working inside of Sun to work through the ļ¬rewall. Once
he got the necessary software up and running, he started running DES-
CHALL clients on the Sun systems at Sunā™s San Diego engineering
The results of his ļ¬rst day of recruiting were impressive. Sun ap-
peared in the DESCHALL statistics as one of the top ten sites testing
keys on May 23.
Word continued to spread inside of Sun, and with other Sun employ-
ees starting to help by running DESCHALL client software on their ma-
chines, Sun Microsystems started making headway against other sites
participating in the eļ¬ort.
A few days later, Nelson Minar would smile as he read over the
previous days statistics. John Falkenthalā™s eļ¬orts inside of Sun seemed
to be paying oļ¬. Sun reached fourth place in keys tested May 27, passing
both MIT and Georgia Tech.
226 CHAPTER 31
Monday, May 26
Loveland, Colorado 12
Rocke Verser looked at the speed
the DESCHALL project was 6
searching the DES keyspace. It 4
had taken us roughly two months 2
to search one percent of the 0
keyspace. We passed the two per-
cent mark nine days later, the
three percent mark six days af- Fig. 10. Sum of DES Keys Tested, as a
ter that, and the four percent Percent of Total, March 14ā“May 29
mark in another four days. As
we built momentum and raced
through the keyspace at an ever-increasing rate, our āEstimated Time
to Fifty Percent Completionā statistic became less useful. Sure, it would
be a good ļ¬gure to have if we wanted to show how long it would take
us to ļ¬nd DES keys on average with the DESCHALL project, but we
were looking for one key, and we wanted participants to know when to
expect to ļ¬nd the one key we wanted before they became distracted or
discouraged and dropped out of the race.
Verserā™s answer was a āTime of Completionā report, posted to the
DESCHALL list for the ļ¬rst time on May 28, analyzing the previ-
ous dayā™s activity. In the report, he noted that DESCHALLā™s previous
ātime to ļ¬fty percent completionā ļ¬gure rapidly became a meaning-
less statistic, that a more accurate measure was the time remaining to
searching ļ¬fty percent of the remaining keys. Additionally, instead of
statistically assuming that DESCHALL was the only project working
on the problem, Verser built a model that looked at both DESCHALL
and SolNETā™s activity. Verserā™s ļ¬rst report was as follows.
Given the āfactual dataā and the āassumptionsā below, the āre-
sultsā of this model are believed (not guaranteed) to be mathe-
matically correct to within one day and to within two percentage
Getting Word Out 227
DESCHALL keyrate 4.014 billion keys/sec.
over last 24 hours
SolNET keyrate 1.738 billion keys/sec.
over last 24 hours
DESCHALL keyspace [tested] 12.193%
SolNET keyspace [tested] 7.849%
ā¢ DESCHALL and SolNET are working independently.
ā¢ Each groupā™s keyspace rate remains constant at the levels
ā¢ Nobody else on the planet is working on the RSA DES Chal-