One-time pad

The one-time pad is one of the simplest of all cryptography methods. It was invented and patented just after World War I by [Gilbert Vernam]? (of AT&T) and [Joseph Mauborgne]? (USA, later chief of the [Signal Corps]?). The fundamental features are that the sender and receiver each have a copy of an [encryption key]?, which is as long as the message to be encrypted, and each key is used for only one message and then discarded. That key must be random, that is without pattern, and must remain unknown to any attacker. For example, two identical pads of paper with random letters can be exchanged between sender and receiver. Later, when they wish to send a message, the sender uses the random key on the first page of his pad to encrypt a message; one technique is to XOR? (combine in a particular way) the first character of the key with the first character of the plaintext, the second character of the key with the second character of the plaintext, etc. Even a simple [letter-substitution cipher]? as has been known at least since Julius Caesar's time can be used--as long as the offset for each letter is determined individually by the corresponding random letter of the key (the traditional "Caesar cipher" used a single offset for the whole message). He then sends the encoded message to the receiver, who decrypts it with his copy of the first page of the pad. Both now discard the used key page.

One-time pads are provably secure, in that if all the conditions are met properly (i.e., the keys are chosen randomly, are at least as long as the message, and are never reused), all possible messages of that length are equally likely, without additional information being available to the cryptanalyst. The disavantages of the method are that it requires very large keys, requires that they be exchanged in advance and kept synchronized, and requires the keys to be secret from all attackers. It is therefore not practical for most users lacking diplomatic bag protection. It is also very cumbersome for large messages (without automatic equipment). The advent of widely available small computers has made the one-time pad algorithm much less difficult to use and much faster. Key material distribution is still sufficiently difficult that, even so, the one-time pad is not, despite is proven unbreakability, practical for most users.

One-time pads have been used in specialized circumstances, especially in the early-to-mid 1900s; the Weimar Republic Diplomatic Service began using the algorithm about 1920. Poor Soviet cryptography (broken by the British and made public in two instances in the 1920s) forced them to improve their systems, and they seem to have gone to one-time pads for some uses around 1930. KGB spies used pencil and paper one-time pads to communicate. Beginning in the late 1940s, the U.S. Government was able to break some of the one-time pad traffic to Moscow as a result of errors made near the end of 1941 in generating the key material. By the time the effort ended in the 1970s(?), the United States had fully or partially decrypted several thousand of the hundreds of thousands of Soviet messages from the U.S. to Moscow during and just after World War II. Some of those messages provided evidence of the identity of members of the "Atom Spy" ring which operated in WWII. You can find this history of this project, code named Venona?, at the [NSA web site].

The absolute security of one-time pads is dependent upon the randomness of the pad. If the pad is perfectly random, then it is absolutely secure. If the pad is generated by a deterministic program, then it is not a one-time pad; it is a [stream cipher]?. Stream ciphers can be secure in practice, but none is known to be (and none is thought ever to be) absolutely secure in the same provable sense.

The random number generators that come with most computer programming languages and in operating system call libraries are often flawed, and produce very poor random sequences which are cryptographically useless. More advanced algorithms called cryptographically secure generators, such as [Blum Blum Shub]?, are believed to be secure stream ciphers in practice. None of these stream ciphers have the absolute, theoretical security of a one-time pad. Shannon's work can be interpreted as showing that any provably secure cypher will be effectively equivalent to the one-time pad algorithm. If so, one-time pads offer the best possible security of any cypher, now or ever.

---

/Talk