<<

. 22
( 41 .)



>>

software didn™t know how we were determining exportability, it did
serve its purpose. Plenty of people from ineligible areas of the world
did try to download our client software and were denied. To this day, I
know of no case where Dolske™s software allowed a download incorrectly.
Sometimes, the system refused to grant access for users who were
eligible to download, which is the reason why the form had a link on
it to send email to Dolske and me. Anytime that we got a request
from someone who said he should have access, we would investigate,
using basically the same methods as the software”looking at the IP
addresses and system names in the headers of the email request that we
received for additional con¬rmation. If the user was incorrectly denied
access, we would reply with a special password that could be fed to the
system that would allow the user to download the software. The user
could then answer the questions and put in the special password to be
granted access to the client archive.
DESCHALL key-cracking clients were available for about thirty-six
di¬erent platforms at this time, covering systems running Windows,
OS/2, many di¬erent variants of Unix, as well as a wide variety of
processor types. Within the week, new clients would be released for
146 CHAPTER 20

Macintosh systems that were optimized for the PowerPC 601 and 604
processor models. Users could download any number of clients once
they had been approved, so users with many di¬erent system types
could go through veri¬cation once and then download all of the appro-
priate clients without needing reveri¬cation.


Thursday, May 1
Megasoft Online, Freehold, New Jersey

Justin Dolske and I both ran o¬cial DESCHALL client archives”using
exactly the same software, and coordinated with each other so all of
the DESCHALL client software for download was identical. For the
¬rst few days of operation, we advertised Dolske™s distribution site at
Ohio State as the “primary” and mine at Megasoft as “secondary,”
available in case the primary wouldn™t work for some reason. After
feeling comfortable that the system was working properly and seeing
the kind of load that the system was putting on the underpowered
computer Dolske was using at Ohio State, we decided to reverse roles,
making my newer system at Megasoft act as the primary site, with
Dolske™s site acting as secondary.
We announced that the testing period was over, and the DES-
CHALL project had a new method for client distribution. While al-
ways grateful to Michael Paul Johnson for hosting our software on his
North American Cryptography Archive from the earliest days of the
e¬ort, DESCHALL would now only be available through its own client
distribution sites. No more confusion regarding which downloads were
for which projects.




Although it was frustrating to have to glean participants from a pool
of two countries, we felt we were making good progress nonetheless.
Just as we were passing the point of having two percent of the total
keyspace tested, however, one of our participants gave many of us cause
to wonder just how much the cryptography regulations limited our
e¬orts.
Download 147

Sunday, April 27, 1:15 p.m.
University of Alberta, Edmonton, Alberta

Fourth year honors computer science student Howard Cheng was check-
ing on our overseas competition and reading the SolNET project™s Web
site. Cheng read a ¬gure that prompted him to send an urgent message
to the DESCHALL mailing list: SolNET was claiming a spike in its
search rate up to 1.5 billion keys per second, while our most recent
statistics were showing only 1.16 billion keys per second. He correctly
observed that SolNET had an advantage in being able to recruit par-
ticipants from all over the world. SolNET seemed to have support from
easily a dozen di¬erent countries, while DESCHALL, working under re-
strictions on cryptography export, was limited to the U.S. and Canada.
Not everyone was alarmed by the news. Justin Dolske observed that
our rate had actually increased a bit to 1.25 billion keys per second.
Guy Albertelli also noted that SolNET was reporting peak rates, while
we were reporting the average number of keys tested over a 24-hour
period.
Furthermore, the reason behind the sudden increase in SolNET key
testing speed was no secret. It wasn™t even the result of an e¬ort to
recruit a large number of new participants. A single site, a university
in Taiwan, had started running 2000 SolNET clients over the weekend.
I quickly sent a message to the mailing list, reminding everyone that
our project had only really taken o¬ in April. Our ¬rewall-traversing
system had just been brought online and our client distribution system
had just been improved. Our best answer to any challenges would be
to recruit more people to run clients while the core DESCHALL team
continued to improve the system architecture and develop faster clients.
But where would we ¬nd more clients? Looking at really large
companies”AT&T, for example”reminded us that there were many
tens of thousands of desktop systems available in the U.S. and Canada.
If we could harness any signi¬cant part of that power, we could sustain
our amazing growth for quite some time. Considering that the previous
week had seen a 74 percent increase in speed up to a rate of 1.2 billion
keys tested per second with 3000 participating machines, the potential
seemed staggering.
By Tuesday, April 29, real comparisons were made between Sol-
NET and DESCHALL, and an online dialog began as users from both
camps debated the importance of the two organizations™ statistics. One
SolNET participant observed on its mailing list that DESCHALL was
148 CHAPTER 20

running at twice the speed of SolNET, that connectivity to our key-
server was better, and their e¬ort had not grown signi¬cantly since
their big boost over the previous weekend from the Taiwanese univer-
sity. In fact, they had network and server problems that ¬‚attened their
search rate.
Jeremy Bradley, a SolNET participant from Bristol University in the
UK, asserted on the SolNET mailing list that DESCHALL had three
“major weaknesses:” a single keyserver with an Intel 486 processor (to
which he added, “I say no more,” as if the computational power of
the keyserver had anything to do with the rate at which the keyspace
would be searched), di¬culty with statistics (as evidenced, he asserted,
by estimates being reported instead of precise ¬gures”something we
actually had not done since the middle of March), and our modest 3000
participating client machines versus SolNET™s 15,000 clients. Bradley
concluded with a prediction that SolNET would overtake DESCHALL
within a week or two.
Adam Haberlach at Oregon State University responded with a mes-
sage posted to the DESCHALL mailing list and copied to Bradley.
Therein, Haberlach pointed out that our 486 keyserver was working
just ¬ne and that we were more interested in computing the right key
than computing statistics. (In truth, our computers were busy search-
ing keys, leaving us to talk about statistics; we could argue that other
projects were busy computing statistics, leaving them free to talk about
searching keys.) Haberlach also argued that we actually had closer to
5000 clients”but even with one third the number of clients, we were
staying ahead of SolNET because our software was so much more e¬-
cient.
Whether DESCHALL was being hindered by being restricted to
the U.S. and Canada had already been considered several times by this
point, and we knew that many contest participants overseas would run
the DESCHALL clients if they could. With competition from SolNET
becoming more intense, more participants were more urgently needed.
Because SolNET was able to recruit from the entire world”including
North America, since EAR, like ITAR before it, applied only to ex-
port of clients; people in the U.S. could import any cryptography they
wanted”we knew that we needed to continue in our recruitment e¬orts
and improve our clients™ speed even further.
Iowa State University student Mikael Brown wrote to the DES-
CHALL mailing list, musing that there would be some risk in a foreign
Download 149

project successfully answering the challenge. While the success of a for-
eign group like SolNET might show the futility of attempting to control
crypto export to a technocrat, Brown noted that lawmakers had a ten-
dency to view things from a very di¬erent perspective. He didn™t need
to elaborate, because many of members of the cryptographic commu-
nity had long viewed legislatures and their restrictions on cryptographic
products as irrelevant to the world around them. Many believed that
the restrictions did nothing to stop the spread of cryptography to hos-
tile entities abroad, but only prevented law-abiding citizens from being
able to address global market needs. The danger Brown worried about
was that if a foreign project like SolNET actually won the challenge,
lawmakers might even attempt to increase the restrictions on cryptog-
raphy.
What the future of this type of legislation would be was debated
vigorously during the RSA contest. The discussion was not new to
the contest, however, and was part of the arguments advanced in the
Crypto Wars, the public policy debate on cryptography.
We could clearly see that U.S. policy disallowing the general export
of cryptographic software was negatively impacting DESCHALL™s abil-
ity to grow and helping SolNET to close the gap in performance.
Once again, we knew we urgently needed to get the clients running
on more machines, and we were going to have to grow our ranks by
appealing to a larger set of of users based in the U.S. and Canada.


Monday, April 28, 2:01 P.M.
The Ohio State University, Columbus, Ohio

DESCHALL coordinators were keenly aware of the challenges before
us and were anxious to help our enthusiastic group of participants get
more involved in the project. To that end, Justin Dolske composed a
message to the DESCHALL mailing list simply entitled, “Things you
can do.”
Among the things Dolske enumerated were an improved front-end
for the key-cracking clients, one that would allow for o¬„ine processing
and better support for automatic stopping and starting so the client
software would only work when no one was using the machine. This ¬rst
request called for programmers who were familiar with the C program-
ming language and who would be able to develp clients on Windows
and Unix systems. The programmers did not need a particularly strong
150 CHAPTER 20

knowledge of DES since those requested components would not involve
the key-testing parts of the client software.
Dolske also described a number of ways that someone might be
able to enhance our progress graphs and statistical reports. Dolske was
particularly interested in seeing someone develop a program that would
allow participants to build queries of progress on particular groups
of participants, such as all of the clients from a speci¬c company or
university, a feature that required more ¬‚exible system than the present
Graph-O-Matic. Dolske ¬nally called for people who could help us with
publicity. We needed participants who could distribute press releases
and explain the importance of the DESCHALL project to the media.
At this point in the project, DESCHALL™s advantage of fast clients
tied together with a capable and well-managed architecture was show-
ing itself. We intentionally focused on recruiting new participants and
enhancing core functionality instead taking the advice of some partic-
ipants who wanted us to add new features and start cooperating with
other projects. Rocke Verser decided”and other developers agreed”
that having another set of client software, built and maintained by a
di¬erent group of developers (from outside of the U.S.) for working
with the DESCHALL keyserver would be a horrible distraction from
what we did well, and that would probably not be possible to manage
e¬ectively. Dividing up the keyspace ahead of time and having, for ex-
ample, SolNET search part, while DESCHALL searched another part,
could be done if we had worked together from the beginning, but could
have proved di¬cult once the projects were already up and running.
Karl Runge™s April 24 calculations about expected search time showed
that the amount of return that we would have from working with an-
other project was minimal, especially in light of the additional e¬ort
that would be required to pull it o¬.
21
Short Circuit




Thursday, April 10, 12:41 A.M.
Megasoft Online, Columbus, Ohio

Mike Heroux at the University of Washington asked a good question.
He wanted to know why we didn™t write a client in Java so that it
could run on any type of computer, instead of spending so much time
and energy in platform-speci¬c versions. Answering on the DESCHALL
mailing list, I discussed the tremendous performance advantage that
some implementation strategies had over others. In particular, I pointed
to the speed of the 32-bit Pentium clients versus to the clients for
more powerful 64-bit processors. I observed that one of the best ways
to increase speed was to optimize the client heavily for the speci¬c
processor in use, as Verser had done with the Intel clients. Another
option I mentioned was the use of the “bitslicing” method described
in a recent paper by Israeli cryptographer Eli Biham.
In typical key-search algorithms, the computer™s processor will oper-
ate as it normally does”taking blocks of data and performing a series
of functions on them. Various techniques were available for reducing
the amount of work needed to test a key to see whether it was the right
key to unlock the block of data. Biham™s bitslicing key-search method
took a rather di¬erent view of the problem.
Rather than treating a processor as a single component that works
on numbers of a particular size (say, 64 bits), the processor is treated as
64 independent 1-bit processors. Thus, rather than the 64-bit proces-
sor changing from instruction to instruction through the course of the
processing, each “independent 1-bit processor” performs the same in-

151
152 CHAPTER 21

struction at each step, but with a di¬erent bit each time. This method
can be used to reduce the total number of steps needed to test each
key, resulting in a dramatic increase in speed. The end result is that
roughly 300 instructions are needed to compute DES, where previously
over 600 were used in other fast implementations.
This was the theory, at least. It would be up to implementors to
prove just how much faster the technique would be.


Monday, April 18, 11:52 p.m.
Carnegie Mellon University, Pittsburgh, Pennsylvania

Darrell Kindred, a Ph.D. candidate at Carnegie Mellon University, had
spent the weekend implementing Eli Biham™s bitslicing method, be-
cause he was sure that if our clients could use the method, we could
increase our key search. DESCHALL™s code for the Intel processors
was already the fastest of all known DES key search software thanks
to Rocke Verser™s tremendous optimizations for that platform. If Kin-
dred could make bitslicing work for DESCHALL™s clients on the more

<<

. 22
( 41 .)



>>