News Release

Secret code machine

Reports and Proceedings

New Scientist

MICHAEL RABIN might be in for trouble. A Harvard professor of computer science, he is building a secret code machine, an Enigma for the 21st century. But this is better than Enigma. This time, there's no hope for anyone who might want to break the code's ciphers, even if they get hold of the key. Rabin's trick is to use an electronic version of vanishing ink.

The people at the National Security Agency, the US government's temple of spies, aren't going to like it one bit. For this isn't some quantum code that can only run on a quantum computer-an as yet only dreamed of machine. It is something anyone, anywhere can use. And if Rabin's machine works as well as he believes it will, it could undermine the NSA's efforts to track terrorist activities. These days, maybe that's something a wise man should think twice about.

But the rewards are clear. For people whose concern is to maintain their own privacy, rather than invading someone else's, Rabin's scheme could be the ultimate cloak of secrecy.

It sidesteps a common flaw of other codes. All encryption schemes mix up your message into an unreadable mess using some kind of secret key known only by the sender and the receiver. In many schemes, the key is a string of random binary 0s and 1s that is added to the message to make it seem like gibberish. Then if an eavesdropper knows what the key is, they can subtract it to extract the message. If they don't, they can't.

Trouble is, if you use the same key for too long, eavesdroppers can analyse the coded messages and use statistical techniques to break the cipher. One remedy is to use the key only briefly then destroy it, and have a pad of many keys to be used only once-the "one-time pad". This makes it mathematically impossible for an eavesdropper, even someone with unlimited computing power, to work out the message.

That leaves you with the problem of how to keep the key out of enemy hands. The US president communicates with his Russian counterpart via a one-time pad system, using a network of trusted go-betweens to ferry the code books that contain the pads. But this is impractical for most people, and is always open to abuse from defecting agents.

A cunning way around this is public key cryptography. The kind that protects much of the world's e-commerce, for example, is called RSA, a scheme based on the difficulty of factorising large numbers. You broadcast a huge number, which is used as the key to encrypt the message. It can only be decrypted using a private key-the prime factors of that number, which only you know. Even though everyone knows the public key, they can't use it to eavesdrop without first breaking it into factors, and that's tremendously difficult.

Difficult, that is, using known mathematical techniques. What keeps e-commerce experts awake at night is the fear that someone might discover a new technique that does the job with ease. "Right now, it's perfectly possible that some smart kids down the street could figure out a way to break RSA," says Richard Lipton, a computer scientist at Georgia Institute of Technology in Atlanta.

In any case this is only a protection against unofficial snoopers. Governments could simply use the courts to make someone divulge their key, or to take a look at e-mail archives or old financial transactions. Civil liberties groups are already concerned at the measures that governments have rushed into law, with the avowed aim of tackle terrorism or organised crime, which could also be used to search and store our communications for future reference.

Rabin's scheme would change all that. Your secrets would be safe forever. And the strangest thing of all is that this acme of secrecy relies on data that anyone can tap into-the flood of digital information continuously being transmitted from TV broadcast satellites and mobile phone masts and a host of other sources. All of it is public. Given the right equipment anyone can pick up that raw digital signal and record it. And if you can pick it up, you can use it to create a key to an unbreakable code.

It works like this. The two conspirators, Alice and Bob, first have to establish a set of secret rules for picking random bits from the data. This is a potential weakness in the scheme-how do they share these rules securely? But it would only involve one meeting, say, rather than the repeated ferrying of one-time pads.

They might share a computer program that taps into the world's data stream, pulling out a certain bit from the Sky TV satellite at 12 noon precisely, a bit from the Microsoft home page half a second later, a bit from the Dow Jones index after that, and so on. The program assembles these bits into a key.

Whenever they want to communicate, Alice just tells Bob over the phone which key-say, the one their program made last Tuesday-she is using to encode the message. The eavesdropper, Eve, is sunk. Without Alice and Bob's program, she doesn't know which bits to look for. So it's a machine for generating an endless one-time pad, with no reliance on couriers.

And it's even better than that. Suppose Eve recorded the encrypted message, and then later somehow get hold of the program-by breaking into Bob's office, say. She still wouldn't be able to decode the message because the data stream that produced the key is long gone, lost in space. Lipton believes that this "everlasting security" will be a big draw. "That's a very interesting and compelling kind of cryptography that we don't currently have," he says.

It might be especially popular for corporations who want to conduct deals with each other away from prying eyes. "Everlasting security is very important here," Rabin says. The partners in a merger may want to ensure that the encrypted messages they exchanged about tactics and business strategies remain secret for a decade.

The only way to crack the code is if Eve can record the information on which Alice and Bob base their key. And she has to record almost all of it. In 1990, Ueli Maurer, a cryptography researcher at the Swiss Federal Institute of Technology in Zurich, worked out that an eavesdropper who can store up to 50 per cent of the whole data stream, and therefore snare about half of the key, can't break the code even with unlimited computing power at her disposal to make guesses about the rest of the key. Rabin has taken this further and shown that even 90 per cent isn't enough.

"This stuff is terrific," says Lipton. Even when the would-be code breaker has a computer endowed with science-fiction power, the system is secure. The only way to decode the message is to have the key in advance, or to have stored almost every 0 and 1 that's transmitted anywhere in the world.

The next question is what data to use for the key. Public data streams from satellite broadcasts, Internet activity and the like would be one option, but because they are so diverse-requiring many kinds of receiver, for example-they would be cumbersome to use. So Rabin is now working on a project to design a purpose-built system. He has teamed up with Harvard electrical engineer Woody Yang to build a beacon to transmit a stream of random bits from a satellite.

Eventually, Rabin hopes to establish a fleet of satellites that will broadcast packages of random bits at a rate that defeats anyone's storage capabilities. Instead of monitoring optical fibres, phone masts and Internet pages, users would be able to generate their keys to the vanishing code from a single source of data, making the system a worldwide resource. Rabin won't elaborate on any of the details. "It's a work in progress that I cannot discuss," he says.

Establishing this infrastructure is going to take some serious money. Rabin is aiming for 45,000 gigabits per second of random data, transmitted by a fleet of 48 low-orbit satellites. The reason for this extravagance is to drive up the costs of storing the data. Each bit will cost around 500 times more to store than transmit, Rabin believes, so a year's data from all the satellites would cost many billion dollars to store. Far too much for any corporation's espionage budget, and probably even for the NSA.

Rabin envisages a network of corporations sharing the setup cost for the advantage of being able to conduct their business securely. Smaller companies or even individuals would then be able to buy into the network once it has been built.

Unbreakable

Not everyone is convinced that Rabin's scheme is a practical business proposition, as there are other cryptographic techniques that work well enough for everyone except the most paranoid. Maurer certainly never bothered to patent his contribution. "I didn't think this would ever be used," he says. But one thing is certain: if Rabin can turn his idea into a practical, unbreakable code machine-and he insists he can-the NSA won't be best pleased.

"What scares the NSA most is not simply unbreakable encryption, but unbreakable encryption that's easy to use," says Brad Templeton of the Electronic Frontier Foundation, a group that seeks to protect civil liberties in digital media. The NSA already encourages people to use weak encryption that it can break, such as the Data Encryption Standard. It also tries to control the availability of the best encryption technologies. "The NSA's nightmare is the phone you buy at Radio Shack having strong encryption built in," Templeton says.

The NSA already dislikes some of today's encryption methods, and regularly tries to force manufacturers to build in "back doors" that government officials can use to access encrypted material. But, so far, the people's right to privacy has been protected, even after the terrorist attacks on America. "They floated another attempt to put legally required back doors in after September 11, but it didn't get far," Templeton says.

Phil Zimmerman, creator of the Pretty Good Privacy encryption software, did some soul searching in the wake of the 11 September terrorist attacks. But he remains convinced that his PGP scheme does much more good than harm: it is used to defend human rights around the world, and possible use by terrorists is a price worth paying, he believes. Efforts by politicians to impose new regulations on the use of strong cryptography are "well intentioned but misguided", he says.

Zimmerman was at the centre of legal battles with US government agencies, notably the FBI, through the 1990s over the availability and strength of cryptographic software. At the core of the debate was whether terrorists would use strong cryptography. "We beat the Feds fair and square," he says. "It's now a dead issue. It does not matter how good anyone's scheme is, the Feds have completely given up."

But Rabin's code may change things. Maybe the only reason government agencies don't fight current cryptography harder is that they can always apply to the courts for the right to obtain the key. Having got it, they can then go back through the communications archives. "The one reason they tolerate public key cryptography and the like is that they know they can at least get the public key," Lipton says.

With the everlasting security of Rabin's code, however, that's not an option. So what are the NSA to do? Ignore the risk? Or lean on Rabin to desist from his secret work?

Rabin has had e-mail from government employees asking for copies of his research papers. "I don't know who they were, but their e-mail addresses ended with .gov," he says. He duly sent the papers. "I don't know what they're doing with them, but I haven't heard back."

But he rejects the idea that he and his scheme pose any threat to national security, or that he should seek official permission to build his machine. It's not clear whether he's right-the NSA is unwilling to talk about the implications of Rabin's ideas. In response to an e-mail asking whether it might cause a problem it says: "The NSA has no information to provide." So much for open communications.

###

Author: Michael Brooks

New Scientist issue: 5th January 2002

PLEASE MENTION NEW SCIENTIST AS THE SOURCE OF THIS STORY AND, IF PUBLISHING ONLINE, PLEASE CARRY A HYPERLINK TO: http://www.newscientist.com


Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of news releases posted to EurekAlert! by contributing institutions or for the use of any information through the EurekAlert system.