Main Page | See live article | Alphabetical index

One-time pad

The one-time pad is the most secure, and one of the simplest, of all ciphers. 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 of this cipher 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. In addition, the key must never be reused, otherwise the cipher becomes trivially breakable.

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 in the pad (say that on the first page of his pad) to encrypt a message. One technique is to XOR (ie, 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, having used it only 'one-time'.

One-time pads are information-theoretically 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), then the ciphertext gives the attacking cryptanalyst no information about the message other than its length. This is a very strong notion of security, and implies that one-time pads are secure even against cryptanalysts with infinite computational power. Also, they are one of very few cryptosystems which can be implemented on a deterministic computer which would provably survive any affirmative solution of P vs. NP.

The disadvantages of the method are that it requires very large 'keys', requires that they be exchanged in advance and kept in synchrony when used, be entirely without pattern (ie, random), 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 and cheap computers has made the one-time pad algorithm much less difficult to use and much faster.

Key material distribution is still sufficiently difficult that except for rare circumstances (e.g., spies who must encrypt short messages without access to sophisticated encryption methods), one-time pads are at present mostly of theoretical interest. In some diplomatic or espionage situations, the one-time pad is useful because it can be computed by hand, after breaking a word into equal-sized groups of letters.

At other times, it can be useful to use very simple "one time" signals - a signal, used only once, of "A" for "mission completed" and "B" for "mission failed" cannot be "decrypted" in any reasonable sense of the word. However, such strategies (often used by real operatives) are not a cryptographic one-time pad in any real sense.

The recent development of quantum cryptography has provided a way, theoretically, to securely transmit identical key pads between two locations simultaneously, in such a way that eavesdroppers cannot determine their contents without the eavesdropping being detected. This may eventually provide a better way to distribute one-time pad key materials. It is not yet clear whether this will ever be convenient enough to see widespread use.

One-time pads have been used in specialized circumstances, since the early 1900s; the Weimar Republic Diplomatic Service began using the algorithm about 1920. Poor Soviet cryptography (broken by the British, with messages 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 also used pencil and paper one-time pads to communicate. Beginning in the late 1940s, the U.S. and British intelligence agencies were able to break some of the one-time pad traffic to Moscow during WWII as a result of errors made near the end of 1941 in generating/distributing the key material. This huge, decades long effort was codenamed VENONA. The "hot line" from the White House to the Kremlin during the Cold War reportedly used a one time pad; this line was used so infrequently that pad exhaustion was a minor concern relative to providing the necessary security.

The information-theoretic security of one-time pads is wholly dependent upon the randomness (or unpredictability) and secrecy of the key pad material. If the key material is perfectly random (and never becomes known to an attacker), then it is information-theoretically secure. If the pad material is generated by a deterministic program, then it is not, and cannot be, a one-time pad; it is a stream cipher. A stream cipher takes a short key, and uses it to generate a long pseudorandom stream, which is combined with the message using a mechanism similar to that used in a one-time pad. Stream ciphers can be secure in practice, but cannot be absolutely secure in the same provable sense. At least one of the Fish cyphers used by the German military in WWII turned out to be an insecure stream cypher, not a practical automated one-time pad as seems to have been intended by its designers. Bletchley Park broke Lorenz machine messages regularly. None of these stream ciphers have the absolute, information-theoretical security of a one-time pad, although there exist stream ciphers that appear to be unbreakable in practice by a cryptanalyst without access to the key.

The similarity between stream ciphers and one-time pads often leads cryptographic novices to invent (usually very insecure) stream ciphers under the mistaken impression that they are using one-time pads. An especially insecure approach is to use any of the random number generators that come with most computer programming languages and operating system call libraries. These typically produce sequences that pass simple statistical tests but that are nonetheless highly predictable given a sample of their output—making them absolutely useless for cryptographic purposes. In particular, the Mersenne twister algorithm, while "random" for almost any research or simulation use, cannot be used to generate a one-time pad. One reason this, and similiar algorithms, are useful in research is that they are deterministic - and therefore an independent researcher can seed the algorithm with the same values and get the same result. This is a severe weakness for cryptographic use.

Though cryptographically secure pseudo-random number generators exist that permit computationally secure stream ciphers, even these do not provide the information-theoretic security of a one-time pad, and a claim that a particular stream cipher is equivalent in strength to a one-time pad is often viewed as a clear sign of snake oil by professional cryptographers.

Shannon's work can be interpreted as showing that any information-theoretically secure cipher will be effectively equivalent to the one-time pad algorithm. If so, one-time pads offer the best possible security of any cipher, now or ever.