One-time pad

A one-time pad (often abbreviated OTP) is a cipher system in which the cryptographic key, i.e. the secret used to encrypt and decrypt messages, is a sequence of random values, each one of which is only ever used once, and only to encrypt one particular letter or word. In practice, this means that the volume of key must be equal to that of all traffic to be sent or received, which makes it logistically impractical in high-volume applications. It remains useful in certain niches, and must observe a number of precautions for its use.

The name is derived from the physical implementation of the first cipher to use this approach. which used pads containing pages of printed random numbers, which were added to the plaintext using the rules of modular arithmetic; each page was used only once, after which it was destroyed.

Bell Labs researcher Gilbert Vernam effectively invented the stream cipher, obtaining U.S. Patent 1,310,719 on a device that took key and plaintext on paper tape in Baudot code and combined them with exclusive OR to produce ciphertext. Vernam's device was not completely secure since the key tape ran in a loop. Shortly thereafter, in 1918, US Army signals expert Joseph Mauborgne suggested using a truly random non-repeating key. effectively inventing the mechanised one-time-pad. However, since the best key storage mechanism of the time was punched paper tape, the volume was infeasible for military applications of the time.

Proof

The proof that a one-time pad, correctly used, is unbreakable was published just after the Second World War, by Claude Shannon.

A one-time pad is a cipher in which the key is:

• at least as long as the total set of messages to be enciphered
• a sequence of genuinely random numbers
• never re-used

Given those three conditions, it can proven that the cipher is perfectly secure. The proof is that

• the intercept could decrypt to any possible message of the correct length with some key (from properties of the XOR operation used)
• if the key is truly random, then all keys are equally likely (by definition)
• therefore all decryptions are equally likely
• an attacker with an intercepted message in hand has exactly the same chance of guessing the message as an attacker who only knows the message length
• except for telling him the message length, intercepting the message is of zero value to the attacker
• that is, the cipher is perfectly secure.

No such proof exists for any other cipher. Several others have proofs of security against an enemy whose resources (memory and/or computational effort) are bounded, but no other has a proof that holds even against an unbounded opponent.

Shannon also proved that any cipher with this security property must use a key at least as long as the message.

Not quite a one-time pad

All three of the conditions above are absolutely required for the proof. Small changes which violate those conditions do not just weaken the cipher a little. Quite often they destroy its security completely.

• Without truly random numbers, the security proof is not valid.

• It must be a one-time pad. Reusing any part of the pad, even once, makes the cipher vulnerable to a simple attack.

• The key must be as long as the the message. If it is shorter, then you must either re-use part of the key or generate a longer pseudorandom sequence from the key. The former is insecure. The latter gives you a stream cipher, not a one-time pad.

The OTP proof requires that all possible pads be equally likely; to achieve this, the key must be completely random and as long as the message. There are 2^padsize possible pads, but a deterministic algorithm to generate pads from keys can only generate 2^keysize of those, so with keysize < padsize no such algorithm can possibly meet the required condition. A non-deterministic algorithm to generate a pad from a key would not give a useful cipher; the recipient, even with the key, would have no way to generate the same pad and decrypt the message.

Using any algorithmic method to generate "random numbers" gives a stream cipher, not a one-time pad. A well-designed and well-implemented stream cipher can certainly be secure, but it cannot be proven secure by the one-time pad proof. Evaluating the security of a stream cipher requires an analysis of the random number generator; that raises a whole set of issues that are irrelevant for a one-time pad. There are random number generators such as Blum Blum Shub which have their own proofs of security. One of these might be used to build a stream cipher with provable security, but it still would not be a one-time pad.

Re-using any of the pad material creates a substantial weakness; see this discussion. When Soviet cryptographic clerks, in different locations, used the same one-time pad twice for different messages, the U.S. National Security Agency was able, with massive computational effort for the time, to read many of their messages; see VENONA.

One sometimes sees woefully insecure crytosystems with extravagant marketing claims; these are often described as snake oil. One common sign of snake oil is that the vendor claims one-time pad security for something that is not actually a one-time pad.

One-time pad generation

Choosing random quantities to foil a resourceful and motivated adversary is surprisingly difficult. — IETF Best Current Practice 106

The content of a one-time pad must be truly random. This immediately rules out a function such as UNIX/LINUX random(), which is a pseudo-random number generator. Pseudo-random means that the function will always produce the same output when initialized with the same value which is useful in certain software testing; see pitfalls in computer simulation.

Effective one-time encryption depends on having truly random keys, which must be generated from nonmathematical methods. With modern instruments and equipment, a truly random one-time pad may be generated with a combination of measurement of a random physical phenomenon (e.g., thermal noise or radioactive disintegrations), which is then captured by a computer and put into high-density storage. The measurement may be self-similar in a way that can be exploited statistically; see Fractal for a specific type of self-similarity.

See random number generator for techniques used to generate such pads.

Manual generation

In the past, one-time pads were generated by typists who were told to type randomly, but, in practice, had patterns. Limited to manual methods, a not-unreasonable way is to put numbered balls in a bowl, having a blindfolded person take it out, the number recorded, the ball returned to the bowl, and the bowl shaken thoroughly before taking the next ball.

Applications

While cryptographic security is established, one-time pads tend to be usable, for practical and technical reasons, in only small niches of encryption. Bruce Schneier has a good discussion of the difficulties. He also has more recent comments .

As a practical person, I've observed that one-time pads are theoretically unbreakable, but practically very weak. By contrast, conventional ciphers are theoretically breakable, but practically strong. — Steve Bellovin as quoted in Marcus Ranum's One-time-pad FAQ

First, it is impractical for applications involving appreciable amounts of traffic. There must be as much key as there is traffic, which may be practical for high-security applications if the key can be stored on high-density computer-readable media. While it would be useless for the headquarters of an army, it has been entirely practical for espionage traffic that is of small volume. Another example where it was a practical solution was for the original implementation of MOLINK, the "hotline" between Washington and Moscow, which was encrypted with a commercial machine that originally used one-time paper tapes. The two sides generate tapes for their direction of transmission. One-time pad was attractive because it gave total security, but was implemented with a commercial device rather than forcing either side to reveal their sensitive high-security encryption methods. Since the traffic was limited, and between two fixed locations, key volume was not overwhelming.

If an adversary can obtain a one-time pad, he can send deceptive messages, called a rewrite attack.. In espionage practice, there are usually additional security measure that are not part of the one-time pad, such "bluff checks", an example of which would be a prearrangement that the thirteenth word of the message would have an extra character at the end. .

All the possible attacks on a one-time pad (plus some others) apply to stream ciphers. For more on these attacks, see stream cipher.