One-time pad: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Howard C. Berkowitz
(snapshot save)
imported>Howard C. Berkowitz
(snapshot save)
Line 1: Line 1:
{{subpages}}
{{subpages}}


A '''one-time pad''' (often abbreviated OTP) is a [[cipher]] system in which the [[key (cryptology)|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. In practice, this means that the volume of key must be equal to that of all traffic to be sent or received, which make its use logistically impractical.
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.


It is the only cipher that is provably unbreakable, if the adversary does not have a copy of the key. <ref name=ShannonSec>{{citation  
The technique appears to have been invented in 1918 by Joseph Mauborgne,<ref name=Kahn>{{citation
| first = David | last = Kahn
| title = The Codebreakers: the story of secret writing
| date = second edition, 1996
| publisher = Scribners}} p. 398</ref> but was not proven unbreakable until during or slightly after the [[Second World War]], by Claude Shannon <ref name=ShannonSec>{{citation  
  | title = Communication Theory of Secrecy Systems  
  | title = Communication Theory of Secrecy Systems  
  | first = Claude E. | last = Shannon
  | first = Claude E. | last = Shannon
  | url = http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf}}</ref>
  | url = http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf}}</ref>


The name is derived from the first [[cryptosystem]]s which used this approach, code systems which used pads containing pages of printed [[random number]]s used as [[additive]]s; each page was used only once, after which it was discarded.
The name is derived from the physical implementation of the first cipher to use this approach. which used pads containing pages of printed [[random number]]s, 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. <ref>Kahn, pp. 397-398</ref>


==Implementation==
==Implementation==
Line 22: Line 26:
While cryptographic security is established, one-time pads tend to be usable, for practical and technical reason, in only small niches of encryption.  
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.<ref name=Kahn>{{citation
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.<ref> Kahn, p.663-666 </ref>  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.<ref name=NYT1988-09-18>{{citation
| first = David | last = Kahn
| title = The Codebreakers: the story of secret writing
| date = second edition, 1996
| publisher = Scribners}} p.663-666 </ref>  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.<ref name=NYT1988-09-18>{{citation
  | title =  Moscow's Still Holding
  | title =  Moscow's Still Holding
  | journal = New York Times
  | journal = New York Times
Line 42: Line 42:
* 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.
* 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, although there are usually additional security measures, such as bluff checks, in espionage traffic. 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 an adversary can obtain a one-time pad, he can send deceptive messages, called a '''rewrite attack'''.<ref name=Smith>{{citation
| first = Richard E. | last = Smith
| title = Internet Cryptography
| publisher = Addison-Wesley | year = 1997}} pp. 69-70</ref>.  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. <ref>{{citation
| title = Her life as a spy
| first =  Laura | last = Miller
| journal = Salon.com
| url = http://www.salon.com/books/review/2007/01/04/helm/print.html}}</ref> 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.
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.

Revision as of 13:12, 3 August 2008

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 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,[1] but was not proven unbreakable until during or slightly after the Second World War, by Claude Shannon [2]

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. [3]

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.[4] 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.[5][6]

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[7] .
  • 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.[8]. 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. [9] 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[10]

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

References

  1. Kahn, David (second edition, 1996), The Codebreakers: the story of secret writing, Scribners p. 398
  2. Shannon, Claude E., Communication Theory of Secrecy Systems
  3. Kahn, pp. 397-398
  4. Kahn, p.663-666
  5. Stone, Webster (September 18, 1988), "Moscow's Still Holding", New York Times
  6. Kahn, pp. 715-716
  7. National Security Agency, VENONA
  8. Smith, Richard E. (1997), Internet Cryptography, Addison-Wesley pp. 69-70
  9. Miller, Laura, "Her life as a spy", Salon.com
  10. Eastlake, D. 3rd; J. Schiller & S. Crocker (June 2005), Randomness Requirements for Security, RFC 4086; IETF Best Current Practice 106