<<

. 14
( 41 .)



>>


I looked over our statistics to see just how much progress we were
making. Our statistical reporting was simple, but it got the job done.
Each day, we reported the number of keys that we tested that day and
the running total of keys tested. Recognizing the psychological di¬culty
of running a race without knowing how far away we were from the ¬nish
line, we had to ¬nd a way to represent the goal for our participants.
That need was satis¬ed by another statistic that some people found
curious”“Time to 50%.”
We didn™t want to make the goal seem too far out, and putting the
time needed to search the entire keyspace would be an unrealistically
long period of time. We had only one chance in over 72 quadrillion
of having to search the entire keyspace. On the other hand, we didn™t
want the goal to seem too unrealistically close. In the end, Rocke Verser
decided simply to use the mid-point as the goal we watched because on
average, any brute force attack would need to run through half of the
total keyspace. In any case, it was a useful metric, allowing participants
to think about how long it would take a project like DESCHALL to
crack not just one key, but DES keys in general, based on the key
testing rate that DESCHALL had achieved.
Looking over the statistics showed us several important milestones,
and how far we had managed to come in just under a month. Given
DESCHALL™s performance in mid-March, we were seventy-¬ve years
away from ¬nding the DES key we wanted. Organizing the project in
March gave us a boost, bringing our search time down to under ten
years. Within a few days of the mailing list being brought online, we
managed to cut that time in half. With more participants joining the
project in the past two days, we had managed to pass the point of
having searched roughly half of a percent of the total keyspace. The
day before, we managed to sustain a key search rate of 300 million keys
per second.
Looking over these statistics, I could see that about March 21, the
project started to increase its rate of progress dramatically. Seeing that
this is when we started to get some of the labs of systems sitting idle at
universities, I thought this con¬rmed our strategy of making the soft-
ware as easy to run as possible. In addition to making the key-cracking
client easy to start, having it operate quietly in the “background” would
The Race Is On 89

Daily Total Estimated
Date Keys Tested Keys Tested Time to 50%
03/14/97 1313404354560 14017854701568 75.0 years
03/15/97 2342485229568 16360339931136 42.0 years
03/16/97 2881570734080 19241910665216 34.0 years
03/17/97 2560471597056 21802382262272 39.0 years
03/18/97 2780831940608 24583214202880 35.0 years
03/19/97 2997157363712 27580371566592 33.0 years
03/20/97 3724239962112 31304611528704 26.0 years
03/21/97 6298259161088 37602870689792 16.0 years
03/22/97 9185290878976 46788161568768 11.0 years
03/23/97 9667770056704 56455931625472 10.0 years
03/24/97 8623505801216 65079437426688 11.0 years
03/25/97 7939918135296 73019355561984 12.0 years
03/26/97 9066726293504 82086081855488 11.0 years
03/27/97 10519398318080 92605480173568 9.0 years
03/28/97 10115017080832 102720497254400 10.0 years
03/29/97 14256128917504 116976626171904 7.0 years
03/30/97 14365398925312 131342025097216 7.0 years
03/31/97 12454079758336 143796104855552 8.0 years
04/01/97 12892275474432 156688380329984 8.0 years
04/02/97 15425928691712 172114309021696 6.0 years
04/03/97 14122640998400 186236950020096 7.0 years
04/04/97 17942393651200 204179343671296 5.5 years
04/05/97 22777738297344 226957081968640 4.3 years
04/06/97 21748321878016 248705403846656 4.3 years
04/07/97 21215989202944 269921393049600 4.6 years
04/08/97 23947613569824 293869006619424 4.1 years
04/09/97 25581437582560 319450444201984 3.9 years
04/10/97 28855494508544 348305938710528 3.4 years
Table 4. DESCHALL Statistics Through April 10



prevent many from not running DESCHALL because they believed it
somehow interfered with a computer™s normal day-to-day functions.
It has been said that it™s easier to get forgiveness than permission,
and while this may be true for a one-time event, our early experiences
indicated quite the opposite is true in an ongoing e¬ort such as ours.
Dealing with computing management worked better than letting man-
agers discover how much of their systems™ computing power was being
devoted to the project by stumbling across it. Likewise, getting cooper-
ation from the policy makers by explaining the project, its importance,
and, perhaps most important, showing how the software didn™t inter-
fere with normal work proved itself e¬ective. Not only were we getting
90 CHAPTER 12

permission for the speci¬c networks in question, but we were winning
advocates to the DESCHALL cause.
13
Clients




Those statistics showed us that we had come a long way since March.
The problem was that we were still far less than one percent through
the keyspace, and we could expect that we were years away from ¬nding
the key. We knew that we needed to make the DESCHALL project run
faster”to test more keys in a day. We already had enthusiastic par-
ticipants helping to get more systems running the DESCHALL client
software. We needed more speed, and that would have to come not only
from getting more systems working on the project but in getting that
client software to run faster. How can we get the software to run faster
when the DES algorithm itself speci¬es each step that must be taken
to take ciphertext and to turn it into the corresponding plaintext?
The ¬rst insight into the process of testing keys quickly is that you
don™t need to try them one at a time. One of the beauties of a procedure
with many steps is that by putting the steps in a particular order, you
can reduce the number of steps overall. To illustrate, suppose you are
packing your car for an overnight trip; you don™t take each article of
clothing out of a drawer all the way outside to your car, open the trunk,
place it inside, close the trunk, then back for the next item. Instead,
you determine what you need, place everything into bags”perhaps an
overnight bag and a garment bag”thus reducing the number of trips
from the house to the car from the number of items you™re taking to
two.
A further re¬nement could occur if you observe that the process of
opening and closing the trunk works the same way for each bag. You™d
notice that you are simply ¬lling a bag, taking it to the car, opening
the trunk, placing the bag inside, closing the trunk, and then going
back to pack another bag. Once you see this and recognize that the


91
92 CHAPTER 13

process of putting a bag in the trunk is exactly the same for each bag,
you could pack both bags, carry one in each hand to the car, open the
trunk, place both bags inside, and then close the trunk.
Just as anyone who has ever packed for a trip can order and reorder
events to reduce the amount of time and e¬ort needed, programmers
can increase their systems™ e¬ciency by studying a particular process
and ¬nding ways to eliminate redundant work, a strategy called opti-
mization.
This is precisely what Rocke Verser did with our DESCHALL
clients. By studying DES, he was able to ¬nd ways to perform DES
encryption and decryption very quickly. By studying DES decryption
in greater detail, he found ways to test for valid keys even more e¬-
ciently than using his fast decryption processes.


January 1997
Loveland, Colorado

While looking over the process of decrypting DES ciphertext, Rocke
Verser got an idea. There was no need to program the computer to
execute the decryption routine in its entirety with one key, then to
execute the entire decryption routine with the next key, and so on. By
looking at each step in the decryption process individually, Verser could
¬nd ways to save himself some e¬ort in searching lots of DES keys.
Verser watched the results of the ¬rst steps of a DES decryption
with each key with which he performed that calculation. He quickly
noticed that each DES key has another DES key that is mathematically
related to it”a complement”that behaves identically in the ¬rst few
steps of the DES decryption process. A complementary key is like a
photographic “negative.” Although the colors are backward, the ¬rst
few steps in identifying the subject of the photo (¬nding the outlines)
will be the same for both the photographic print and the negative.
Verser could take advantage of this property so that instead of per-
forming those initial steps for every single key to be tested, he could
perform those steps once”for both a key and its complement at the
same time. Since this worked only for the ¬rst few steps of the decryp-
tion process, it didn™t cut the number of decryptions in half, but it did
reduce the amount of work needed to test two keys.
After further study, Verser found that a key could be identi¬ed
as incorrect for the ciphertext to be decrypted well before the entire
Clients 93

decryption process would run its course. In the DESCHALL key-testing
client, Verser wrote four tests to ¬nd when a key was the wrong one so
he could make his DES key testing client run even more quickly. The
vast majority of incorrect keys would be identi¬ed by one of the ¬rst
two tests”only one out of 4096 keys passed both of these tests.
After running a few more steps through the decryption process, the
DESCHALL client would run a third test, after which only one key out
of about four billion would still be a possible match. Verser called a key
passing this test a “half-match” because half of the bits in the key were
correct, like having half of the numbers in a 56-number combination.
The DESCHALL client then performed another step in the decryp-
tion operation and then one more test. If the result of the test is what™s
expected, the key is a “full-match,” which almost certainly makes it the
correct key.
Between the early-stage reductions in processing and the late-stage
detection for non-matching keys, Verser™s method for testing DES keys
was dramatically more e¬cient than running each key straight through
the decryption process. DES decryption straight through takes sixteen
rounds”Verser™s method tested keys in under twelve. These perfor-
mance improvements allowed for many more keys to be tested each
second.
Verser knew that his key-testing program would need to run on
many di¬erent kinds of computers, from the engineering workstations
found at universities and in scienti¬c institutions to desktop PCs. Even
among the PCs there would be considerable variation, since Windows,
OS/2, Linux, FreeBSD, and other operating systems would need their
own versions of the software.
The C programming language was well-suited to the task. Originally
written in 1973 at AT&T Bell Laboratories by Brian Kernighan (pro-
nounced “Kern-ih-han”) and Dennis Ritchie for the purpose of building
the Unix operating system, the language had two important properties
that mattered to Verser: it was fast and it was portable, meaning that
its code would be able to require very little e¬ort to build on di¬erent
computer types. A computer type”de¬ned as a particular combination
of hardware and operating system”is known as a platform.
Verser built his software in C and created clients for some of the
most popular platforms of the day”including Windows 95 on Intel,
Solaris on SPARC, and IRIX on MIPS. He had another trick up his
sleeve, though, for platforms that used Intel microprocessors. Now, C
94 CHAPTER 13

code is fast, but not nearly as fast as Assembler. (See page 60 for
discussion.) With the kind of detailed control over the chip™s operation
o¬ered by Assembler, Verser was able to provide precise instructions to
the processor so it could have its calculations organized so they could
be performed very rapidly.
Especially with the Pentium and Pentium Pro processors, Verser™s
code was able to run at a phenomenal speed, allowing modest desktop
computers with Intel processors to run circles around $20,000 scienti¬c
workstations.


Friday, April 4, 9:12 P.M.
Health Networks Australia, Brisbane, Australia

System administrator Andrew Glazebrook posted a message to the
DESCHALL mailing list from Down Under”not itself particularly
strange, because there was no restriction on who could join the mailing
list. Without drawing attention to where he was from, Glazebrook™s
message showed that, despite our limited-access client distribution
system meant to comply with cryptographic export policy, the DES-
CHALL client had found its way to Australia.
Glazebrook was running the DESCHALL client on three of his ma-
chines, a 90 MHz Intel Pentium running OS/2, a 66 MHz Intel 80486-
DX2 running Linux, and another Linux system, with a 133 MHz “Pen-
tium compatible” processor. Virtually all software”including operat-
ing systems, o¬ce suites, and Web browsers”was written in a high-
level language (like C++) and then turned into machine code by a
compiler for execution on the computer. Because the “compatible” pro-
cessors had the same instruction sets as the genuine Intel processor,
they could execute the same machine code.
Even though the processors from Intel and the compatible proces-
sors made by other manufacturers (like Cyrix and AMD) had the same
instructions, they had very di¬erent internal structure”each manu-
facturer™s chip was wired di¬erently to avoid infringing on Intel™s in-
tellectual property. Usually, the di¬erence in internal structure made
no di¬erence to the user”software produced by a compiler would run
about the same speed on a processor from Intel or another manufac-
turer.
Rocke Verser™s key-testing software for Intel processors was not pro-
duced by a compiler, however. Because of all of the optimization that
Clients 95

the DESCHALL client had for various Intel processors, the di¬erences
in processor internals made a huge di¬erence. Much to Glazebrook™s dis-
may, his 133 MHz Intel-compatible system ran the DESCHALL client
much slower than his 90 MHz Intel system”at a speed more compara-
ble to his 66 MHz Intel system.
Glazebrook™s message to the DESCHALL mailing list was to see if
other participants were having similar experiences with Intel compati-
ble processors. They were, and calls for clients built for Intel-compatible
processors started to ¬‚ow in.


April 9, 5:14 P.M.
Loveland, Colorado

Rocke Verser made an announce-
ment on the DESCHALL mail-
ing list: Justin Dolske and Guy
Albertelli, another graduate stu-
dent at Ohio State, were granted

<<

. 14
( 41 .)



>>