Losing the Code War

Wed Jan 30 10:26:09 EST 2002

http://www.theatlantic.com/issues/2002/02/budiansky.htm

The Atlantic Monthly | February 2002

Notes & Dispatches
Intelligence

Losing the Code War

The great age of code breaking is over-and with it much of our ability to
track the communications of our enemies

by Stephen Budiansky

.....

ithin days of the September 11 attacks U.S. intelligence agencies were
being blamed in many quarters for their failure to detect the terrorists'
plans in advance. Mistakes in the formulation and execution of intelligence
policy were no doubt made. Yet there is no one to blame for what is
probably by far the greatest setback in recent years to American
capabilities for keeping tabs on terrorists: the fact that it is now
virtually impossible to break the encrypted communication systems that PCs
and the Internet have made available to everyone-including, apparently, al
Qaeda. The real culprits behind this intelligence failing are the advance
of technology and the laws of mathematics.

For more than a decade the National Security Agency has been keenly aware
that the battle of wits between code users and code breakers was tipping
ineluctably in favor of the code users. Their victory has been clinched by
the powerful encryption software now incorporated in most commercial e-mail
and Web-browser programs.

It has always been theoretically possible to produce a completely
unbreakable code, but only at considerable inconvenience. In the 1920s two
groups of code users, Soviet spies and German diplomats, became aware of
the vulnerability of their existing systems and began to rely on what are
known as one-time pads. In this system sender and receiver are supplied
with matching pages containing strings of numbers; each page is used as a
key for encoding and decoding a single message and then discarded. If
properly used, this scheme is unbreakable. Yet in practice corners were
invariably cut, because the system was logistically complicated,
involving-among other things- teams of couriers to deliver new one-time
pads as the old ones were used up.

Until the end of the twentieth century any more practical coding system
that could be devised was susceptible to a basic flaw that a skilled code
breaker could exploit. Language is extremely patterned-certain letters and
words occur far more often than others. The essential task of a code key is
to disguise that nonrandomness. The key might, for example, consist of a
long string of random numbers specifying where in the alphabet each letter
of the message text should be shifted. If the first letter of the message
were A and the first key number 3, then that A would become D in the coded
version of the text; if the fourth letter were A and the fourth key number
5, then that A would become F; and so on. Many schemes were developed to
provide users with very long key strings, in an attempt to approach the
security offered by the one-time pad. Some systems used code books
containing tens of thousands of key numbers; others, such as the famous
German Enigma machine of World War II, used rotating wheels containing
wires and electrical contacts to generate a sequence of permutations.

Yet eventually some of the strings of key would have to be used in more
than one message, and when they were, the underlying patterns of language
would begin to glow dimly through. The history of twentieth-century code
breaking is at its heart the development of a series of increasingly
sophisticated mathematical methods to detect nonrandomness. The best code
breakers were usually able to keep pace with the latest advances in code
making, because of the practical limitations of producing very long strings
of truly random, nonrepeating key. The Enigma machine could be reset each
day to one of a million million million million different key-string
permutations, yet because of the machine's reliance on mechanically
rotating wheels, those different combinations were not completely random or
independent; subtle mathematical relationships connected one combination to
another, and Allied code breakers were able to develop a brilliant
mathematical technique that required them to test only a few thousand
different combinations to break each day's setting. In effect, they
discovered a shortcut, much like a safecracker's using a stethoscope to
listen to the tumblers fall rather than attempting the "brute force"
approach of trying every single combination.

But the postwar advent of general-purpose computers-stimulated by funding
from the NSA-began a process that by the end of the century gave code
makers an unassailable lead.

t first, when the extremely high price of computers ensured that government
agencies would always have a commanding technological lead over the public,
computers enabled the code breakers to abandon much subtlety in favor of
brute force: the computers could simply run through every possible key
setting to find the one that worked. But this was ultimately a losing
proposition, because in terms of computing power it is always cheaper and
easier to generate longer and longer keys than it is to test longer and
longer keys. Once computers became widely available, the game was over.

In 1998 a team of private-sector computer experts built a special-purpose
computer that could test 92 billion different key sequences per second in
the widely used Data Encryption Standard system, a mainstay of encoding for
commercial electronic traffic, such as bank transfers. It took them
fifty-six hours to break a message that was encoded in a version of DES
that chooses from some 72 quadrillion possible keys for enciphering each
message. (The number of possible keys available in a computer-generated
code is typically measured in terms of the length of the binary numeral
required to specify which key sequence to use; fifty-six bits give about 72
quadrillion combinations, so this version is called 56-bit DES.) That feat
was hailed as a great technological triumph, and it undoubtedly was one. It
was also clearly intended to make a statement-namely, that DES, which the
U.S. government had promulgated, was deliberately designed to keep ordinary
code users from employing anything too hard for the NSA to break. But there
was an utterly trivial fix that DES users could employ if they were worried
about security: they could simply encrypt each message twice, turning
56-bit DES into 112-bit DES, and squaring the number of key sequences that
a code breaker would have to try. Messages could even be encrypted thrice;
and, indeed, many financial institutions at the time were already using
"Triple DES."

Issued in 1977, DES was originally implemented in a computer chip, which
made it possible at least in principle to control the spread of encryption
technology through export restrictions. Huge increases in the processing
power of PCs, however, subsequently made it easy to realize much more
complex encryption schemes purely in software, and the Internet made it
practically impossible to prevent the rapid spread of such software to
anyone who wanted it. Today most Web browsers use 128-bit encryption as the
basic standard; a brute-force attack would take the world's fastest
supercomputer something like a trillion years at present. If someone
develops a supercomputer that is twice as fast, a code user need only start
using 129-bit encryption to maintain the same relative advantage.

The standard e-mail encryption software, supplied with most computers, is
the PGP ("pretty good privacy") system. In its latest version it is
actually considerably better than pretty good. Users can select 2048-bit
(equivalent to a little less than 128-bit DES) or even 4096-bit (equivalent
to significantly more than 128-bit DES) keys.

Osama bin Laden's network is suspected of employing additional methods to
veil its communications. Some reports suggest that al Qaeda not only used
encrypted e-mail but also hid encrypted message texts within picture files
or other data that could be downloaded from a Web site.

The implications of this fundamental shift in the balance of cryptologic
power between the spies and the spied-upon are profound. Before World War
II most Western governments and their military officials looked on
intelligence with considerable contempt if they paid attention to it at
all. Information from paid spies has always been notoriously
unreliable-colored by ineptness, by a mercenary calculation of what the
customer wants to hear, and sometimes by outright deceit. The explosion of
intelligence from decoded enemy signals that took place during World War
II, however, revolutionized both the profession of intelligence gathering
and its impact. Signals intelligence was information coming unfiltered from
the mouth of the enemy; its objectivity and authenticity were unparalleled.
The proof was in the payoff. The victory at Midway, the sinking of scores
of Japanese and German submarines, the rout of Rommel across North Africa,
the success of D-Day-all depended directly and crucially on intelligence
from decoded Axis communications.

Signals intelligence is not completely dead, of course: bad guys make
mistakes; they sometimes still use the phone or radio when they need to
communicate in a hurry; and a surprising amount of useful intelligence can
be gleaned from analyzing communication patterns even if the content of the
communications is unreadable. Still, if encrypted-signals intelligence is
to continue to provide information about enemy plans and organization, it
must be accompanied by a significant increase in direct undercover
operations. A hint of things to come emerged this past summer in the
federal criminal trial of Nicodemo Scarfo Jr., who faces charges of running
gambling and loan-sharking operations for the Gambino crime family. Federal
agents, discovering that Scarfo kept records of his business in encrypted
files on his PC, obtained a court order to surreptitiously install on his
computer what was identified in court papers as a "key-logger system." The
system (whether hardware or software is unclear) apparently recorded every
keystroke typed into the computer, eventually enabling FBI agents to
recover the password Scarfo used with his encryption software. Planting
such electronic bugs directly in computers, or perhaps even sabotaging
encryption software with a "back door" that code breakers could exploit,
would generally require direct access to the machines. A plan proposed by
the Clinton Administration would have obviated the need for direct access.
But the plan, which would have required all American makers of encryption
software to install a back door accessible by U.S. intelligence agencies
acting with court approval, was abandoned, in part because of the argument
that the requirement would not apply to foreign software makers, who are
now perfectly capable of equaling the most sophisticated American-made
commercial encryption software.

An effort in the Senate to revive that plan and include it in the
anti-terrorism bill that was signed into law October 26 received little
support and was withdrawn, and on much the same grounds-that however
powerful an intelligence tool code breaking was during its golden age, in
World War II and the Cold War, the technical reality is that those days are
gone. Code breaking simply cannot work the magic it once did.

Links referenced within this article

National Security Agency
http://www.nsa.gov/
German Enigma machine
http://home.us.net/~encore/Enigma/enigma.html
Data Encryption Standard
http://www.itl.nist.gov/fipspubs/fip46-2.htm
PGP
http://web.mit.edu/network/pgp.html
trial of Nicodemo Scarfo Jr.,
http://www.newsfactor.com/perl/story/12382.html

Find this article at:
http://www.theatlantic.com/issues/2002/02/budiansky.htm

 SAVE THIS | EMAIL THIS | Close 
 Uncheck the box to remove the list of links referenced in the article.

-- 
-----------------
R. A. Hettinga <mailto: rah at ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com