Intelligence February 2002

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

Within 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.

At 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."

Presented by

Google Street View, Transformed Into a Tiny Planet

A 360-degree tour of our world, made entirely from Google's panoramas

Join the Discussion

After you comment, click Post. If you’re not already logged in you will be asked to log in or register.

blog comments powered by Disqus

Video

Google Street View, Transformed Into a Tiny Planet

A 360-degree tour of our world, made entirely from Google's panoramas

Video

The 86-Year-Old Farmer Who Won't Quit

A filmmaker returns to his hometown to profile the patriarch of a family farm

Video

Riding Unicycles in a Cave

"If you fall down and break your leg, there's no way out."

Video

Carrot: A Pitch-Perfect Satire of Tech

"It's not just a vegetable. It's what a vegetable should be."

Video

The Benefits of Living Alone on a Mountain

"You really have to love solitary time by yourself."

More in Technology

More back issues, Sept 1995 to present.

Just In