The ephemeral signals that flood the airwaves are the key to creating
an uncrackable code,says Michael Brooks
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
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.
'EVEN WHEN THE WOULD-BE CODE BREAKER
HAS A COMPUTER ENDOWED WITH SCIENCE-FICTION POWER, THE SYSTEM IS SECURE'
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 any case this is only a protection against unofficial snooper's. Governments
could simply use the courts to make someone divulge their key, or to take
a look at email 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
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.
'THE NATIONAL SECURITY AGENCY'S NIGHTMARE
IS THE PHONE YOU BUY AT RADIO SHACK HAVING STRONG ENCRYPTION BUILT
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 world-wide 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.
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.
|FAST, CHEAP RANDOM NUMBERS. The keys needed to
encrypt credit card transactions and other crucial
information floating in cyberspace often rely on an infusion of
random numbers. Generating true random numbers
is actually harder than it seems since the generation process generally follows
some deterministic algorithm, permitting the possible
reappearance of unwanted predictability. James Gleeson, a physicist at Kent
State University (330-672-9592, firstname.lastname@example.org) has come up with
a cheap, fast solution. He shoots laser light into a sample of
But because the sample is subject to a turbulent flow,
causing haphazard fluctuations in the orientation of the liquid crystals,
the digitized transmitted light coming from the sample represents a stream
of random numbers. Gleeson believes that because his device depends on standard
liquid-crystal-display technology, his compact device can be used for many
processes requiring random-number generation. (Applied Physics Letters, 9
September 2002.) The American Institute of Physics Bulletin of Physics News