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.

Implementation

It is a cipher in which the key is:

• at least as long as the total set of messages to be enciphered
• absolutely random
• never re-used

Given those three conditions, it can proven that the cipher is perfectly secure, in the sense that an attacker with intercepted message in hand has no better chance of guessing the message than an attacker who has not intercepted the message and only knows the message length. No such proof exists for any other cipher.

While cryptographic security is established, one-time pads tend to be usable, for practical and technical reason, in only small niches of encryption.

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.

Small changes which violate the conditions listed above do not just weaken the cipher a little. Quite often they destroy its security completely.

• Re-using the pad weakens the cipher to the point where it can be broken with pencil and paper. With a computer, the attack is trivially easy. The U.S. National Security Agency broke Soviet diplomatic ciphers which had been reused; see VENONA .
• Using anything less than truly random numbers completely invalidates the security proof.
• In particular, using computer-generated pseudo-random numbers may give an extremely weak cipher. It might also produce a good stream cipher, if the pseudo-random generator is both well-designed and properly seeded.

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. The pads themselves are shipped by trusted couriers or other secure means. Paper pads are printed on water-soluble and edible paper, or "flash" paper which will burn with the slightest spark, so they can easily be destroyed.

If he can copy it and return it without detection, he can read future messages. Paper pads were usually bound in a manner that broke a seal when turning to a new page.

Finally, even if the system is implemented and used correctly, it is highly vulnerable to a substitution attack. If an attacker knows some plaintext and has an intercepted message, he can discover the pad. This does not matter if the attacker is just a passive eavesdropper. It gives him no plaintext he didn't already know and we don't care that he learns a pad which we will never re-use. However, an active attacker who knows the plaintext can recover the pad, then use it to encode whatever he chooses. If he can get his version delivered instead of yours, this may be a disaster. If you send "attack at dawn", the delivered message can be anything the same length -- perhaps "retreat to east" or "shoot generals". An active attacker with only a reasonable guess at the plaintext can try the same attack. If the guess is correct, this works and the attacker's bogus message is delivered. If the guess is wrong, a garbled message is delivered.

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.

Different applications, both cryptographic and noncryptographic, may need more or less strict random numbers.

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 thorougly before taking the next ball.

Bogus one-time pads

Marketing claims about the "unbreakable" security of various products which somewhat resemble one-time pads are common; such claims are one of the surest signs of Cryptographic snake oil. Anyone who talks about "generating" a "one-time pad" using some algorithm does not have a one-time pad, but a stream cipher. If he or she does not even know that, it is quite unlikely to be a good stream cipher. Most systems marketed with such claims are worthless..