<<

. 32
( 41 .)



>>

Under the IRIX operating system, the DESCHALL client was still
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
happen.
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
screen.
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,
much worse.




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.
Minar continued,
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
entirely friendly.
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
facility.
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
14
Loveland, Colorado 12
10
Rocke Verser looked at the speed
8
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




May 24
May 10
Apr 26
Apr 12
Mar 29
Mar 15
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
points.
Getting Word Out 227

Factual data:

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%

Assumptions:
• DESCHALL and SolNET are working independently.
• Each group™s keyspace rate remains constant at the levels
shown above.
• Nobody else on the planet is working on the RSA DES Chal-
lenge.

<<

. 32
( 41 .)



>>