One-time pad: Difference between revisions

The one-time pad is the most secure, and one of the simplest of all cryptographic 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. 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, if it's long enough, 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.

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), then the ciphertext gives the attacking cryptanalyst no information about the message other than its length. The disadvantages of the method are that it requires very large keys, requires that they be exchanged in advance and kept in synchrony as 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, even so, the one-time pad is not, despite is proven unbreakability, practical for most users, in most situations, most of the time.

The recent development of quantum cryptography has provided a way to securely generate identical, random pads at two locations simultaneously, in such a way that eavesdroppers cannot determine their contents. This may be a better way to generate and distribute one-time pads. It is not yet clear whether this will 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 absolute security of one-time pads is wholly dependent upon the randomness and secrecy of the key pad material. If the pad is perfectly random (and never becomes known to an attacker), then it is absolutely 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 stream, which is combined with the message. Stream ciphers can be secure in practice, but cannot 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 generators 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 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, here or anywhere else. A remarkable result from a remarkable man.