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."
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.
"Victory at Sea" (March 1999)
The story of the American war is incomplete without the sweep and strategic stakes of the war at sea, in which 104,985 American sailors and Marines were wounded, 56,683 were killed, and more than 500 U.S. naval vessels were sunk. Lest we forget. By David M. Kennedy
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.