One-Time Pads and Vernam's "Cipher Printing Telegraph Systems" Paper
Most people who know something about cryptography have heard of the "one-time pad", the only cipher that is mathematically unbreakable. (I said "cipher" rather than "encryption mechanism" to exclude quantum cryptography from this discusion…) One-time pads work by combining a true-random key stream with the plaintext. If you have a copy of the key stream, you reverse the combination to recover the plaintext.
Let me give a simple example. Suppose that you assign each letter a value between 0 and 25: A=0, B=1, …, Z=25. Each key stream value is a number between 0 and 25. To encrypt a letter, add the key stream value; if the result is 26 or greater, subtract 26. Mathematically, we’d write
It is vital that the keystream values (a) be truly random and (b) never be reused. The Soviets got that wrong in the 1940s; as a result, the U.S. Army’s Signal Intelligence Service was able to read their spies’ traffic in the Venona program. The randomness requirement means that the values cannot be generated by any algorithm; they really have to be random, and created by a physical process, not a mathematical one.
A consequence of these requirements is that the key stream must be as long as the data to be encrypted. If you want to encrypt a 1 megabyte file, you need 1 megabyte of key stream that you somehow have to share securely with the recipient. The recipient, in turn, has to store this data securely. Furthermore, both the sender and the recipient must ensure that they never, ever reuse the key stream. The net result is that, as I’ve often commented, "one-time pads are theoretically unbreakable, but practically very weak. By contrast, conventional ciphers are theoretically breakable, but practically strong." They’re useful for things like communicating with high-value spies. The Moscow-Washington hotline used them, too. For ordinary computer usage, they’re not particularly practical.
One-time pads were invented by Gilbert Vernam around 1917. His scheme involved a keystream punched onto a paper tape. The bits on this tape were exclusive-ORed with the bits of plaintext typed on a keyboard; the resulting ciphertext was transmitted directly to the far end. By chance, I recently acquired a copy of Vernam’s original paper. (Though it is from 1926, it turns out that it’s still covered by copyright. After a bit of discussion, the IEEE agreed that I could post a scan on my web site.) It’s fascinating reading; he indeed realized the essential strengths and weaknesses of the system:
If the key … is made very long, so that it never repeats and if any portion of the key is never used for more than one message, the operation of "breaking" the cipher becomes very much more difficult. If … we employ a key composed of letters selected absolutely at random, a cipher system is produced which is absolutely unbreakable.
Vernam and his colleagues also realized the difficulty of dealing with very long tapes:
In order to reduce the amount of key tape required for handling large amounts of traffic, the "double key" system was devised. In this system two key tapes are used, the ends of each tape being glued together to form a loop preferably about seven feet in diameter…. The characters of the two tapes are combined … with those of the message tape to form the cipher message.The result is the same as though the two key tapes were first combined to produce a long single non-repeating key… This long, single key is not, strictly speaking, a purely random key throughout its length as it is made up of combinations of the two original and comparatively short key tapes.
The story of Vernam’s machine — and of how Major Joseph Mauorgne was able to break the two-tape variant — is told well by David Kahn in his magesterial work The Codebreakers. But what comes next is the most interesting part. According to Vernam, William Friedman — the man responsible for the mathematicization of cryptology — devised a fix: a third key tape, arranged to move irregularly, rather than in synchrony with the other two tapes. This insight — that the dynamic behavior of the cipher machine could itself be controlled by keying material — was the secret behind SIGABA, one of the only World War II-vintage systems that was never cracked. It is fortunate indeed that the Germans did not base the Enigma on this principle.
