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.
Advertisement
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.