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 technique appears to have been invented in 1918 by Joseph Mauborgne, but was not proven unbreakable until during or slightly after the Second World War, by Claude Shannon

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 discarded. An early mechanized system invented by Gilbert Vernam in 1918 offered the potential to use a machine-readable key; if the key was as long as the plaintext, the conditions for provable cryptographic security exist. Given that the best key storage mechanism of the time was punched paper tape, the volume was infeasible for military applications of the time.

Proof

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
• if the key is truly random, then all keys are equally likely
• 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.

Related ciphers

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.

• Using anything less than truly random numbers invalidates the security proof. Using any algorithmic method to generate "random numbers" gives a stream cipher, not a one-time pad.

• Reusing the pad, even once, makes it vulnerable. 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 .

• If the random key is shorter than the message, then you must ether 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.

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 its security 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.

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.

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. An expert in the physical phenomenon being measured. 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.

The possibility of pseudo-random methods that are adequately random

Some research indicates that in carefully selected situations, a pseudo-random number generator, which meets a number of cryptographic criteria, may be adequately random for security. The proofs are complex and not universally accepted, but may be true for a useful number of situations.

A "generator" technique may be quite adequate for the application, but may not be truly unbreakable. Few high-grade military cryptosystems are theoretically unbreakable without possession of the key, but total security may not be necessary. In a simple military example, assume it takes 1 minute for a modern "counterbattery" radar to detect an incoming shell and backtrack to find the location of the cannon that fired it, and send its coordinates to one's own artillery. Further assume that it will take 2 minutes for the return fire to hit that location. If the enemy cannot move out of range in less than 3 minutes, the firing order need not be encrypted at all.

Espionage traffic, however, may need to be protected for decades; there have been real cases of more than one generation of spy in the same family.