One-time pad
A one-time pad (often abbreviated OTP) is a cipher system in which the key, i.e. the secret used to encrypt and decrypt messages, is a long sequence of random values, each one of which is only ever used once, and only to encrypt one particular letter or word.
The name is derived from the first cryptosystems which used this approach, code systems which used pads containing pages of printed random numbers used as additives; each page was used only once, after which it was discarded.
Technical details
More technically, 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 easily be proved 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.
There are, however, several problems with this perfect cipher.
First, it is impractical for applications involving appreciable amounts of traffic. Due to the sheer size of the keys, key management is at best difficult, often completely impossible. While it would be useless for the headquarters of an army, it has been entirely practical for espionage traffic that is of small volume.
Second, it is dependent on having truly random keys, which must be generated from nonmathematical methods. With modern instruments and equipment, a truly random one-time pad can 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 hugh-density storage.
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.
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. In a famous example called Venona, the NSA broke Soviet diplomatic ciphers which had been misused this way.
- 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.
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.
In general then, despite its theoretical perfection, the one-time-pad has very limited practical application.
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 unlikely to be a good stream cipher; most systems marketed with such claims are worthless.
External links
There is a useful one time pad FAQ available.