[HaBi 1]    UNBREAKABLE CODE

UNBREAKABLE CODE By Roger Rapoport Were you the sort of kid who loved to fiddle with a secret-code ring? Do you send messages that you wouldn't want business competitors to intercept? Perhaps you cringe at the thought of a tax audit. If so, you're going to love this. For years now it's seemed that the Silicon Revolution would leave us all naked to the world. Anyone with enough nosiness, gall, and the price of a big computer can build an electronic data base that contains more information about us than we can remember ourselves. The insurance industry has done it. So have the credit bureaus. Some government agencies do little else. Now the computers that helped rob us of our privacy are giving it back-with interest. Two cryptographic geniuses have made the breakthrough that code builders have dreamed of for centuries: They've invented a practical code that can't be broken. Once you've coded your information, no one-not the CIA, not the NSA, not even the IRS--can figure it out unless you've told them how. With the right programming, most home computers could code and decode messages. But without the key, even IBM's biggest number crunchers could work far into the next century without unscrambling them. It's enough to make professional snoops weep. In fact, they've spoken out publicly against nongovernmental code research, interfered with patent applications, and even threatened university-based cryptographers with, prosecution under the State Department's International Traffic in Arms regulation. Now the Defense Department is seeking the power to review articles on cryptography and to ban publication of any that it considers too informative. This round in the battle between privacy freaks and code breakers got started when Martin Hellman, a thirty-three -year -old Stanford University professor of electrical engineering, linked up with another code junkie, Whitfield Diffie. Schooled in symbolic mathematical manipulations at MIT's Artificial Intelligence Laboratory, Diffie had left an industry job in California to search informally for the perfect code. After studying the classical literature, he camped his way across the country, visiting all the major centers of cryptographic research. Each night he examined the latest technical papers from university and corporate tabs by firelight. At IBM's Yorktown Heights, New York, lab, a scientist suggested that he look Hellman up back in California. "When I arrived in Palo Alto," Diffie recalls, "I called Hellman, and we each immediately found the other to be the most informed person in this field not governed by federal security regulations. " The problem they were trying to solve is lodged deep in modern code practices. Most coded messages these days are sent from one computer to another over telephone lines. For confirmation, they are also sent by courier. But that doesn't come cheap, and it often means delays when long distances are involved. A computer-wise thief who's wormed his way into a bank's message network can vanish with millions of dollars before anyone realizes that his orders to transfer the money weren't authorized. Worse yet for government cryptographers, there's always a chance that the courier will be intercepted or will defect with the message. Then there are the electronic eavesdroppers. The National Security Agency has computers tied into long-distance telephone links all over the world. The moment a phrase suggesting a topic that interests the agency appears in a conversation, the NSA's tape recorders kick in. Similar equipment monitors data-processing lines here and abroad. Anytime someone makes a call or sends a wire, the NSA can listen in. New equipment will soon enable the agency to read mail, even before it's sent, by catching and interpreting an electric typewriter's vibrations with remote sensing equipment. And virtually anything the NSA can record, the agency's computers can decode. Hellman and Diffie concluded that the major obstacle to secure transmission of data over teleprocessing networks lay in distributing the key, the instructions that tell the recipient how to decipher a message. "Traditionally," Hellman explains, "'keys have been moved by couriers or registered mail. But in an age of instant communications it was unrealistic for computer manufacturers to expect customers to wait days for the code to arrive. What was needed was a system immediately accessible to users who may never have had prior contact with each other." The idea of sending coded messages to total strangers seemed impractical at first. "In the past," Diffie says, "cryptography operated on a strongbox approach. The sender uses one key to lock up his message, and the recipient has a matching key that unlocks the meaning. As Hellman and I talked, we became intrigued by the idea of a system that used two different keys--one for enciphering and a second for deciphering. This method would operate like a twenty -four-hour bank teller. Any depositor can open the machine to put his money in, but only the bank has the combination to unlock the safe." For a long time now messages have been translated into high-security codes by converting the words into numbers and then scrambling the digits mathematically. What dawned on Hellman and Diffie was that a class of extraordinarily difficult mathematical problems, known as one-way functions, acted like their bank machine. A practical code could be built on them. Users would be able to list their encoding keys in a directory so that anyone could send them a coded message. Yet only they would have the decoding key. Eavesdroppers would have no hope of ever decoding the transmission. What made this practical was the work of Ralph Merkle, a young student at the University of California at Berkeley. Fascinated by the notion of a public-key system, he began working in one of his undergrad courses on a one-way function that could be applied to a code. Lying awake at night, he visualized a technique that would permit authorized users to decrypt messages that baffled eavesdroppers. "The idea," he says, "was for A to send B a message in a million pieces. One of those pieces would be tagged so that B could use it to find the decoding key. But anyone else would have to sort at random through all the pieces to find the right one. " Merkle's approach did not impress his instructor, who considered public-key distribution "impractical. " Unable to convince his Berkeley teacher of the system's promise, Merkle dropped his computer course. Then he wrote up his ideas for a computer journal. It rejected them as complete trash. "When I read the referees' criticisms," Merkle recalls, "I realized they didn't know what they were talking about. " In the summer of 1976 he finally found a sympathetic reception in the Stanford electrical department, and his work contributed to the breakthrough paper on the public-key system. Published that November, the article, called "New Directions in Cryptography," conceded that sending out a miHion pieces to foil spies searching for one that carried the key would be too expensive. Hellman and Diffie remedied this problem by letting each user place his encryption key in a public rile, at the same time keeping the decoding procedure a secret. Since then Ronald Rivest, an MIT computer science professor, and his colleagues Adi Shamir and Len Adleman have made the code breaker's job even more difficult by using a new set of one-way functions. Their method builds encoding keys out of the product of two large prime numbers - numbers that can be divided only by themselves and by 1. This generates a figure hundreds of digits long. In order to find the decoding key, it is necessary to "factor" this giant figure, break it down into the original numbers. It can't be done. Not even the largest computers can factor the product of two numbers with more than 50 digits. Only the recipient who knows the prime numbers used to build his encoding key can retrieve the message. The public-key system also solves the other problem in sending coded messages: How do you know the signal does not come from an impostor? The Stanford and MIT teams have both produced a forgery-proof digital signature. The encoding and decoding keys, though complex, are really just mathematical instructions that reverse each other. If the code were built on a simple arithmetic problem instead of on a one-way function, they might say something like "multiply by five" or "divide by five." The procedure can be used in either direction. So to sign a coded message, you just reverse the process. Encode your name with the secret key you ordinarily use to decode messages. The recipient then looks up your public encoding key in the directory and uses it to decode the signature. Since no one but you could have used the secret key, the recipient can be sure it was you who sent the message. And since the keys are based on a one-way function, the recipient still can't find your secret key. This makes it possible to sign contracts over a computer network. If the sender tries to renege on the deal, the recipient need only produce a copy of the digital signature to back up his claim in court. When the first public-key ciphers were announced, they dropped like bombs into the middle of a running battle. Six years ago the National Bureau of Standards decided to help out the banks, insurance companies, and others that were desperate for a way to keep their proprietary information secret. The NBS invited computer experts to develop a "data encryption standard [DES] algorithm" for computers. (An algorithm is the set of instructions by which you use the key to turn plain text into code and then decode it again.) And they invited the spooks from the NSA to evaluate the ideas. The NSA, of course, couldn't be expected to have much interest in codes that it could not break, and a good many critics complained that letting the NSA work on the DES was like putting the fox on sentry duty around the hen house. Their uneasiness grew when the NSA persuaded IBM, which developed the winning algorithm, to withhold the working papers used to develop it. The NSA insisted that this was only a security precaution in the best interests of all users, but it looked to many as if the government was simply trying to lock up the algorithm's mathematical roots. When computer scientists tried to publish papers suggesting that the new DES was breakable, the NSA tried to classify their work. One of the agency's employees, a man who once proposed to keep tabs on the 20 million Americans with criminal records by wiring them with transponders, even attacked the critics' patriotism in an engineering journal. The NSA finally agreed to meet with dissenters, then promptly destroyed all tapes of the confrontation. Inventors working on cryptographic devices found their patent applications classified and were threatened with prosecution for even discussing the equipment. The NSA claimed it would take 91 years of computer work to break the DES key. According to Stanford's Hellman, however, "DES could be broken by an enemy willing to spend twenty million dollars on a computer that could test all the possible keys in less than a day." The DES key is a string of O's and I's, known as bits. It is 56 bits long. All you'd have to do to make it unbreakable would be to switch to a key with 128 or more bits. Since it wouldn't make the DES device much more expensive, why was the government being so stubborn? "It occurred to us," Hellman says, "that the NSA wanted an algorithm that it could crack. That would prevent anyone else in the country from using a foolproof code." With that controversy to prepare their way, the public-key codes have received a warm welcome from just about everyone but the government. Some New York banks have already decided to reject the NSA-backed 56-bit encryption standard. An officer at Banker's Trust Company said his company refused to go along with the federal plan because it "did not meet all the bank's requirements." Bell Telephone has also rejected DES on security grounds. These corporations may be better served by private companies now hoping to market coding devices based on the systems MIT and Stanford inventors are trying to patent. "Since we would share some of the royalties," Hellmann says, "some government people suggest our opposition to DES is motivated by self-interest. Sure, we would benefit if public-key systems go into widespread use. But the facts are that our method provides real protection and DES can be broken." Rivest is already consulting for companies that hope to market foolproof systems. "What we want," he says, "is to develop an add -on encoding device for computer terminals that any user could afford. We're building a prototype now and working to see that it ends up in the marketplace." Bell Northern Labs, a subsidiary of the Canadian phone company, has hired Diffie to help make electronic eavesdropping more difficult. At the company's Palo Alto research facility, he is leading a cryptographic research group that wants to show callers how they can mask their identity. Some computer experts, such as George Feeney, who invented the concept of EDP time sharing and who heads Dun and Bradstreet's advanced-technology group, voice concern about the practicality of these promised systems. "The unbreakable code is a brilliant piece of conceptual work," Feeney says. "These inventors have done an incredible job. But some of us wonder whether the process may turn out to be beyond the current state of the computer art. We still don't know how long it's going to take to get this dream going and whether the cost will be realistic. " The NSA, though, has already begun to whine about the prospects of companies and private individuals communicating over foolproof lines. The agency's director, Vice Admiral Bobbie Ray Inman, is so anxious that he recently broke official policy to go on record about this sensitive matter. "There is a very real and critical danger that unrestrained public discussion of cryptologic matters will seriously damage the ability of this government to conduct signals intelligence and protect national security information from hostile exploitation," he complained. "The very real concerns we at NSA have about the impact of nongovernmental cryptologic activity cannot and should not be ignored. Ultimately these concerns are of vital interest to every citizen of the United States, since they bear vitally on our national defense and the successful conduct of our foreign policy." Another NSA employee, Joseph A. Meyer, has warned his colleagues in the Institute of Electrical and Electronic Engineers that their work on publickey cryptography and data encryption might violate the International Traffic in Arms regulation. This law, which the government uses to control the export of weaponry and computer equipment, can even be invoked to thwart basic code research. As a result, people like University of Wisconsin computer-science professor George DaVida, who recently tried to patent a new cryptographic device, have run into trouble. Although his work was sponsored by the federally funded National Science Foundation, the Commerce Department told DaVida that he could be arrested for writing about, or discussing, the principles of his invention. A similar secrecy order was issued to a Seattle team that had invested $33,000 to develop a coding device for CB and marine radios. Protests from the scientific community persuaded the government to lift its secrecy orders in both these cases. At least for now, academics and inventors can continue to write and confer on cryptographic schemes. But the threat of renewed government harassment has complicated further research. Universities have agreed to defend professors against federal prosecution related to code research, but they can't protect students. As a result, some students have decided not to contribute papers to scientific conferences. In at least one instance Hellman had to shield two of his graduate students at Stanford by reading their reports for them at a meeting of the Institute of Electrical and Electronic Engineers. It's too soon to know whether the government will move to block the use of the public key, but Hellman and his colleagues fear that young cryptographers may be scared away by Inman's tough admonitions. This could hold up the practical refinements necessary to make the unbreakable code widely available. A real chance to stop crime in the electronic society might be postponed indefinitely. With computerized theft increasing every year and computers controlling more of society's daily activities, this doesn't seem wise. But this issue appears secondary to Washington cryptographers, who sound as if they would like to reserve the public key for their own use. "I'm not suggesting government agents want to listen in at will," Diffie says, "but I'm sure they don't want to be shut out. For them the perfect code is the one only they can break."

[HaBi 1]    UNBREAKABLE CODE