<<

. 10
( 41 .)



>>

Testing cryptographic keys can be easily parallelized, just like a large
number of trivial arithmetic problems. To show how supercomputers
and desktop computers compare in this contest, let™s assume that a
supercomputer can test a cryptographic key in one second and that a
regular desktop computer can test a cryptographic key in ten seconds.
One supercomputer (at, say, $30 million) will be ten times the speed of
a single desktop computer (at, say, $3000). That same supercomputer
would be the same speed as ten desktop computers ($30,000). The same
supercomputer would be one tenth the speed of 100 desktop computers
($300,000).
Almost since the beginning of digital computing, our machines have
become smaller, less expensive, and faster. Where a single, monolithic
Supercomputer 59

machine used to serve a user community, subsequent generations of
computers have become more e¬cient and more numerous. By 1997,
personally-owned computers were commonplace in homes and dorms,
and those machines were many times faster than the kinds of minicom-
puters and even mainframes that were used a decade or more earlier.
At the same time, progress in telecommunications allowed comput-
ers to communicate with each other as they had not been able years
earlier. The rise of the Internet enabled this trend to the point where
every computer in the world had the ability to communicate with nearly
every other computer in the world.
Part of what made the Internet special was that it was not a network
of computers, but of networks. Having Alice put her machine on a
network would allow it to communicate with others on that network.
Bob putting his machine on a network allowed his computer to talk to
others on that network. The Internet made it possible for Alice™s and
Bob™s networks to connect to each other.
Though many academic and business environments had dedicated
connections to the Internet, individual users would typically use modems
to call an Internet Service Provider (ISP). The connection was only
temporary, though, and would only stay active as long as the user
needed to be able to exchange email, to surf the web, or to read arti-
cles.
Very large numbers of computers were out there, able to commu-
nicate with other machines on the Internet. The question was how to
get them to cooperate with one another and apply their energies to a
singular problem like ¬nding the particular DES key needed to read
the encrypted message, thereby solving the RSA challenge.
RSA didn™t put limitations on how anyone could solve its challenges.
With 40-bit and 48-bit RC5 challenges already solved, the world™s cryp-
tographers were thinking seriously about how to increase the e¬ciency
of a large-scale key search computation.
Increasing the number of computers looking for the key is one way
to increase the e¬ciency of the search, but two other important options
are available to the cryptanalyst who wants to use a brute-force attack.
The ¬rst is to increase the e¬ciency of the software itself, and the
other is to wire the instructions needed to ¬nd DES keys directly into
a computer™s hardware.
Consider the ¬rst option”e¬ciency in software itself. This alone
can have a dramatic improvement in performance. When people write
60 CHAPTER 8

programs for computers, they typically use languages that were created
for the speci¬c purpose of communicating an algorithm or program
speci¬cation to a computer. Computers don™t run the programs that
are created by the human programmers. Instead, programmers will
write software in a computer language like Java, Lisp, or C++. The
version of it that programmers work with is called source code. When
the software is ¬nished, the programmer will invoke a program called
a compiler to read the source code and turn it into a form that the
machine can read and run directly, known as the binary executable or
object code.
In essence, the compiler will translate what the programmer says
into something that the computer can do. Building software this way is
economical and frankly much more practical than having people write
object code directly. By making the process of creating the software
easier, we reduce the amount of “people time” needed to create a fully
operational system and to get it running. Since general-purpose com-
puters like your typical PC, Macintosh, or Unix system are so fast and
cheap and people are so expensive, we ultimately save huge amounts
of money having computers do things for us.
If a program was generated by a compiler, its speed is nowhere near
what it would be if the programmer with the skill took the extra time
to write the program in a language that the computer can understand.
A computer language known as Assembler makes it possible for a
programmer that knows the machine very well to be able to create ex-
tremely e¬cient code which is tailored to a given machine and contains
very speci¬c instructions.
An intimate understanding of the computer will allow the program-
mer to write code that performs the job in very few instructions, taking
advantage of any little feature that a particular computer has available.
Languages (like Lisp and Java, mentioned earlier) are typically
called “high level” when they allow the programmer to work on a
solution without thinking much about how the computer is actually
going to get the job done. “Low level” languages (like Assembler) re-
quire the programmer to specify exactly how the machine will store
and manipulate the data in order to solve a problem. The di¬erence
between high-level and low-level languages is roughly the same as say-
ing “walk down the street with a little spring in your step” and saying
precisely how much to move each muscle in the body in order to move
down the street. Writing programs in Assembler is comparatively hard
Supercomputer 61

work. Relatively few programmers can write in Assembler, because it
requires much more intimate knowledge of computer hardware”a level
of knowledge that many programmers simply lack.
A program written so “close to the metal” can be extremely fast on
the system it was designed for. Any variation in that system, though,
can slow it down dramatically. Even an upgrade in processor type (from
one Pentium model to another, for example) will alter the processor™s
internal structure, making a program that ran very quickly in the old
system perform very badly in a newer and faster system.
Peter Trei was able to implement his DESKR program in relatively
little time because he didn™t take the time to make the software search
for keys as fast as the machine could possibly do it. Instead, he chose the
language that most cryptography software is written in, known as C, a
sort of mid-level language that doesn™t let the programmer completely
forget about the hardware, but doesn™t require him to specify exactly
what to do with every single bit in the entire system. That ¬‚exibility
also allowed Steve Gibbons to make relatively minor changes to the
software so that it would work on his computers and for me to make
other minor changes so it would work on my computers. If Trei had
built his software in Assembler, we would have had to write some parts
of the DESKR software almost from scratch to work on other computer
systems.
The only question remaining was whether key-searching software
written in C was fast enough to get the job done. If not, the new key-
cracking system would have to be written in Assembler, or possibly
something even faster.
Building a physical system to perform a brute-force attack in hard-
ware would increase its e¬ciency further, making it even faster than
Assembler. However, the issues that need to be addressed when imple-
menting a program in Assembler are still present when implementing
that same program directly in hardware. Even worse, hardware imple-
mentations require building or physically wiring special-purpose equip-
ment, which is much more expensive than reprogramming software.
Whether to crack keys with regular software written in a high-level
language, specialized software written in a low-level language, or with
custom-built hardware comes down to how fast the system needs to
¬nd keys and how much time and money can be thrown at building
the system.
62 CHAPTER 8

Litt said a supercomputer would take over a year to crack a DES
key. If it took too long to solve RSA™s DES Challenge, the government
would have proved its point about the di¬culty of breaking encrypted
messages by brute force and we would have no choice but to shut up.
The public policy debate over the freedom to use strong cryptography
in the United States could be heavily in¬‚uenced by how cryptographers
would respond to the DES Challenge. We had a lot of decisions to make,
and we had to choose well.
9
Organizing DESCHALL




February 1997
Megasoft Online, Columbus, Ohio

Mindful of the computing power we would need to ¬nd DES keys,
it was important to take advantage of the momentum that had been
built up by the publicity of the 40-bit and 48-bit RSA contests. It
made perfect sense for the same group of people who ran Germano
Caronni™s 48-bit key-cracking software and communicated on mailing
lists to form a new group that would try to solve RSA™s DES Challenge.
These hobbyists, students, amateurs, and professionals from all over
the world (though heavily European) were already “assembled” on the
mailing list, already interested in the topic, and already prepared to
take on RSA™s next challenge.
Just like Caronni™s 48-bit contest e¬ort, there would be no formal
organization, no headquarters, and no employees. People who saw work
that needed to be done would simply do it. After the software was
built, volunteers would run the key-searching programs on their own
computers and communicate via e-mail”participating from wherever
they happened to be, putting in as much time as they wanted. Because
a number of participants were from European countries that lacked
U.S.-style rules against the export of cryptographic software, many
of us thought that the group would produce software that everyone
could run. Even in countries where the export of cryptographic software
was forbidden, there were usually no prohibitions on the import of
cryptographic software from other countries. So if the software were
built in Switzerland, for example, volunteers from the U.S. could run

63
64 CHAPTER 9

the software. If U.S. programmers wrote the software, sending it to
European volunteers would probably be an illegal export of regulated
technology.
Many of us who ran Caronni™s clients wanted to move immediately
to breaking DES keys. Although I had previously worked on Peter Trei™s
DESKR system, I wanted to help with a coordinated e¬ort”one that
would harness the computing power of many machines in an organized
way to search for the right key.
Some participants in Caronni™s e¬ort volunteered to perform certain
vital functions for the DES Challenge early. Six volunteers agreed to
work together to direct the e¬ort and to coordinate the activity of those
who were interested in answering the DES Challenge. Germano Caronni
agreed to be part of this group, as did Piete Brooks of Cambridge
University, Jered Floyd of MIT, Tim Newsome of CMU and a student
programmer at Megasoft Online, Thomas Roessler from Germany, and
“Thomas S.” from the University of Manchester Institute of Science
and Technology.
As the “DES-Challenge Organisation Committee” announced itself
and the work that was to be done, it unveiled a half-dozen mailing lists
to foster communication among participants, each dedicated to some
speci¬c part of the project. On those new lists, cryptographers and
enthusiasts from all over the world discussed what would be needed to
defeat DES. The group quickly agreed that we would need a system
that could support many, many more clients than we ever had working
on RSA™s 48-bit Challenge”which peaked at roughly 4500 at once (and
roughly 7500 total working for any length of time) for a peak key testing
rate of 440 million keys per second.16
After much discussion, a general project architecture emerged. In-
stead of depending on a single server”a single place where a failure
could bring the whole e¬ort to a halt”there would be hierarchies of
servers, each dedicated to a speci¬c purpose. Another server would han-
dle just the highest-level coordination sitting on the network at the root
of the server hierarchies. While someone”we didn™t determine who”
would be responsible for the root server, others would be able to run
servers from wherever they were.
There would be separate servers to hand out key ranges to clients,
while others would receive the status reports from clients. Additional
servers would collect the statistical information from clients (e.g. what
kinds of operating systems were being used, how fast di¬erent sys-
Organizing DESCHALL 65

tems were running the key testing software, and how many keys had
been tested). Still other servers would subdivide key ranges into smaller
ranges for use by very slow clients. Finally, there would be servers that
would convert messages between the key testing client software and the
keyserver into a form that would traverse ¬rewalls”devices designed
to prevent unauthorized intrusion into networks; some options we dis-
cussed included sending the messages through e-mail and the Web.
Still, when it seemed that everything was set and the European
DES-Challenge group e¬ort was well on its way, tra¬c on the lists
dried up. Before long, it became clear that the actual software needed
to crack DES keys was not being written.
While the DES-Challenge team was busy debating technical details
other DES key search projects, such as the DES Violation Group (based
in the U.S.) and SolNET (based in Sweden), had gotten underway.
As the DES-Challenge team endlessly debated the details of its com-
plex scheme for allocating key space for the search, I received private
e-mail from Justin Dolske, a graduate student in the Computer and
Information Science Department at the Ohio State University. Though
Dolske and I lived less than ¬fteen minutes away from each other, it
was not until we both participated in Caronni™s Internet-based project
in Switzerland that we got to know each other. Dolske told me about
a project being led by a programmer named Rocke Verser. Verser™s
project had no name, no Web site, no mailing lists, and no support
sta¬. It only had key-cracking software. Fast software.
Looking at how the DES-Challenge team operated, it was now clear
that software didn™t spring from a project with a name and a mail-
ing list. A fully-functioning project, however, could well spring from
working software.


January 1997
Loveland, Colorado

Like many freelance programmers, Rocke
Verser had spent years honing his software
skills, taking on a variety of challenges sure
to make him better able to practice his
craft. Long attracted to mathematics and
the computational machines that allowed
Fig. 3. Rocke Verser, 1997
66 CHAPTER 9

complex calculations to be made so quickly, Verser was naturally drawn
to cryptography. Finding work in the development of cryptographic
software meant that Verser understood DES and knew ways to make
it work well.
Intimately familiar with Intel™s processors, Verser had written pro-
grams to encrypt and to decrypt data using the DES algorithm in the
kind of hand-crafted Assembler that very few people can understand,

<<

. 10
( 41 .)



>>