An Unbreakable Code?

Once again, a cryptography story has hit the newspapers.

Dr. Michael Rabin, currently at Harvard, announced a new kind of cipher
that is “provably unbreakable.” And, indeed, it is exactly that, given
the assumptions on which it is based.

Two people wishing to exchange a secret message would need to set up
a source of genuinely random numbers that broadcasts these numbers to both
of them, and that produces so many random numbers
that no eavesdropper could possibly record everything it broadcasts
for whatever interval of time it takes to set up a message.

The first step in sending a message would be for the sender to notify
the receiver to start listening for random numbers at a certain time, or
both parties might be continuously listening, so that the numbers to be used
might be collected over days or weeks instead of minutes. Both
parties would, according to a prearranged system governed by a key,
listen for, and record, a minute subset of the broadcast random numbers,
small enough that it could be recorded easily.

Then, the sender would use those recorded numbers to encipher the message,
and the receiver would use them to decipher it.

An eavesdropper, trying to determine the key of the prearranged system
used to pick the random numbers used to encipher the message, would need to be
able to refer to all the broadcast random numbers, because the eavesdropper wouldn’t
know which ones were the right ones until after he had actually broken the code.

So, the code is unbreakable, if it really is impossible to record the
complete random number broadcast.

But it would seem that the difficulty of recording an entire broadcast
could only be something like a million times greater than that of
recording a minute piece of it, where it must be possible to actually find the
pieces of the broadcast, and receive them accurately. The broadcast couldn’t just be
a single digital signal of reasonable bandwidth, as any single signal that could
easily be listened to could also be recorded. Instead, thousands of separate signals
on different channels, using multiplexing techniques such as are used for
FM stereo broadcasts, or for sending telephone conversations over microwave
signals, would be needed. An optical channel, where hundreds of lasers at
different wavelengths of visible light are each modulated by a wide-bandwidth
complex signal of this sort would be better.

Thus, the assumption that the total signal cannot be recorded is based
on a comparison between the recording abilities of the communicating parties
and the eavesdropper.

This is like public-key cryptography, which is assumed to be secure because
the communicating parties have enough computer power to multiply two big numbers
together, but the eavesdropper does not have a computer that is sufficiently larger
that it can factor the product of those two numbers.

But a factor of a million, or even a billion, is not anywhere near the size
of the disparity in computer power that most public-key cryptosystems require
of an attacker.

RSA is unbreakable if no one has a big enough computer to break it. This new
system is unbreakable if no one has a big enough tape recorder. Neither one,
therefore, is just plain unbreakable, the way the one-time pad is. Breaking a
one-time pad is like predicting tomorrow’s lottery numbers. This new cryptosystem
certainly is an interesting idea, and it allows people to look at the problem
of encryption from a different angle. But it is not a new, more practical way
to achieve a higher degree of security than previously available.

This system does, however, have one advantage over public-key systems like RSA.
It is only assumed that, when one uses a modulus that is the product of two sufficiently
large primes, the computer power required to break RSA is many times greater than
the computer power required to use RSA for communications. The need for a wideband
tape recording capability to have the entire random bit stream available for later
use in cryptanalysis in this system, however, is provable. So we do have a proven
level of security, but that level of security is not an absolute one.

It might also be noted that, as it has had to record large quantities of radio
transmissions for later analysis, the National Security Agency is known to have
a lot of experience in designing very good high-bandwidth recording equipment.
This ability was necessary for intercepting radio signals transmitted using
spread-spectrum techniques, as well as for monitoring all radio traffic of interest
in any given place.

The most common form of spread-spectrum communications is called frequency
hopping. A pseudorandom number generator is used to determine which radio frequencies
are used in succession for small parts of a transmission.

If the pseudorandom number generator is of cryptographic quality, an eavesdropper
would have to record the signals, if any, found on all the channels that could be used
for the transmission.

This new proposed cryptosystem is a bit like spread-spectrum communications turned
inside out. A spread-spectrum signal which extends over too many channels for anyone to
record would also be protected against ever being intercepted. In spread-spectrum,
a wide bandwidth is mostly silent, except for the small part in which a signal is being
sent. In this system, a wide bandwidth is filled with a stream of random numbers,
but only a small part of them is used.

The advantage of this new system over spread-spectrum
is that there is no way to distinguish the random numbers that are used from those that are
not used by looking at them. The message itself provides a way to distinguish those that produce
sensible text from those that don’t, but the message is not sent until after the random numbers
used with it are sent, so the random numbers must all be recorded. However, one could
improve the spread-spectrum technique by filling all the unused channels with random signals
for a closer correspondence with this new idea. //

John Savard (jsavard@securityportal.com) is a writer for SecurityPortal

References

The Key Vanishes (New York Times)
http://cryptome.org/key-poof.htm

Harvard prof in uncrackable crypto claim
http://www.theregister.co.uk/content/4/17115.html