The Key Vanishes: Scientist Outlines Unbreakable Code

[InfoSec News <isn () C4I ORG>]

Forwarded by: Gary Stock <gstock () net-link net>

http://www.nytimes.com/2001/02/20/science/20CODE.html

February 20, 2001
By GINA KOLATA

A computer science professor at Harvard says he has found a way to
send coded messages that cannot be deciphered, even by an all-powerful
adversary with unlimited computing power. And, he says, he can prove
it.

If he is right, and he does have some supporters, his code may be the
first that is both practical and provably secure. While there are
commercially available coding systems that seem very hard to break, no
one can prove that they cannot be cracked, mathematicians say.

In essence, the researcher, Dr. Michael Rabin and his Ph.D. student
Yan Zong Bing, have discovered a way to make a code based on a key
that vanishes even as it is used. While they are not the first to have
thought of such an idea, Dr. Rabin says that never before has anyone
been able to make it both workable and to prove mathematically that
the code cannot be broken.

"This is the first provably unbreakable code that is really
efficient," Dr. Rabin said. "We have proved that the adversary is
helpless."

Dr. Richard Lipton, a computer science professor at Princeton, who is
visiting this year at the Georgia Institute of Technology, said, "It's
like in the old `Mission Impossible,' where the message blows up and
disappears."

Someone who uses one of today's commercially available coding systems,
Dr. Lipton explained, uses the same key - mathematical formulas for
encoding and decoding - over and over. Eventually, they may be forced,
perhaps by a court order, to give up the key. Or the key may be
stolen. But with Dr. Rabin's system, the message stays secret forever
because the code uses a stream of random numbers that are plugged into
the key for encoding and decoding. The numbers are never stored in a
computer's memory, so they essentially vanish as the message is being
encrypted and decrypted.

"If someone walks into my office with a court order or if they put a
gun to my head they still could not read my conversations," Dr. Lipton
said.

In a sense, say some mathematicians and computer scientists, Dr. Rabin
may have solved the ultimate problem in cryptography, one that has
driven research for centuries: finding a provably unbreakable code
that is also practical. But, they say, the paradox is that the
discovery has come at a time of vigorous debate over whether such a
code will make much difference in keeping communications private.

Some say that a provably unbreakable code could have profound effects,
keeping secret messages secret forever. But others say that codes
today are already so good that there is little to be gained by making
them provably, rather than just probably, unbreakable.

For now, Dr. Rabin's idea is simply a scheme backed up by a
mathematical proof that he has been presenting to scientists at
seminars. No company is lurking in the background to sell it, and Dr.
Rabin says he has no commercial interests in it.

"I never commercialize anything," Dr. Rabin said. "I am not in that
business." Instead, he said, he did the work because it was a
challenge.

Dr. Rabin's idea is simplicity itself, at least in the world of
encryption. Previous coding methods rely for their security on the
limitations of computing power. They assume that if breaking a code
requires enough calculations, even the best computers will not be able
to do it.

But, Dr. Rabin said, there is no proof that such codes are secure.
Their security hinges on the belief that no one will find a shortcut
to doing the calculations. It is always possible that such a shortcut
exists, waiting to be discovered by a clever mathematician.

Dr. Rabin relies instead on the limits of memory banks in computers.
No matter how powerful a computer is, no computer can store an
unlimited amount of data. And yet that is what is required for an
eavesdropper to break his code.

The coding starts with a continuously generated string of random
numbers, say from a satellite put up to broadcast them or from some
other source. The numbers can be coming by at an enormous speed - 10
million million per second, for example.

The sender of a message and its recipient agree to start plucking a
sequence of numbers from that string. They may agree, for example, to
send a message, encoded with any of today's publicly available
encryption systems saying "start" and giving instructions on capturing
certain of the random numbers. As they capture the numbers, the sender
uses them to encode a message, and the recipient uses the numbers to
decode it.

An eavesdropper can know the mathematical formula used to encode and
decode, but without knowing the exact sequence of random numbers that
were used in the formula to send a particular message, the
eavesdropper cannot decode the message. And the only way to have that
sequence is to just happen to be storing numbers from the unending
stream at exactly the right moment.

If the eavesdropper, for example, had a secret way to decode the
message saying "start" and it took a minute to do the calculation
needed to decode it, it would be too late by the time the eavesdropper
got going. The sender and recipient would already have their string of
numbers and that string of numbers, once broadcast, could never be
retrieved. It would be infeasible to store the endless string of
numbers in any computer and so they are essentially gone forever.

Often, Dr. Rabin said, eavesdroppers will capture and store encoded
messages hoping to decode them at later, either when computers have
improved - making it easier to do the calculations to break a code -
or when the method for encoding and decoding is known, perhaps because
it has been stolen. But, he said, messages encoded with his system can
never be broken by these means because the random numbers used in
encoding and decoding are used once and are never stored.

"That is why I call it `everlasting security,' " he said.

Dr. Richard DeMillo, chief technology officer at Hewlett-Packard, said
that what interested him about the scheme was that it "reshuffles the
policy deck."

"Normally," he explained, "agencies put the burden of wiretapping on
the carrier." A telephone company, for example, would have to allow an
agency like the Federal Bureau of Investigation to listen in on coded
material. But with this system, the agency would still have the burden
of trying to capture the appropriate stream of random numbers, a task
that would be technologically infeasible.

Dr. Lipton also said the scheme could thwart law enforcement agencies.

"If I'm saying to you, `Buy 1,000 shares of I.B.M., I'm sure it's
going to go up,' " he said, "and if that was an insider trading
situation, five years from now the F.B.I. could go after you."

If the agency had the encrypted message in hand, it could demand the
key to read it, he said. But, Dr. Lipton said, if the random numbers
used to encode were used once and never stored, the agency would be
hamstrung. "It changes the ground rules," he said.

Dr. Lipton added that, as a computer scientist, he appreciated the
proof that the code could not be broken. "Michael's big contribution
has been the proof that the system actually works," he said. "It's one
of those things that sounds obvious but the mathematics is quite
hard."

Of course, what is good for those who want privacy may not be good for
law enforcement. Even the cryptography systems sold today are a
problem for the F.B.I. "Uncrackable encryption allows drug lords,
terrorists and even violent gangs to communicate about their criminal
intentions without fear of outside intrusion," the F.B.I. director,
Louis J. Freeh, told the Senate in 1998, according to a transcript
from the Federal Document Clearing House. "This type of encryption
also allows these same people to maintain electronically stored
evidence of their crimes beyond the reach of law enforcement."

Still, some computer experts said that while it might be interesting
in theory to have a provably unbreakable code, the practical
importance of Dr. Rabin's code may be minimal.

Some, like Dr. Dorothy Denning, a computer science professor at
Georgetown, and Dr. Cipher Deavours, a professor of computer science
and mathematics at Kean University in Union, N.J., said the code was
simply impractical for large messages. The larger the message, the
longer the string of random numbers needed to encode it, and the more
difficult it would be to send.

"It's a cute idea, but it's simply unmanageable," Dr. Deavours said.

Others, like Dr. Lipton, disagreed. "I think it is quite practical,"
he said. And Dr. Rabin insisted that computers would have no problem
with the encryption scheme, even with long messages that were sent
among a large group of people.

Beyond the question of whether the system would work in practice, some
question it because, they say, the role of cryptography in protecting
privacy has been overblown.

"If you think cryptography is the answer to your problem, then you
don't know what your problem is," said Dr. Peter G. Neumann, a
computer scientist at SRI International in Menlo Park, Calif.

Dr. Neumann explained that there are always ways to get around
cryptography barriers and that these methods have nothing to do with
breaking codes.

"It's like the voting machines," he said. "You'd like to have some
integrity in the electoral process and now folks are coming out of the
woodwork saying, `We have this perfect algorithm for privacy and
security.' "

But, he said, while the systems may use cryptography to make sure that
when someone touches a screen to vote, that vote is transmitted with
perfect security, who's to ensure the integrity of the person who
programs the computer?

"There is no guarantee that your vote actually goes into the computer
the way it looks on the touch screen," Dr. Neumann said. "What does it
take to buy a computer programmer? A couple of years' salary and a
house in the Cayman Islands?"

Bruce Schneier, who is founder and chief technical officer for
Counterpane Internet Security in San Jose, said that, as a scientist,
he liked the idea of a provably secure system. "Research like this
should be encouraged," he said. "But research is different from
engineering."

But in the real world, a burglar confronted by an impenetrable lock on
the front door may well go round to the back and just smash a window.
"I'm a cryptographer by trade," Mr. Schneier said. "And a provably
secure cryptosystem doesn't do me any good. We're putting a stake in
the ground and hoping the enemy runs into it and now we're arguing
about whether it should be one mile tall or two miles tall. It doesn't
matter. The enemy will walk around it," he added.

Dr. Robert Morris, a retired cryptographer who was chief scientist for
the National Security Agency, the nation's code-making and code-
breaking agency, also questioned the primacy of cryptography.

"As far as I can see, he seems to be correct - it's a provably secure
method," Dr. Morris said. "But does that mean no one can read it?
Nah."

He explained: "You can still get the message, but maybe not by
cryptanalysis. If you're in this business, you go after a reasonably
cheap, reliable method. It may be one of the three B's: burglary,
bribery or blackmail. Those are right up there along with
cryptanalysis in their importance."

Dr. Rabin said that just because there are other weaknesses in
communications systems, that did not mean that secure encryption was
not important.

It is as though medical researchers started arguing that there is no
need to find a cure for AIDS, Dr. Rabin said. After all, many more
people die of heart disease, and if you cure people of AIDS, heart
disease can still strike them.

"This is not a reason not to work on H.I.V.," Dr. Rabin said. "The
problem of H.I.V. is still important."

Dr. Morris said that even though the actual breaking of codes might
not be necessary to read encrypted messages, Dr. Rabin's method could
have an effect. "In a sense, what it does is shift the emphasis from
cryptanalysis to some other sort of attack," he said.

ISN is hosted by SecurityFocus.com
---
To unsubscribe email LISTSERV () SecurityFocus com with a message body of
"SIGNOFF ISN".