<<

. 2
( 41 .)



>>


ix
Acknowledgments


This book is the product of tremendous work by many people. Thanks
must go to Peter Trei for suggesting the demonstration of a brute force
attack on the Data Encryption Standard and to RSA for sponsoring the
contest that at long last demonstrated the weakness of DES. I also offer
my heartfelt thanks to Rocke Verser for his work in starting and running
the DESCHALL project that participated in RSA™s contest. Justin Dolske,
Karl Runge, and the rest of the DESCHALL developers also put in many
hours to ensure our project™s success and were as pleasant and interest-
ing as one could hope for. Not to be forgotten are the thousands of peo-
ple who participated by running the DESCHALL client programs on their
computers, telling their friends about our project, and giving us access to
the tremendous computational power needed to verify that strong cryp-
tography makes the world a safer place. Telling the story of this signifi-
cant period in the history of cryptography in the form of the book that you
are now holding proved to become another sizable project. Gary Cornell
at Apress got me connected with the right people at Copernicus Books. I
appreciate the connection as well as the help that Anna Painter, Paul
Farrell, and the rest of the folks at Copernicus Books provided in moving
the book from a raw manuscript into its final, published form. Thanks are
also due to John Gilmore for resurrecting a recording of Martin Hellman
and Whitfield Diffie arguing with government representatives the need
for a stronger standard than what became codified in DES. The recording
and other electronic resources of interest are available at:

http://ergo-sum.us/brute-force/.

Finally I thank my wife Nicole for her continued support and thought-
ful interest in my work.

Matt Curtin
December 2004




x
To the Cypherpunks”
making the networks safe for privacy¦
1
Working Late




June 17, 1997, 11:51 P.M.
Salt Lake City, Utah

A modest desktop computer quietly hummed along. It sat in the of-
¬ces of iNetZ Corporation, a Web services company started just a
few months earlier. This machine, just an ordinary machine with a
90 MHz Intel Pentium processor, was still hard at work in the darkness
of an o¬ce that had closed for the day several hours earlier. Running a
program called DESCHALL”pronounced “DESS-chall” by some, and
“dess-SHALL” by others”this computer was trying to read a secret
message. After all, it was practically the middle of the night, and the
machine had nothing else to do.
The secret message was protected by the U.S. government standard
for data encryption, DES. Largely as a result of the government™s ¬at,
DES was used to protect sensitive data stored on computers in banking,
insurance, health care, and essentially every other industry in nearly
every part of the world. It was a U.S. standard, but in a world of
international corporations and global trade increasingly conducted by
computer, it was in everyone™s interest, or so it seemed, to standardize
on DES.
The slowest of eight iNetZ machines on which system administra-
tor Michael K. Sanders installed DESCHALL, the quiet little com-
puter was trying to ¬nd the single key out of more than 72 quadrillion
(72,000,000,000,000,000) that would unlock the secret message. Apply-
ing one key after another to the message and checking the output for
something intelligible, the machine was trying some 250,000 keys per

1
2 CHAPTER 1

second. It did not falter. It did not quit. It just kept banging away at
the problem.
Quite suddenly, just before midnight, the computer™s DESCHALL
program came to a halt.
When Sanders came to work at iNetZ the following morning, this
unassuming computer was displaying an urgent message on its screen.
Information security would never be the same.
2
Keeping Secrets




Cryptography is quite simply the practice of secret writing. The word
itself comes from two Greek words, kryptos (“hidden”) and graphein
(“writing”). With a history going back at least 4000 years, cryptogra-
phy has long been surrounded by mystery and intrigue.
Ancient Egyptians used cryptography in hieroglyphic writing on
some monuments, thus protecting some proper names and titles. Some
2000 years ago, Julius Caesar used a simple system of substituting one
letter for another to send secret messages to his generals. In the thir-
teenth century, English mathematician Roger Bacon wrote of systems
to write in secret in his “Concerning the Marvelous Power of Art and of
Nature and Concerning the Nullity of Magic.” In that document, Bacon
enumerated seven methods for secret writing and famously opined, “A
man who writes a secret is crazy unless he conceals it from the crowd
and leaves it so that it can be understood only by e¬ort of the studious
and wise.”
Throughout its history, cryptography has primarily been a tool of
government elites because they were the ultimate keepers of military
and diplomatic secrets. Code makers and breakers alike have thus al-
most always been employed by governments to discover others™ secrets
while protecting their own.
Cryptography is important because it enables information to be
stored and transmitted secretly. The ability to control the ¬‚ow of in-
formation, to enforce who may and may not know a particular fact
is precisely the kind of power that traditionally governments and in-
creasingly private businesses seek to wield against adversaries and com-
petitors. Especially when the keepers of a secret are not able to meet
together, out of the range of eavesdroppers and spies, there is a need for


3
4 CHAPTER 2

communicating secretly right in the open. As had been demonstrated
in numerous wars of the twentieth century, anyone can intercept ra-
dio signals. Telephone lines can be tapped. This is where cryptography
comes into play”locking up information so that it will remain secret
while it is being transmitted via a medium that is open to all.
Once we had passed the age of the trusted courier and locked box,
new telegraph and especially radio technologies created the need for re-
liable encryption machines. In the early twentieth century, enterprising
inventors saw an opportunity and before 1920 had invested four such
devices. At the heart of these machines was a series of three or four
rotors”wired code wheels, each with twenty-six di¬erent electrical con-
tacts on each side. To encrypt a message, the user would type a letter
on the keyboard, such as A, and electrical current would ¬‚ow through
the machine, going through the rotors, and printing a completely dif-
ferent letter, such as V. The rightmost code wheel would then advance
one position, and the user pressing A again would result in another
letter being printed, such as T, before the code wheel rotated again.
Once the rotor went through all twenty-six positions, the rotor next to
it would also advance, much like an analog odometer on an automobile.
In this way, the user would type the original message, while the
machine would produce ciphertext that could safely be sent as a radio
signal. The intended recipient of the message would have a matching
cipher machine that would turn the signal back into human-readable
plaintext. In the United States, Edward H. Hebern invented his machine
in 1917, Germany™s Arthur Scherbius invented his in 1918, and 1919
saw the invention of a machine in the Netherlands by Alexander Koch
and in Sweden by Arvid Gerhard Damm. Scherbius called his machine
Enigma, and it would become the only ¬nancially successful cipher
machine from the era.
Enigma was patented by Scherbius, an electrical engineer, and E.
Richard Ritter, a certi¬ed engineer. After the eventual transfer of
patent rights, Engima would come to be marketed commercially by
Chi¬riermaschinen Aktien-Gesellschaft (Cipher Machines Stock Cor-
poration), whose board of directors included Scherbius and Ritter. Sev-
eral governments began to investigate Engima, with variations of the
original design eventually coming into use throughout the German,
Italian, and Japanese armed forces.
Despite the best e¬orts of its producers, Engima was not generally
accepted in the world of business. Its commercial success came as a
Keeping Secrets 5

result of the Axis use of the machine to protect military and diplomatic
communications.1
With the rise of radio technology in government and military com-
munications in the early twentieth century, the danger of messages be-
ing intercepted increased dramatically. Instead of having to get physical
access to communications circuits such as telephone or telegraph lines,
operatives could simply point high-powered antennas toward their tar-
gets and start listening. Governments throughout the world developed
“signals intelligence” groups, chartered to intercept radio communica-
tions sent by other nations, and to report their ¬ndings to their own
leaders. To protect their own communications from foreign signals in-
telligence e¬orts, governments began to encrypt their radio signals.
Governments would not easily give up the ability to read others™
messages. Signal intelligence came to mean not just message intercep-
tion but also breaking the encryption used to protect the messages. In
the years leading up to World War II, the United States maintained
an active signal intelligence operation even while hoping to avoid being
drawn into the global con¬‚ict. In 1938, the Japanese empire began to
use a machine they called “Alphabetical Typewriter 97” for their diplo-
matic messages”a rotor machine like Germany™s Enigma. Unable to
read those messages, the U.S. Army Signals Intelligence Service (SIS)
began a project to break the Japanese system, which they had code-
named, “Purple.”
In the late 1930s, SIS cryptanalysts (code breakers) under the di-
rection of cryptographic pioneer Frank Rowlett spent eighteen months
studying intercepted Japanese diplomatic messages, looking for any
clue that would help them to unlock Purple™s secrets. One day in
September 1940, SIS cryptanalyst Genevieve Grotjan made a critical
discovery. She found important and previously undiscovered correla-
tions among di¬erent messages encrypted with Purple. After Grotjan
brought her discovery to the attention of the rest of the SIS Purple
team, they were able to build a duplicate of a machine they had never
seen”the Alphabetic Typewriter 97.2
Putting its new machine to work right away, SIS discovered that
Purple was used not simply for routine tra¬c, but the most sensitive
of the Japanese empire™s secrets. Intelligence gathered from intercepted
and decrypted Purple messages was so valuable that those decrypted
intercepts came to be called “Magic” within SIS.
6 CHAPTER 2

When Rowlett returned to his o¬ce from a meeting at midday on
December 3, 1941, he picked up a Magic decrypt from his in-box. That
message, intercepted just that morning, was directed to Japan™s em-
bassy in Washington. Rowlett read the bizarre orders for Japanese
diplomats to destroy their code books and even one of the two Pur-
ple machines they had. Without their code books and with only one
working Purple machine, the Japanese embassy simply would not be
able to operate normally. Colonel Otis Stadtler, who was responsible
for distributing Magic decrypts arrived as Rowlett was reading the mes-
sage. After some discussion, Stadtler realized the meaning of the order:
Japan was preparing to go to war with the United States.
On the evening of December 6, U.S. president Franklin D. Roosevelt
received analysis of the intelligence: war with Japan was inevitable,
and the Magic decrypts were used to support the conclusion. As the
Japanese military used di¬erent codes from the Japanese diplomats,
President Roosevelt had no way of knowing that on the very next day,
Japan would attack Pearl Harbor and kill over 2300 Americans. Only
¬ve years later would there be enough time for SIS cryptanalysts to
look at the military intercepts in the months before the strike on Pearl
Harbor. Their e¬orts to break those messages proved successful, and
they anguished over the results of their work. Though not naming Pearl
Harbor explicitly, the Japanese military had been ordered to be on a
footing for war with the United States by November 20, 1941.3




Private industry, driving much of the revolution in communication tech-
nology of the twentieth century, also developed its interest and expertise
in cryptography. Claude E. Shannon at AT&T Bell Telephone Labo-
ratories made several critical contributions to modern communication,
computing, and cryptography. Shannon joined Bell Labs in 1941, after
completing his Ph.D. in mathematics at the Massachusetts Institute of
Technology. At Bell Labs, Shannon worked as a research mathemati-
cian and came to be known for “keeping to himself by day and riding
his unicycle down the halls at night.”4
In 1948, Shannon published “A Mathematical Theory of Commu-
nication” in the Bell System Technical Journal.5 The paper was a
breakthrough, founding the study of information theory, and coining
Keeping Secrets 7

the term “bit” to describe a BInary uniT. Up
to that time, communication was thought to
require electromagnetic waves down a wire or
radio waves toward a receiver, but Shannon
showed how words, pictures, and sounds could
be sent across any medium that would carry
a stream of bits. The following year, Shannon
applied his work directly to cryptography in
a paper entitled, “Communication Theory of
Secrecy Systems.”6 This paper founded mod-
Fig. 1. Claude E. Shan- ern mathematically-based cryptography out-
non, c. 1952. Property of
side of government intelligence agencies.
AT&T Archives. Reprinted
The rise of the computer and the rise of
with permission of AT&T.
cryptography have gone hand in hand. Com-
puting technology has made exchanging infor-
mation easier, making communication and collaboration easier. Since
people still want”and in an ever-growing number of cases, are legally
obligated”to stay in control of information in their stewardship, people
need cryptography.
Code makers and code breakers agree: the computer is both friend
and enemy. For cryptographers, computer technology makes the im-

<<

. 2
( 41 .)



>>