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鈥檚 no hope for anyone who might
want to break the code鈥檚 ciphers, even if they get hold of the key. Rabin鈥檚
trick is to use an electronic version of vanishing ink.
The people at the National Security Agency, the US government鈥檚 temple of
spies, aren鈥檛 going to like it one bit. For this isn鈥檛 some quantum code that
can only run on a quantum computer鈥攁n as yet only dreamed of machine. It
is something anyone, anywhere can use. And if Rabin鈥檚 machine works as well as
he believes it will, it could undermine the NSA鈥檚 efforts to track terrorist
activities. These days, maybe that鈥檚 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鈥檚, Rabin鈥檚 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鈥檛, they can鈥檛.
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鈥攖he 鈥渙ne-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鈥檚 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鈥攖he prime factors of that number, which only you know. Even
though everyone knows the public key, they can鈥檛 use it to eavesdrop without
first breaking it into factors, and that鈥檚 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. 鈥淩ight now, it鈥檚 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鈥檚 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鈥攖he 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鈥攈ow 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鈥檚 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鈥攕ay, the one their program made last Tuesday鈥攕he is using to
encode the message. The eavesdropper, Eve, is sunk. Without Alice and Bob鈥檚
program, she doesn鈥檛 know which bits to look for. So it鈥檚 a machine for
generating an endless one-time pad, with no reliance on couriers.
And it鈥檚 even better than that. Suppose Eve recorded the encrypted message,
and then later somehow get hold of the program鈥攂y breaking into Bob鈥檚
office, say. She still wouldn鈥檛 be able to decode the message because the data
stream that produced the key is long gone, lost in space. Lipton believes that
this 鈥渆verlasting security鈥� will be a big draw. 鈥淭hat鈥檚 a very interesting and
compelling kind of cryptography that we don鈥檛 currently have,鈥� he says.
It might be especially popular for corporations who want to conduct deals
with each other away from prying eyes. 鈥淓verlasting 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鈥檛
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鈥檛 enough.
鈥淭his 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鈥檚 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鈥攔equiring many kinds of receiver, for
example鈥攖hey 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鈥檚 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鈥檛
elaborate on any of the details. 鈥淚t鈥檚 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鈥檚 data from all the satellites would
cost many billion dollars to store. Far too much for any corporation鈥檚 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鈥檚 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. 鈥淚 didn鈥檛 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鈥攁nd he insists he can鈥攖he NSA won鈥檛 be best pleased.
鈥淲hat scares the NSA most is not simply unbreakable encryption, but
unbreakable encryption that鈥檚 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. 鈥淭he NSA鈥檚 nightmare is the
phone you buy at Radio Shack having strong encryption built in,鈥� Templeton
says.
The NSA already dislikes some of today鈥檚 encryption methods, and regularly
tries to force manufacturers to build in 鈥渂ack doors鈥� that government officials
can use to access encrypted material. But, so far, the people鈥檚 right to privacy
has been protected, even after the terrorist attacks on America. 鈥淭hey floated
another attempt to put legally required back doors in after September 11, but it
didn鈥檛 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 鈥渨ell 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. 鈥淲e beat the Feds fair and square,鈥� he says. 鈥淚t鈥檚 now
a dead issue. It does not matter how good anyone鈥檚 scheme is, the Feds have
completely given up.鈥�
But Rabin鈥檚 code may change things. Maybe the only reason government agencies
don鈥檛 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. 鈥淭he 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鈥檚 code, however, that鈥檚 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. 鈥淚 don鈥檛 know who they were, but their e-mail addresses ended
with .gov,鈥� he says. He duly sent the papers. 鈥淚 don鈥檛 know what they鈥檙e doing
with them, but I haven鈥檛 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鈥檚
not clear whether he鈥檚 right鈥攖he NSA is unwilling to talk about the
implications of Rabin鈥檚 ideas. In response to an e-mail asking whether it might
cause a problem it says: 鈥淭he NSA has no information to provide.鈥� So much for
open communications.