An Unbreakable Code?
By John Savard for SecurityPortal
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.
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.
The Key Vanishes (New York Times)
Harvard prof in uncrackable crypto claim
SecurityPortal is the world's foremost on-line resource and services
provider for companies and individuals concerned about protecting their
information systems and networks.
The Focal Point for Security on the Net (tm)