Wisecrackers

"It may roundly be asserted that human ingenuity cannot concoct a cipher which human ingenuity cannot resolve."
- Edgar Allan Poe
If you are a cryptographer, you know one code that requires no calculation to decipher: when the calendar hits the last week in August, you must pack up your shorts and T-shirts, proceed to the beachfront campus at the University of California at Santa Barbara, pick up a plastic badge at the front desk in a residence hall, and attend Crypto - five days of seminars and receptions to discuss the state of encipherment, decoding, and various other cryptographic matters, ranging from elliptical curves to secret sharing. Last year's event could not have come at a better time. Crypto '95 happened at the peak of a mania about the once arcane study of communicating in code. The networking of the world's computers had thrust into the mainstream popular notions of cryptography, the art of keeping secrets readable only to insiders, as well as cryptanalysis, the art of outsiders cracking the codes to get at those secrets. Cryptography was gaining currency as the only way of securing the global info-matrix from a host of meanies, ranging from info-thieves to government snoops. Some people now regard crypto's scrambling mechanisms as a panacea. Just flood the world with it, crypto-enthusiasts say, and our secrets are safe. They crow that the technological problems in securing the Net have largely been solved. Naturally, this leads proponents to the optimistic outlook that cryptography will ensure privacy, as well as secure electronic money - or e-money - the key to burgeoning business on the electronic frontier. A highlight of Crypto '95 was a rambling speech by a grizzled, bearded man who until recently addressed only crowds authorized to receive wisdom deemed top-secret by the US government. His name was Robert Morris Sr., recently retired as the senior scientist at the National Security Agency, the cloistered intelligence organization at Fort Meade, Maryland. His presence drew an auditorium full of fascinated cryptographers, who leaned forward in their seats, hoping for an epiphany. The NSA's skills in cracking crypto are legendary, as is its silence in revealing how advanced those skills are. Would Morris slip some of that wisdom into his talk? Yes and no. Trade secrets were not forthcoming. But Morris, in sort of the spirit of the Eastern masters, did utter a pair of truisms - fundamental tenets of the crypto creed, as it were. Tenet Number One: Never underestimate the time, expense, and effort an opponent will expend to break a code. This was directed at codemakers. He was referring to those moments of dark speculation that keep ace cryptographers staring at the ceiling long after losers have retreated to dreamland, wondering: Have I plugged every hole? Anticipated every attack? The subtext of Morris's point was that cryptography is best left to the paranoid, those who believe beyond question that their opponents just may be very rich, very clever, and very dedicated - hellhounds on the trail. Those opponents can and will launch vicious direct attacks on your codes by mustering who knows how much computer power. If you assume that those who want your secrets are underfinanced, undermotivated, or just plain goofballs, then you are the goofball. And you've got no business on a crypto team. Remember: beware the frontal assault. Tenet Number Two spoke to the code breakers: Look for plaintext. In the jargon of the field, plaintext is a message of regular words that anybody can read - before the words get scrambled. No matter how baffling the task of code breaking might seem, very fallible human beings are the ones who must employ these sophisticated systems. And indeed they fail. Sometime, when one least expects it, a passage - or an entire message! - might somehow lie unencoded within seemingly impenetrable code. In that case, you can read it as easily as a fortune cookie. But that's only if you were open to the possibility that the plaintext might be there. Remember: exploit your opponent's mistakes. Quite coincidentally, just as Morris was delivering his speech, a movement was afoot to translate his points into action. An informal, yet formidable, group of amateurs in the cryptanalysis game was forming and finding success in cracking code that supposedly was vulnerable only to the likes of the Fort Meade crowd. Disgusted at seeing watered-down versions of cryptography, this group set out to expose the pretenders. Their message: just because it's crypto doesn't mean it's safe. Their work would create severe embarrassment for those promulgating security systems that were exposed as pitifully weak. The crackers' victims included two mighty institutions: the US government and Netscape Communications Corp.
(Page 2) These self-described cypherpunks included students, researchers, mathematicians, hackers, activists, and joyful troublemakers from around the world. Some of them became instant media stars: the researcher in France who used massive computer power to find a key to certain Netscape crypto, or the two UC Berkeley students who, with minimal computer power, discovered a mistake that shook loose a Netscape key. But, in truth, it would be an aggregate effort, powered by the pooled minds and computer resources of the Net. In the end, the Net would emerge as a star in its own right, ushering in a new era of collective code breaking. In short, the cryptocracking fraternity had been thrown open to the rabble. These new code breakers are not interested in crime and espionage, but in making a political point and reaping great fun in the process. And so far, they're succeeding on both counts.
Beating deadline by 40 quadrillion years The story begins, sort of, with the RSA-129 challenge, an obscure code-breaking challenge made in 1977. Martin Gardner spelled it out in his famous Scientific American article, where the mainstream world first learned about the breakthrough in public key cryptography that would expand the technology of privacy to the masses. The estimable Gardner began with a celebrated quote from Edgar Allan Poe: "It may roundly be asserted that human ingenuity cannot concoct a cipher which human ingenuity cannot resolve." Recent developments made that statement dead wrong, Gardner declared. The emergence of the RSA cryptosystem, which seemed to provide a simple way for everyone to keep secrets from all listeners - even those with unlimited time and resources - was an important part of Gardner's argument. The RSA system (which derives its name from its three inventors: Ron Rivest, Adi Shamir, and Leonard Adleman) was the first, and is still the dominant, form of exploiting the breakthrough in public key cryptography, which uses pairs of keys, rather than single keys, to scramble and decode messages when sending them over insecure channels. To prove the system's soundness, Gardner had asked the three inventors to devise a challenge. Rivest picked an RSA key of 129 digits, encoded a message with it, and dared anyone to read it. Rivest, Shamir, and Adleman offered US$100 to anyone who decoded the message, and they didn't seem overly concerned about the money. After all, Rivest estimated that if someone dedicated a supercomputer to breaking the code, it would take 40 quadrillion years. For those of you keeping score, that's a 40 with 15 zeros following it. But even if you did not accept that time frame (Rivest now says it was a miscalculation), a much, much shorter time frame - a billion years, say, or a measly few million years - would ensure that anyone breathing today's air would be fossilized before the secret of the RSA-129 message would be revealed. That's just one reason Gardner believed the Poe quote was erroneous. Gardner finished his column with a Requiem for all the great code breakers throughout history. As codes have become stronger, he wrote, "the talents of these experts have gradually become less useful." And now, with the RSA system, "these people are standing on trapdoors that are about to spring open and possibly drop them completely out of sight." Fifteen years later, public key encryption had spread into many security systems. RSA Data Security Inc., a company specializing in the RSA system, licenses to many big companies such as Lotus and Microsoft. But perhaps the most popular public key encryption program around is PGP - Pretty Good Privacy, Phil Zimmermann's freely distributed software that lets two people send e-mail to each other that they can read but eavesdroppers can't. Or can they? This was the question raised in 1992 by Derek Atkins, then a 21-year-old electrical engineering student at MIT. When Atkins first saw Zimmermann's program, he immediately recognized its importance and joined the impromptu, far-flung, and unpaid development team that works on new versions of the software. But as Atkins talked to friends about the program, he began to wonder what attacks might work against it. Robert Morris implied that there are two general ways to crack a cryptosystem. One is to explore the possibility that an unintended weakness will enable you to break the codes - akin to Morris's suggestion to look for plaintext. Expect people to make mistakes. The other method is to unleash a frontal assault on the crypto, applying more resources - both computational and intellectual - toward breaking the code than the system designers would have thought possible. Beware the frontal assault.
(Page 3) Here's a good way to distinguish between the two: Let's say you've got a friend's ATM card and, purely for experimental purposes, you want to draw money out of the bank. But you don't have the personal identification number. In an attack focusing on mistakes, you try easily recognizable key combinations - those that spell out the name of your friend's dog, or that form a simple number combination, such as 1234. Maybe you get lucky and guess right. Your chances depend on the negligence of your friend. But a frontal assault, while more tedious and time-consuming, is more likely to succeed. First, you type in 0000. If that doesn't work, you try 0001. And you methodically count upward - searching what is known as the keyspace, or space of possible keys - until you hit the right PIN. As it turns out, something existed that could deliver both the computational and intellectual resources required to pull off a credible direct attack. To Atkins and his friends, that something was the Net. They suspected that by tapping into a previously unavailable resource - the thousands of computers accessible through the Internet - they might make code-breaking history. They would regard the aggregate computing power of Internet users as a giant supercomputer, a kludged cousin to the ones that supposedly exist in Fort Meade's basement. So, Atkins and his colleagues - including Michael Graff at Iowa State University and Paul Leyland of Oxford University - decided to try an attack based on dispersed resources and fanatical dedication. They also agreed that the most direct route to cracking PGP would be to employ a mathematical technique called factoring. What is factoring and why is it important? Well, the strength of PGP or other cryptosystems that use RSA public key cryptography, rests partly on certain mathematical principles. For reasons that your high school math teacher may know, it's very easy to multiply two big prime numbers to get a whomping huge number that might act as a key to encode and decipher text. But if you present that huge number to someone, it's damn difficult for him or her to figure out those two original prime numbers. Actually, "damn difficult" isn't nearly strong enough to convey how hard it is. But that difficulty is essential, because in the RSA system eavesdroppers can easily obtain the number that comes when the two primes are multiplied together. Yet to use that number to read stolen messages, it must be factored to yield the original primes. When the crackers considered a direct attack against PGP, however, they realized that the numbers routinely used as keys were so big that, even with the power of the Net, they could not be factored. Then Arjen Lenstra, a noted mathematician at Bellcore, pointed them to the RSA-129 challenge. Why not use the collective force of the Internet to attack RSA-129? So, 15 years after Rivest threw down the gauntlet with the challenge, Atkins and his colleagues joined forces with the Net to attempt to collect that $100 reward. What's more, the crackers figured they could do it in a matter of months. The first, and probably most important, thing Atkins and company required was a good factoring algorithm, the mathematical technique used to narrow the possibilities of which two prime numbers might have combined to make that 129-digit composite. As it turns out, there had been some conceptual advances in this area since Gardner's column was published. Specifically, someone had devised the "double large prime multiple polynomial variation of the quadratic sieve." Atkins says that this was a huge time-saver. The method involves searching for certain numbers known as unit vectors. After identifying the unit vectors, you can combine them to chart mathematical relations in a way that yields the two original primes. "One way of looking at it is that we were searching for 8 million needles in a haystack full of countless needles, and any of these needles is as good as any other," says Atkins. "You're not looking for any particular needle - you just find enough of them and combine them in a special mathematical means to actually factor the number." This technique was perfect for a distributed Internet attack, where hundreds of people could donate computer time to solve the problem. The crackers needed about half a million unit vectors, but not every possible one was needed to factor the number. "If you say you'll start searching from a certain location and then you fall off the Earth, it's not a problem," says Atkins. "If you don't turn in your needles, someone else will turn them in later on."
(Page 4) By late summer 1993, Atkins and company had the software ready, and the team began recruiting volunteers for the unit vector hunt. They sent calls out through mailing lists and newsgroups. Anyone who downloaded the software could play. Participants put the program on their machines, and when their computers had accumulated 25 "needles," they automatically sent the needles to MIT. The response was terrific: more than 1,600 machines from all over the world worked on the problem. "We had every continent except Antarctica," Atkins says. Computers ranged from garden-variety PCs to Bellcore's 16,000-processor MasPar supercomputer, one of the most powerful computers in the world. A standard measurement of computer power is a mips year, based on a million-instructions-per-second machine running for a solid year. From September 1993 to April 1994, the RSA-129 experiment used about 5,000 mips years. Then Atkins and the others guessed that they had enough unit vectors for the calculation. "Basically, what happens is you get all these needles and you put them in a very sparse matrix," says Atkins. "And you need a very powerful computer to take the matrix and squoosh it down." Atkins sent a tape with 400 Mbytes worth of unit vectors via FedEx to Lenstra at Bellcore. Lenstra fed it to his machine, and for two days it squooshed. On April 26, 1994, roughly eight months after they started, Atkins posted the following message on the Net:
We are happy to announce that RSA-129 = 114381625757888867669235779976146612010218296 72124236256256184293570693524573389783059712 3563958705058989075147599290026879543541 = 349052951084765094914784961990389813341776463 8493387843990820577 * 32769132993266709549961 988190834461413177642967992942539798288533
Applying the key yielded the message that supposedly would not be read for 40 quadrillion years: "The magic words are squeamish ossifrage." To be fair, Rivest did not exactly pass out when he saw the magic words presented to him. For one thing, in the intervening years he had forgotten what the message said. And then, as new factoring algorithms emerged, he had come to accept the fact that one day he might have to write out a check for $100. (The successful crackers donated the money to the Free Software Foundation.) "It was probably accurate for the analysis of the fastest algorithm we knew about at the time, but technology was moving fast on the factoring frontier," Rivest says. But hold on here. The very idea of a factoring frontier throws some doubt on the security of the public key cryptosystem. Now, it's important to note that breaking RSA-129 does not mean that PGP in particular, or RSA encryption in general, is weak. An RSA key based on a 129-digit prime is only 425 bits long. Atkins later calculated that had his team attempted the same task, using the same factoring algorithm with the recommended RSA key of 1024 bits, their computers would still be working on the problem - for a few million more years. Yet that degree of futility was once predicted for those attempting to factor RSA-129. Is it possible that one day even newer factoring techniques might melt down even the fattest RSA keys? That's not taking into account the possibility of a dramatic advance in hardware, such as the development of quantum computers, machines that take advantage of subatomic physics to run much faster than our current models. (Think more like the difference between turtles and laser beams.) All that is speculation, though. The reality is that Derek Atkins and his colleagues took what seemed an invincible problem and, working informally with an ad hoc collection of computers, managed to crack it. "What we learned is that a bunch of amateurs can get together and do this," Atkins says. The breaking of RSA-129 established a disturbing principle, albeit one embedded in Robert Morris's first bit of wisdom: Don't ever underestimate what a few good hackers can do with a good algorithm and a few thousand mips years.
The cypherpunks key-cracking ring The next step in this strange form of participatory cryptanalysis began when Hal Finney made his challenge. A Santa Barbara, California, programmer and a participant in PGP development, Finney was a regular follower of the cypherpunks mailing list, which is where he laid out his idea. The cypherpunks are a loose confederation of crypto-activists, who have for the past three years conducted an active colloquy about issues related to cryptography and participated in the field by writing crypto software, ranging from encryption toolkits to anonymous remailers.
(Page 5) Throughout July '95, the cypherpunks list filled with messages speculating on ways to crack what was considered the relatively weak crypto used in Microsoft's database program Access. The posters were not interested in raiding anyone's data. The idea was to slam an exclamation point on what was considered an intolerable political situation: the United States government, by limiting the key size of cryptography approved for export, was foisting a wimpy form of crypto on all of us. The July postings opened a new chapter in cypherpunk history: garage-band cryptanalysis - the cracking, rather than the creating, of code. Now that computer security had become the hot topic of a broader population, the cypherpunks were about to engage in a series of actions that would highlight the flimsy state of our patchwork security system - one hobbled by government interference and amateurish implementation. Presumably, observers would then adopt the obvious conclusion: only a strong, well-supported cryptography infrastructure could address the complex problems of a global network. In the case of export controls, the system just wasn't working. The strength of cryptosystems commonly depends on the size of the keys that code and decode the messages. The longer the key, the stronger the crypto. Domestically, there are no limits on key sizes. But government officials believe that the widespread use of strong cryptography outside the US would hamper law enforcement and threaten national security. They fear the specter of terrorists, child pornographers, and drug dealers taking advantage of a ready-made security system. As a result, the US limits key sizes in shrink-wrapped software shipped outside the country - generally to 40 bits. But in effect, the government often winds up limiting crypto for the rest of us. Since companies like Microsoft, Sun Microsystems, and Apple Computer generate about half their revenues overseas, they're loath to put out two versions of their products. Some simply use the short-key versions in all models. Others try to support two versions: a domestic version with long keys and an export version with short keys. In either case, a standard system with strong cryptography - the ideal solution - eludes the companies. If someone dramatically exposed the fact that 40-bit crypto could be broken by amateurs, this fact would be very useful propaganda for the pro-crypto agenda. But how could the cypherpunks achieve this? Again, in line with Morris's first tenet, they chose a frontal assault, unleashing huge resources. But factoring would not be the right approach in this case. Instead, the cypherpunks had an opportunity for a brute-force attack, an attempt to try out every possible key. Let's go back to our ATM example. A typical ATM PIN has only 10,000 possibilities, so a brute-force attack means that eventually you'll be able to sweep every possibility in the keyspace in 10,000 attempts at most. The cypherpunks would attempt the same thing with Microsoft Access, which relies on an encryption method that uses a single key to encode and decipher data. Experts recommend that the key be a minimum of 128 bits, so presumably a 40-bit key would be much more vulnerable. Still, a 40-bit key has about a trillion actual possibilities, enough to keep a mass of workstations busy for days. But that was what the cypherpunks had in mind: a phalanx of attackers, each of whom would claim some portion of keyspace, test it, and then request another. The process would continue until someone found the key. As it turns out, the cypherpunks never found the key to Microsoft Access; the effort got bogged down for technical reasons that the participants still haven't identified. (Some, like Finney, say they failed because Access didn't use a single-key encryption.) Finney had a strong interest in how cryptography would be used in electronic commerce, and he'd become familiar with the technology used by Netscape Communications Corp. in its Navigator browser. Called Secure Sockets Layer, it used RSA technology, which RSA Data Security claimed provided bulletproof security. But Netscape, like Microsoft, was not about to violate US export control laws. The company released two commercial versions of the browser: a domestic version with a 128-bit key and a version for export, with the required 40-bit key. Finney wondered: what if the cypherpunks were to hack Netscape? Just as Rivest had done with RSA-129, Finney constructed a challenge. He performed a dummy transaction within Netscape and used the export version to encode it. He then challenged his fellow cypherpunks to break his encoded transaction. So began a race to be the first to complete a brute-force attack on Netscape's export-level security - and to embarrass the US officials who assured people that such security was sufficient.
(Page 6) The first attempt was organized by Adam Back, a 25-year-old computer science student at the University of Exeter in England. Back was one of a number of students who had been reading the cypherpunk list to satisfy their curiosity about cryptography. Over the previous month, Back - with the help of two colleagues - became a central figure in writing scripts to allow people to participate in a group crack. Back's original intent was to apportion the keyspace among many people by assigning slices from his Web page. But one programmer, an Australian named Eric Young, offered to organize half the search himself, moving through the second half of possible keys. As it turned out, the first half of the keyspace would be swept by a single programmer - a 24-year-old, American-born grad student at Sweden's Linköping University named David Byers. His university had a powerful MasPar MP-1 computer, which could search the keyspace at about 1.5-million keys per second. He ran the program on the MasPar for six hours at a time over several days, but then had to interrupt the process. "Someone else had to use the MasPar for a weeklong project," Byers says. He insists he had no problem with this: "People doing 'real work' should have precedence." It was during this lull in the action that a second attempt got underway by an individual who wanted to see if he could solve the problem on his own. Damien Doligez was a 27-year-old computer scientist who had just gotten his PhD and was working as a researcher at INRIA, a French government computer lab. His office was situated in a cluster of shacks in a former NATO base a few miles outside Versailles. He knew that the cracking feat was possible and assumed that the cypherpunks would have fulfilled Finney's challenge fairly quickly. Still, Doligez decided to do it himself. Doligez had access to an entire network of computers at INRIA, including a KSR-1 - the equivalent of six to ten workstations. Over the next week, Doligez concocted a small program to allow a computer to quickly test a potential key. Then he adapted the program to work on the various machines on the INRIA network, as well as some machines at nearby universities. His workstation acted as the server, distributing the work to a few dozen machines. Five minutes after an INRIA worker would stray from his or her computer, Doligez's program would take over the machine, crunching perhaps 10,000 keys per second. Simply by touching the keyboard, a user could regain control over the machine. No one complained. "It's very open here; there's no administrative problem using those machines," he explains. "You just have to ask for permission first. I never got the answer No." Doligez figured his odds of finding the key first would be better if he started from the end of the keyspace and worked backward. After a few false starts and glitches, the program was working fine when Doligez left work on Friday, August 11, for a four-day weekend. Over the holiday, he used his home computer to check his workstation. "I saw that it found the key," he says. But he figured he'd wait until he went back to work to make the announcement. Meanwhile, the ad hoc British/Austra- lian/Swedish team kept at it. Using an array of workstations, Young in Australia had swept the top half of the keyspace, and had not found the key. It had been up to Byers in Sweden to search the first half of the space. His first few days had been fruitless. He eventually regained control of the MasPar but still hadn't found the key by Friday, August 11, when he set things up and left for the weekend. Only an hour or so after Byers left work, the MasPar located the key. It was nestled just below the halfway point in the keyspace. However, Byers did not discover this until he returned to work on Tuesday. He e-mailed the key to Adam Back. "I wasn't thinking about posting the result publicly," Byers says. "I didn't think it was that important. It was something I was just doing for fun." Back immediately tried to use the key to decrypt the message in Finney's challenge. "Once you've got the key, you've got to decode it," he says. "But, I was making a small error. I was only getting the first part of the message, and the rest was garbled." The next day, Back took his wife and kids to the beach. That was the day Doligez drove to work from his home outside Paris and recovered the key from his workstation. He successfully decrypted the message and posted his discovery to the cypherpunks. Those familiar with the RSA-129 crack would appreciate the address of the fictional character that Hal Finney had created in his coded message: "Mr. Cosmic Kumquat, SSL Trusters Inc., 1234 Squeamish Ossifrage Road, Anywhere, NY 12345 (USA).''
(Page 7) Posting to the cypherpunks list turned out to be an inexpensive means of getting lustrous media exposure. Reporters from The New York Times and The Wall Street Journal routinely scan it for scoops. Once one of those venerable broadsheets runs an article, media bottom feeders descend en masse. When reporters besieged Doligez - so much so that he quickly created a "virtual press conference" on his Web page - he took pains to emphasize that this could be done only because the US export standards mandated a weak form of crypto. Because the break occurred just a week after Netscape enjoyed an extraordinarily successful public stock offering, some journalists played the crack as if it spoke to the state of the company's overall security, and not as an example of the government's export rules weakening software. In a message Netscape sent over the Net later that week, the company noted that Doligez had simply broken one message - and that had taken about 64 mips years to carry out. Netscape correctly noted that its domestic version also used a much sounder 128-bit key. Doligez agreed that with his resources, attempting a brute-force attack on such a key would be ludicrous. "We are not even talking centuries," he says. He'd even done the math. "If you had a billion machines, each one of them a million times as powerful as what I had, you would still need about 6 billion years to do it." As far as the cypherpunks were concerned, this was the point: export-level crypto was needlessly weak. Unfortunately, the stronger domestic version of Netscape Navigator is effective only when communicating with similarly configured US versions. Yet the Net is supposed to be a global phenomenon, with a single level of high security. The cypherpunks had made the point that export-control crypto failed to heed the first of Bob Morris's warnings. But what about the second point? The one about exploiting your opponent's mistakes? That would be left to two students at the University of California at Berkeley.
Not your random hack Only a few weeks later, in September 1995, David Wagner was sitting in front of his computer, looking at Netscape's security programs. He couldn't believe what he saw. "Something that looks strange jumps at you," he says. "It just kind of gets your attention. That's what pointed me to it." Wagner was a 21-year-old graduate student at Berkeley. He had arrived four weeks earlier and met a fellow first-year grad student, 22-year-old Canadian Ian Goldberg. Both held similar interests in computer-security issues, and both had been inspired by the cypherpunk hacks. They, too, liked the idea of hacking Netscape. But the brute-force attacks had just been completed, so the two students began to explore a different mode of attack - looking for plaintext. Could it be that Netscape's security team had made some egregious error in implementing their software, exposing what might be millions of electronic commerce transactions to eavesdroppers? Not likely. But, as Morris suggests, you never know until you look. The folks at Netscape, after all, were human. And that's when Wagner saw it. Buried in the code were the instructions for Netscape's pseudo-random number generator. An important part of many cryptosystems, this piece of code scrambles the plaintext in such a way that the encoded text has no systematic means of conversion. It is well known that a lack of true randomness is a weakness smart code breakers can eventually exploit. So, it's important to have a solid PRNG - something that spins the alphabetic roulette wheel quite thoroughly. A good PRNG always uses an unpredictable "seed," a number that begins the randomization process. Since, unlike dice, computers do the same thing each time they run, it's essential to begin the process with a seed that a potential enemy cannot possibly guess. Methods of choosing a seed often include using some off-the-wall statistics from the real world - the position of the mouse, for instance.
(Page 8) Netscape ignored this wisdom. As Wagner saw, its PRNG worked by taking the time of day and two forms of identification called the Process ID and the Parent ID. This was a disaster. Finding the first part of the seed is a no-brainer - just run through various times of day. In many cases, the other parts of the seed, the identification numbers, are easy to intercept, particularly if someone is sharing a server with a number of people - as often happens in an Internet environment, particularly a university like UC Berkeley. "If an attacker has an account on your machine, it's trivial," says Goldberg. "But it's not too hard to figure out the IDs even if the attacker has no way of accessing the machine." This is because the identification numbers are only 15 bits long - not a difficult task for a brute-force attack. Put another way, Netscape made this sort of mistake: Let's say you are playing a game with a friend in which you think of any object in the world and your friend has to guess it. Chances are unless you choose something obvious, your friend isn't going to nail it right away. But what if you slip up and say you're thinking of famous pictures in the Louvre? It radically narrows the possibilities. Wagner and Goldberg began writing a program to take advantage of Netscape's weakness. They worked over a weekend, and on Sunday night they tested it. By zeroing in on the huge flaw in Netscape's implementation, they were able to find a key in less than a minute. So much for Netscape security. Goldberg posted the result to the cypherpunks mailing list that night. "We didn't expect lots of press," he says. Silly boy. After The New York Times ran a story, the two grad students were deluged with questions from journalists and curiosity seekers. They used the opportunity to give a warning. "We're good guys," says Goldberg. "But we don't know if this flaw has been discovered by bad guys." Better cypherpunks than crooks. But you have to figure that sooner or later, crooks are going to get in this game. Unlike the first Netscape crack, where the company could quite rightfully claim that its otherwise strong crypto was crippled by government restrictions, this was a total flub by whoever was in charge of software security. Crackers didn't need to tap into a network of workstations or get access to a supercomputer. In certain circumstances, all you needed was a minute's worth of crunching on a Pentium machine. This wasn't a case of poor judgment - it was incompetence. To its credit, Netscape immediately rushed out a new version of Navigator that addressed the problem. But if the company blew this, what other mistakes, perhaps more critical, has it made? None of the cypherpunks involved in the cracking project want to single out Netscape as the worst offender. To the contrary, they praise the company as being responsive to reports of security flaws. Indeed, soon after the Berkeley hack, Netscape set up its own program to encourage amateur security testers. Called Bugs Bounty, it offers cash to those who find weaknesses in security, and there already have been $1,000 winners. Expect even more winners, as a tradition has been established: cypherpunks not only write code, they crack codes. Good thing they do it for glory and not crime. But if they can do it, bad guys can too.
Phil and Bob have a chat In a matter of weeks, the back-to-back cracking episodes - ones that seemed destined to continue with the onset of electronic commerce - had appended a giant exclamation point to Morris's talk. Both of his cryptic tenets had been dramatized by crystal-clear examples. It was sort of a belated validation of Edgar Allan Poe's assertion. While in theory an unbreakable cipher is conceivable, you don't want to bet your life on its actual implementation. That's especially true when there exists a throbbing collaborative network of potential crackers - and, maybe, thieves and saboteurs. If this ad hoc effort could succeed, imagine how porous our current cryptosystems must seem to the folks at Fort Meade, whose resources are expansive and whose expertise is unquestioned.
(Page 9) This takes us back to Derek Atkins's original question regarding the safety of PGP, the software considered the choice of cryptorebels worldwide. Certainly in its current strength, it seems impervious to brute-force attacks. But can there be other flaws, perhaps already discovered by the NSA or others? As it turns out, the subject came up the night before Morris's speech at Crypto '95. The former NSA scientist was holding court at a round table at an evening reception. He had mentioned that he wouldn't mind meeting Phil Zimmermann, the author of PGP who had unleashed the program that some consider the antidote to a global epidemic of snooping. Someone flagged down the bespectacled 41-year-old Coloradan, the two were introduced and indicated mutual respect.
"Phil," said Morris, "let me ask you a question. Say that someone used PGP for very bad stuff. How much would it cost us to break it?"
Zimmermann seemed a bit flustered. "Well, I've been asked that before. It could be done."
"But how much would it cost us?"
Perhaps at that moment, the Morris Tenets, not yet delivered, hit Phil Zimmermann with full force. While Morris listened, quite poker-faced, Zimmermann explained that while he believed PGP would not be attacked by key size, the program could be vulnerable to other methods of attack, which he speculated on. Morris ultimately gave no indication whether the NSA has cracked PGP. We still don't know and the spooks aren't talking. Yet notice the question itself. It was not whether PGP could be cracked, but how hard it would be to crack. That was the lesson Morris subtly imparted in his speech the next day, a lesson that Poe would appreciate. But it took the cypherpunk cracking ring to bring that message to the world. In the process, they inadvertently helped usher in a new era of collective code breaking. The Net could begin to cobble together computer power that someday might rival the supercomputers holed up in Fort Meade. And while the Net's collective cognitive power lacks the code-breaking experience of the NSA's élite brain trust, it's significant in itself that smart people are attempting real-world cryptanalysis and are sharing the results. This effort is going to keep a lot of security specialists on their toes. And it's going to knock some others on their asses. Most important, by warning us that perfect safety is an illusion, these garage-band code breakers already have changed the nature of the crypto discussion. In a digital world increasingly dependent on strong encryption, maybe "pretty good" privacy is the best we can expect.