One-time pad

From Citizendium
Revision as of 21:36, 1 August 2008 by imported>Sandy Harris
Jump to navigation Jump to search
This article is developed but not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable, developed Main Article is subject to a disclaimer.

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 wildly impractical for most applications. Due to the sheer size of the keys, key management is at best difficult, often completely impossible.

Second, it is extremely fragile. 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.
  • 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.

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; many systems marketed with such claims are worthless.

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.

There is a useful one time pad FAQ available.