Cracking the Code By: Mark D. Uehling Last April, detectives in San Diego stunbled upon a national network of about 1,000 computer hackers who had breached more than the conventional password- related defenses of banks and credit card companies. In the months after the first arrests in California, police caught ringleaders in New York, Florida, Arizona, Pennslyvania, Washington, and Ohio. Among other financial data, the hackers had illegally divined the personal identification numbers used in automated teller machines. These numbers are encrypted with a special federally approved scarambling formual intended to protect the customers of every bank. But the hackers were able to thwart that encryption. They even used other scrambling techniques to hide their own records from police. "The hackers have their own encryption system that is probably better than any at IBM," says Dennis Sadler, the San Diego detective in charge of the case. Banking identification numbers depend on the sort of scrambling code used to generate the gibberish displayed on Robert Redford's computer screen in the movie Sneakers. This code can garble any form of information--words or numbers-- stored as computer data. It can prevent eavesdropping on telephone conversations, keep facsimiles out of the wrong hands, and safeguard radio broadcasts. Crop reports at the U.S. Department of Agriculture are encrypted with it. So are Nintendo cartridges and money (most funds move from one bank to another via computers, not armored cars). The original name of the devilishly versatile code was Lucifer. At IBM, where the formula was devised early in the 1970's, executives despaired of profiting from Lucifer and released it to the public domain. The U.S. government, which has long collaborated with IBM, tinkered with the code and renamed it the Data Encryption Standard, or DES. Aware of the many illicit uses to which sensitive government information could be put, Congress mandated DES encoding for federal computer files. It was adopted as a national standard in 1977. With government approval, DES gained wide public use first in banking and more recently in personal computers and facsimile machines. Fortunately, considering the stakes, most cryptographers have complete faith in the code, believing it will never be cracked. To the credit of IBM and its allies in the intelligence agencies, a generation of mathematicians have spent their careers trying to break DES without success. While other codes fell to one mathematical attack or another, DES remained invulnerable, invincible, uncrackable. Now, however, that impressive record seems destined to end. The speed of integrated circuits has grown at a fantastic rate, and it is not impossible to envision a day when supercomputers will be powerful enough to search all possible passwords for the key to a DES message. "All cryptography has a natural life span, and advances in technology will reduce the security provided by DES in the future," concedes Michael S. Conn, chief of information policy at the National Security Agency (NSA), a Pentagon division devoted to electronic espionage. The federal government recognized the vulnerabilities of DES in 1988, when the NSA decertified DES for classified purposes within the government. For the customarily silent espionage establishment, that was a shotgun blast alerting the computer industry that DES was no longer wholly reliable. By then, however, American banks had adopted DES so completely that some form of federal approval was demanded by the business community. The Commerce Department obliged, reapproving DES. However, Commerce's reputation for world-class code-making is weaker than that of the NSA, which has more cryptographic brain power than any university in the world. One possible reason why the NSA souded the alarm about DES is because the code is so well known. As Conn of the NSA explains: "Government use of DES equipment has spread to applications making [DES] increasingly attractive as a potential target for adversaries of the U.S. government." Indeed, unlike the classified cryptography used for top-secret military plans and the Oval Office telephone, DES is an open book. Its workings have been described in official U.S. government publications and countless technical articles. In basic DES procedure, a letter or document is converted into numbers. These numbers are then replaced and reordered using numbers selected from a key--a password-like number chosen by the person encrypting the message. The substitution and reordering occur gradually so that the message and the key are thoroughly mixed. The resulting number is then scrambled again and again, for a total of 16 rounds of manipulation. By the end, a phrase such as "Cancel Plan B!" becomes 3102 5896 4807 1192 5046 1891 0288. The numbers can only be converted back into "Cancel Plan B!" if they are put through the same scrambling operation in reverse order, using the same key. A DES key is 56 binary digits long. In the world of computers, each digit can be either a one or a zero, so the number of possible keys that can be used is two raised to the 56th power. That works out to 72,057,594,037,927,936 different ways to encode a message with DES. Cryptographers haggle over how much time is needed to plow through these 72 quadrillion passwords. Some say a month; others believe it could be done in a few hours on a supercomputer dedicated to the task. "There must be thousands of computers that could succeed with a brute force approach,"muses David Stang, research director of the National Computer Security Association. "A desktop computer you can buy for $20,000--maybe it sits on the floor by your desk--is certainly as powerful as anything the National Security Agency owned a decade ago when the standard was first discussed. And a desktop computer could succeed in some cases." Thanks to faster silicon chips, parallel processing, and ever-better supercomputers ["The Teraflops Race," March '92], even those with faith in DES agree that some day soon DES keys will be searched and tested with ease. What's more, 16 rounds of substituting and reordering may not be enough to protect a message from prying eyes. In 1974, when DES was first publised in the Federal Register, 16 rounds seemed more than sufficient. But as many cryptographers have shown, sometimes informally at conferences, they can track messages through three-quarters of those rounds before getting lost in the maze of numbers. "There are theories that you can break a 12-round data encryption scheme without a tremendous amount of trouble," says Gary S. Morris, a Pentagon consultant on information security. It was against this backdrop that a gifted but self-promoting mathematician named Adi Shamir stepped forward in the fall of 1991 to announce he had discovered a "weakness" in DES. Shamir, a professor at Israel's Weizmann Institute of Science, distributed his tantalizing comments over an international computer network. In the close-knit world of cryptography, the announcement was big news; today the presence of Shamir's finding is about as widely known as DES itself. Collaborating with graduate student Eli Biham, Shamir developed a technique called "differential cryptanalysis." The technique currently has little practical application in breaking DES, but it outlines a method for discovering a DES key without trying all of the 72 quadrillion possibities. In essence, Shamir claims that once he is given enough messages encrypted with the same DES key, he can detect a pattern that will allow him to decipher other messages. "Computers are hundreds or thousands of times more powerful than they were when DES was first developed," says Nathan Myhrvold, vice president for advanced technology at Microsoft Corp. "Shamir's work makes it potentially feasible to break DES without brute force. DES doesn't afford the same measure of security [as it once did]." For now, though, DES appears to be safe from Shamir's attack. Although his technique is a shortcut that makes it unnecessary to test 72 quadrillion passwords, there's a hitch: To identify a DES key, Shamir must first obtain several trillion messages encrypted with that key, as well as the original texts. That requirement makes it exceedingly difficult for im to crack the code. A top IBM research scientist, Don Coppersmith, who worked on DES in its early days says the company anticipated Shamir's analysis more than 15 years ago, in the mid 1970's. According to Coppersmith, the DES formula is strong enough to withstand the attack. Shamir's technique won't work, Coppersmith maintains, unless a code-cracker can either persuade his enemy to encrypt an unimaginable quantity of data, or commandeer his enemy's computer. If Joe Q. Hacker wanted to identify a DES key used by the First National Bank in Chicago, he would have to take control of the bank's computers for months or years. On a theoretical level, Coppersmith syas, the IBM team anticipated a hacker who might try to break DES by analyzing differences in the enciphered versions of two similar messages. To do so, the hacker would need to detect a faint pattern of differences after each of the 16 rounds of encryption. By finding that pattern, in theory, a hacker might be able to identify part of the DES key-- and quickly calculate the rest. However, says Coppersmith, "the probability of finding any one of these patterns is enormously small." At best, he says it's one in one quadrillion. Discerning the pattern through trial and error would require an astronomical number of calculations, as Shamir himself admits. A code-cracker simply wouldn't have time to perform the calculations on the targeted computer. No matter how the scientific community assesses the Shamir attack, there are two other problems with DES that have spurred the search for a new standardized code. The biggest obstable to using DES is that the sender and the recipient of an encrypted message must somehow share the key. Mentioning it on the telephone is unwise; a novice detective could intercept the key with inexpensive gear from Radio Shack. Mail services can be subverted with equal ease. Large companies have been reduced to using trusted couriers; some departments in the U.S. and Canadian government have spent millions of dollars a year using such messengers. However, couriers are out of the question for a sender and a recipient who have never met: The recipient has no way of ascertaining whether the DES key and message are genuine. Worse, many cryptographers in academia and industry have long suspected that the government can already break the widely used DES code. Its motive: to intercept the communications of foreign governments, terrorists, or the Mafia. The government has long denied this ability exists, as does IBM. But the NSA's expertise in cryptography is so esteemed, so revered, that many cryptographers assume the government can devote a supercomputer or a battalion of analysts to cracking an important DES key. "Undoubtedly the U.S. government knows how to break DES," says Harold J. Hyland, editor emeritus of the journal Computer Security and a former intelligence officer. "The people capable of breaking it could never publish it. They work for the government or in academia. If you did find a way to break it, you'd find it very hard to get funding." Many in the field share Hyland's view and cite the government's role in the birth of DES--when, at the NSA's request, IBM shortened the original key. That made DES easier to break. The skepticism over DES intensified when the Commerce Department's National Institute of Standards and TEchnology (NIST), guided by the NSA, proposed a new standard in 1991--a so-called digital signature--for verifying and authenticating any electronic document. Shortly after the government proposed its method, a pair of mathematicians at Bellcore, the research arm of the regional Bell telephone companies, announced several shortcomings. The bottom line: Under the new proposal, the government might be able to forge any signature or read any document. "Their proposal had a number of things wrong with it," says Bellcore mathematician Stuart Haber. Speaking of a hypothetical bureaucrat, he adds: "If he does a very simple bit of arithmetic, he can check whether his guess is correct. He gets the message and he gets your key from then on. You don't need very sophisticated techniques to mount this attack." The government has not responded to the Bellcore objections, adding to speculation about Orwellian intentions. Given concerns about DES and the government's motives, the computer industry is trying to agree on a new standard without the official backing of the government. The system eliciting the most interest is a method of encryption that does not depend upon easily intercepted exchange of a password. Many of the largest computer hardware and software companies have already licensed the RSA Public Key Cryptosystem, which can be used in concert with DES. RSA is named after its inventors--Ronald L. RIvest, a computer scientist at the Massachusetts Institute of Technology (MIT);Shamir; and Leonard M. Adleman, a mathematics professor at the University of Southern California who recently served as a consultant for Sneakers. All three were professors at MIT when they devised the system in 1977. The university licensed the patent to them in 1982, and they formed RSA Data Security in Redwood City, Calif., to market the technology. TWO KEYS ARE BETTER THAN ONE Instead of a single key that must be shared between users, the RSA system has a matched pair of keys. One key is private, and the other is public. The public key is published in a directory, allowing people who have never met to send messages to each other. The public and private keys perform inverse functions: What one does, the other can undo. Under the RSA protocol, as with DES, a document is first converted into numbers. Using the public key, these numbers are rased to frighteningly high exponential powers and divided by the product--at least 150 digits long--of two prime numbers. The remainder of the fraction is the encrypted bit of information. Only someone with the private key, which contains the two prime numbers, can compute the remainder and decode the message. The system relies on the difficulty of factoring a large number back to two prime numbers--numbers that can be dvided evenly only by the number 1 and themselves (3,5,7,11, and so on). It is easy to multiply two large prime numbers together, but hard to factor their product back to its two components. In October 1988, for example, it took an international group of computer scientists nearly a month to factor a 100-digit number. More than 400 computers worked on the problem during idle hours to find the number's two factors--one 41 digits long, the other 60 digits long. In June 1990, another team factored a 155-digit number. The number was handpicked to make the task easier, but it still took 275 years' worth of computer time. To keep pace with ever-faster computers, RSA's inventors can simply add more digits to the system's keys. RSA and DES are not competitors. In fact, RSA could help prevent DES from becoming obsolete. Because it takes a long time to encrypt an entire message with RSA, the system is typically used to encrypt a DES key. That key is then used to encrypt the rest of the message. "RSA lets you use a different DES key for every message," explains James Bidzos, president of RSA Data Security. A NEW GOVERNMENT STANDARD? In the coming months, NIST will decide whether DES will remain as the standard encryption method used by the federal agencies. Because the new "digital signature" standard proposed by NIST is under fire, the Commerce Department's computer security advisory board has recommended that the standards institute delay its decisions until June of this year. The computer industry would like NIST to adopt the RSA technology, but that isn't likely to happen. One reason: If the privately developed technology becomes a standard, the government will have to pay royalties for its use. And perhaps more important, the NSA does not want the government to back the RSA encryption system. The agency has already conducted private negotiations with the Software Publishers Association, which represents computer software makers, regarding the export of programs containing encryption features. "[The NSA] dislikes our system because it's too hard to break," says Bidzos. "They clearly don't like what we do, but we're succeeding in spite of that." The power of RSA's approach has already spread, through unknown channels, to foreign enemies. Iraqi generals are believed to have used RSA encryption during the Persian Gulf war, and the technology is indisputably on the move throughout the world. Perhaps the only good news is that American generals had the same RSA technology in their laptop computers. This article appeared in the January 1993 Popular Science, Vol 242, No. 1. It was on pages 71-74,84. Cobra read any document. "Their proposal had a number of things wrong with it,