Crypto: How the Code Rebels Beat the Government--Saving Privacy in the Digital Age

Excerpt from

Chapter One

A substitution cipher is one where someone creates ciphertext (the scrambled message) by switching the letters of the original message, or plaintext, with other letters according to a prearranged plan. The most basic of these has come to be known as the Caesar cipher, supposedly used by Julius Caesar himself. This system simply moved every character in the plaintext to the letter that occurs three notches later in the alphabet. (For instance, a Caesar cipher with its "key" of three would change A to D, B to E, and so on.) Slightly more challenging to an armchair cryptanalyst is a cryptosystem that matches every letter in the alphabet to one in a second, randomly rearranged alphabet. Newspaper pages often feature a daily "cryptogram" that encodes an aphorism or pithy quote in such a manner. These are by and large easy to crack because of the identifiable frequency of certain letters and the all-too-often predictable way they are distributed in words.

Like countless other curious young boys before him, Whit Diffie was thrilled by the process. In his history of cryptography, The Codebreakers, author David Kahn probes the emotional lures of secret writing, citing Freud's theory that the child's impulse to learn is tied to the desire to view the forbidden. "If you're a guy, you're trying to look up women's skirts," says Kahn. "When you get down to it basically, that's what it is, an urge to learn." For many, the fascination of crypto also deals with the thrill that comes from cracking encoded messages. Every intercepted ciphertext is, in effect, an invitation to assume the role of eavesdropper, intruder, voyeur. In any case, it wasn't the prospect of breaking codes that excited Whit Diffie but the more subtle pursuit of creating codes to protect information. "I never became a very good puzzle solver, and I never worked on solving codes very much then or later," he now says. He would always prefer keeping secrets to violating the secrets of others.

Diffie's response to Miss Collins's cryptography lesson was characteristic. He ignored her homework assignment, but independently pursued the subject in his own methodical, relentless fashion. He was particularly interested in her off-the-cuff remark that there were more complicated ciphers, including a foolproof "U.S. Code." He begged his father to check out all the books in the City College library that dealt with cryptography. Bailey Diffie promptly returned with an armload of books. Two of them were written for children; Diffie quickly devoured those. But then he got bogged down in Helen Forché Gaines's Cryptanalysis, a rather sophisticated 1939 tome.

Gaines offered a well-organized set of challenges that would provide hardworking amateurs an education in classical cryptographic systems. Many of these were refinements of advances made centuries ago, which in turn were more complicated variations of the earlier substitution ciphers. The best known were the polyalphabetic systems, first hatched in Vatican catacombs and later revealed in the early 1500s by a German monk named Johannes Trithemius. Published in 1518-two years after his death-Trithemius's Polygraphia introduced the use of tables, or tableaux, wherein each line was a separate, reshuffled alphabet. When you encoded your message, you transformed the first character of the text using the alphabet on the first line of the tableau. For the second character of your message you'd repeat the process with the scrambled alphabet on the second line, and so on.

On the heels of Trithemius came the innovations of a sixteenth-century French diplomat named Blaise de Vigenére. Here was a man who had penetrated the soul of crypto. "All things in the world constitute a cipher," he once observed. "All nature is merely a cipher and a secret writing." In the most famous of almost two dozen books he produced after his retirement from the diplomatic service, Vigenère produced devastating variations on previous polyalphabetic systems, adding complexity with a less predictable tableaux and "autokeys" that made use of the plaintext itself as a streaming key. The Vigenère system won a lasting reputation for security-it was known as le chiffre indéchiffrable-so much so that until almost the twentieth century, some armchair cryptographers believed that a certain streamlined version of the system was the sine qua non of cryptosystems.

Actually, by the time Diffie encountered them, the cryptologic arts had progressed dramatically since Vigenère. Still, Diffie's juvenile inquiries led him to think that Vigenère was the endpoint of the subject. Bored by the thought that cryptography was a problem already solved, he didn't delve too deeply into Gaines's book. His obsession with codes faded. At the time, he also felt that everybody was interested in codes, and, as a dogged contrarian, "this made it seem vulgar to me," he later recalled. "Instead, I learned about ancient fortifications, military maps, camouflage, poison gas, and germ warfare." He came to share his interests with a small group of teenage friends, and even considered pursuing a career in the armed forces, checking out the ROTC programs of universities he was interested in. But only one of Diffie's militia-minded clique actually enlisted in one of the armed services-and died in Vietnam.

Ultimately it was mathematics, not munitions, which dictated Diffie's choice of college. Math offered one thing that history did not: a sense of absolute truth. "I think that one of the central dilemmas of Whit's life has been to figure out what is really true," explains Mary Fischer, who says that early in the boy's life, Diffie's father was called to school and told that his son was a genius. As Fischer tells it, Bailey Diffie's reaction was to offer a ruse, in hopes that it would provoke discipline. He told Diffie that he wasn't as bright as other boys, but if he worked harder than those favored with high intelligence and applied himself, he might be able to achieve something. "With some children that might have worked," says Fischer, "but with Whit it was a bad tactic. It shook him for years, and I think it gave Whit a real hunger for what was ground-zero truth."

Though Diffie performed competently in school, he never did apply himself to the degree his father hoped. He was sometimes unruly in class; he worked best with material untainted by the stigma of having been assigned. Once a calculus teacher, fed up with Whit's noise-making, remarked, "One day you'll be roasting marshmallows in here!" and sure enough, the next class Diffie brought a Sterno canto toast the marshmallows a friend smuggled into school. He failedto fulfill the requirements for a full academic diploma, settling for a minimal distinction known as a general diploma. Nor did he attend graduation; he left with his father on a European trip. (The great tragedy of Diffie's high school years was the death of his mother; he still avoids talking about it.) Only stratospheric scores on standardized tests enabled him to enter the Massachusetts Institute of Technology in 1961.

"I wasn't a very good student there, either," Diffie admits. He was, however, dazzled by the brainpower of the student body, a collection of incandescent outcasts, visionaries, and prodigies, some of whom could solve in a minute problems that would take Diffie a day to complete. Of these mental luminaries, Whitfield Diffie might have seemed the least likely to produce a world-changing breakthrough. But since his brilliant friends were human beings and not high-powered automata, their trajectories proved far from predictable. Some of the very brightest wound up cycling through esoteric computer simulations, or proselytizing smart drugs, or teaching Transcendental Meditation.

Contemporaries from MIT recall Diffie vividly as a quirky teenager with blond hair sticking out from his head by two inches ("You wanted to take a lawn mower to it," says a friend). He bounded through campus on tiptoe, a weird walk that became an unmistakable signature in motion. But he was noted for his deep understanding of numbers as well.

He also took up computer programming-at first, Diffie now says, to get out of the draft. "I thought of computers as very low class," he says. "I thought of myself as a pure mathematician and was interested in partial differential equations and topology and things like that." But by 1965, when Diffie graduated from MIT, the Vietnam War was raging and he found himself deeply disenchanted with the trappings of armed conflict. "I had become a peacenik," he says. Not to mention a full-blown eccentric. He and his girlfriend lived in a small Cambridge apartment that eventually became packed with glass-walled tanks to hold their prodigious collection of exotic fauna. An aficionado of Chinese food, Diffie was also known for carrying around a pair of elegant chopsticks, much the way a serious billiard player totes his favorite cue.

To avoid the draft, Diffie accepted a job at the Mitre Corporation, which, as a defense contractor, could shelter its young employees from military service. His work had no direct connection to the war effort: he worked under a mathematician named Roland Silver, teaming up with another colleague to write a software package called Math-lab, which later evolved into a well-known symbolic mathematical manipulation system called Macsyma. (Though few knew of the nature of his contribution, the nerd cognoscenti understood that Diffie's work here involved a virtuosic mastery of arithmetic, numbers theory, and computer programming.)

Best of all, Diffie's team did not have to work at the Mitre offices but, in 1966, became a resident guest of the esteemed Marvin Minsky in the MIT artificial intelligence lab. During the three years he worked there, Diffie became part of this storied experiment in making machines smart, in pushing the frontiers of computer programming and in establishing an information-sharing ethos as the ground zero of computer culture. One aspect of this hacker-oriented society would turn out to be particularly relevant to the direction that Diffie's interests were heading. Just as some words in various languages have no meaning to drastically different civilizations (why would a tropical society need to speak of "snow"?), the AI lab had no technological equivalent for a term like "proprietary." Information was assumed to be as accessible as the air itself. As a consequence, there were no software locks on the operating system written by the MIT wizards.

Unlike his peers, however, Diffie believed that technology should offer a sense of privacy. And unlike some of his hacker colleagues, whose greatest kick came from playing in forbidden computer playgrounds, Diffie was drawn to questions of what software could be written to ensure that someone's files could not be accessed by intruders. To be sure, he participated in the literal safecracking that was a standard hobby in the AI lab: a favorite hacker pastime involved discovering new ways of opening government-approved secure safes. But Diffie got more of a kick from the protection of a strongly built safe than the rush of breaking a poorly designed system of locks and tumblers. He liked to keep his things in high-security filing cabinets and military safes.

In the information age, however, the ultimate information stronghold resides in software, not hardware: virtual safes protecting precious data. Information, after all, represents the treasure of the modern age, as valuable as all the doubloons and bangles of previous eras. The field charged with this responsibility back then was computer security, then in a nascent stage. Not many people bothered to discuss its philosophical underpinnings. But Diffie would often engage his boss in conversations on security. Inevitably, cryptography entered into their discussions.

Silver had some knowledge in the field, and the elder man opened Diffie's eyes to things unimaginable in his fifth-grade independent study. One day the pair sat in the cafeteria at Tech Square, the boxy nine-story building whose upper levels housed the AI lab, and Silver carefully explained to Diffie how modern cryptosystems worked.

Naturally, they depended on machinery. The machines that did the work-whether electromechanical devices like the Enigma cipher machines used by the Germans in World War II, or a contemporary computer-driven system-scrambled messages and documents by applying a unique recipe that would change the message, character by character. (The recipe for those transformations would be a set of complicated mathematical formulas or algorithms.) Only someone who had an identical machine or software program could reverse the process and divine the plaintext, with use of the special numerical key that had helped encrypt it.

In the case of the Enigma machines, that key involved "settings," the positions of the various code wheels that determined how each letter would be changed. Each day the encrypters would reset the wheels in a different way; those receiving the message would already have been informed of what those settings should be on that given day. That's why the Allied coup of recovering live Enigma machines-the key intelligence breakthrough of World War II-was only part of the elaborate codebreaking process that took place at Bletchley Park in England. The cryptanalysts also had to learn the process by which the Axis foes made their settings; then they could conduct what was known as a "brute force" attack that required going through all the possible combinations of settings. This could be efficiently done only by creating machines that were the forerunners of modern computers.

With computers, the equivalent of Enigma settings would become a digital key, a long string of numbers that would help determine how the system would transform the original message. Of course, the intended recipient of the message had to have not only the same computer program, but also that same key. But both mechanical and digital systems had two components: a so-called black box with the rules of transformation and a key that you'd feed into the black box along with your everyday message in plain English. Such was the background for what Silver talked about to Diffie that day-but not being privy to government secrets, he actually knew few of the details. He was able to explain, however, how computer cryptosystems generated a series of digits that represented a keystream, and how that would be "xor-ed" with the plaintext stream to get a ciphertext. (As any computer scientist knows, an xor operation involves pairing a digital bit with another bit, and generating a one or zero depending on whether they match.) If the key is suitably unpredictable, your output would be the most imponderable string of gibberish imaginable, recoverable (one hoped) only by using that same key to reverse the process.

Imponderable, of course, is a relative term, but those who devised cryptosystems had a standard to live up to: randomness. The idea was to create ciphertext that appeared to be as close to a random string of characters as possible. Otherwise, a smart, dedicated, and resourceful codebreaker could seize upon even the most subtle of patterns and eventually reconstruct the original message. A totally random stream could produce uncrackable code-this essentially represented the most secure form of encryption possible, the so-called one-time pad, a system that provided a truly randomly chosen substitute for every letter in the plaintext. One-time pads were the only cryptographic solution that was mathematically certain to be impervious to cryptanalysis.

The problem with one-time pads, however, was that for every character in the message, you needed a different number in the "key material" that originally transformed readable plaintext into jumbled ciphertext. In other words, a key for a one-time pad system had to be at least as long as the message and couldn't be used more than once. The unwieldiness of the process made it difficult to implement in the field. Even serious attempts to deploy one-time pads were commonly undermined by those tempted to save time and energy by reusing a pad.

His conversations with Silver excited Diffie. The subject of "pseudo-randomness" was clearly of importance to both the mathematical and real worlds, where security and privacy depended on the effectiveness of those codes. How close to randomness could we go? Obviously, there was a lot of work going on to discover the answer to that question-but the work was going on behind steep barriers erected and maintained by the government's intelligence agencies.

In fact, just about all the news about modern cryptography was behind that barrier. Everyone else had to rely on the same texts Whitfield Diffie had encountered in the fifth grade. And they didn't talk about how one went about changing the orderly procession of ones and zeros in a computer message to a different set of totally inscrutable ones and zeros using state-of-the-art stuff like Fibonacci generators, shift registers, or nonlinear feedback logic. Diffie resented this. "A well-developed technology is being kept secret!" he thought. He began to stew over this injustice. One day, walking with Silver along Mass Avenue near the railroad tracks, he spilled his concerns. Cryptography is vital to human privacy! he railed. Maybe, he suggested, passionate researchers in the public sector should attempt to liberate the subject. "If we put our minds to it," he told Silver, "we could rediscover a lot of that material." That is, they could virtually declassify it.

Silver was skeptical. "A lot of very smart people work at the NSA," he said, referring to the National Security Agency, the U.S. government's citadel of cryptography. After all, Silver explained, this organization had not only some of the best brains in the country, but billions of dollars in support. Its workers had years of experience and full access to recent cryptographic discoveries and techniques unknown to the hoi polloi-however intelligent-without high security clearances. The agency had supercomputers in its basement that made even MIT's state-of-the-art mainframe computers look like pocket calculators. How could outsiders like Diffie and Silver hope to match that?

Silver also told Diffie a story about his own NSA experience years earlier while writing a random number generator for the Digital Equipment Corporation's PDP-1 machine. He needed some information: his reasons were noncryptographic; he simply had a certain mathematical need, a polynomial number with some particular properties. He was sure that a friend of his at the NSA would know the answer instantly, and he put in a call. "Yes, I do know," said the friend. What was it? After a very long silence, during which Silver assumed that the friend was asking permission, the NSA scientist returned to the phone. Silver heard, in a conspiratorial whisper, "x to the twenty-fifth, plus x to the seventh, plus one."

Diffie was outraged at this secretiveness. He'd heard about the NSA, of course, but hadn't known that much about it. Just what was this organization, which acted as if it actually owned mathematical truths?...