One-time pad: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Sandy Harris
No edit summary
mNo edit summary
 
(104 intermediate revisions by 7 users not shown)
Line 1: Line 1:
{{subpages}}
{{PropDel}}<br><br>{{subpages}}
{{TOC|right}}
A '''one-time pad''' 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 of which is only ever used ''once'', and only to encrypt ''one'' particular item &mdash; a character of text in a manual system, a byte or computer word in an electronic version. The receiver has an identical pad to use in decryption. One-time pad is often abbreviated '''OTP''', which unfortunately also occurs as the abbreviation for another cryptographic concept, the [[one-time password]].


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.
The great advantage of a one-time pad is that, properly used, it is provably secure against all [[passive attack]]s. However, the requirement that each part be used only once means the key must be as long as the total volume of all traffic to be sent or received, which makes it logistically impractical in high-volume applications. The technique is useful only in certain niches, and then only if a number of precautions are observed in its use.  


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 destroyed. Computer implementations typically use exclusive-or (XOR) to combine plaintext and pad bit-by-bit.


==Technical details==
[[Bell Labs]] researcher [[Gilbert Vernam]] effectively invented the [[stream cipher]], obtaining U.S. Patent 1,310,719 on a device that took key and plaintext on paper tape in Baudot code and combined them with exclusive OR to produce ciphertext. Vernam's device was not completely secure since the key tape ran in a loop. Shortly thereafter, in 1918, US Army signals expert [[Joseph Mauborgne]] suggested using a truly random non-repeating key. effectively inventing the mechanised one-time-pad.<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> However, since 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>


More technically, it is a cipher in which the key is:
== Proof ==
The proof that a one-time pad, correctly used, is unbreakable was published just after the [[Second World War]], by [[Claude Shannon]]. <ref name=ShannonSec>{{citation
| title = Communication Theory of Secrecy Systems
| first = Claude E. | last = Shannon
| url = http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf}}</ref>
 
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
* at least as long as the total set of messages to be enciphered
* absolutely [[random]]
* a sequence of genuinely [[random number]]s<ref name=Knuth-II>{{citation
* never re-used
| first = Donald | last = Knuth
| title = The Art of Computer Programming, Volume II: Seminumerical Algorithms
| chapter = Chapter III, Random Numbers
| date = 3rd Edition, 1998 | publisher = Addison-Wesley}} </ref>
* never re-used, not even in part
 
Given those three conditions, it can be 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 (from properties of the XOR operation used)
* if the key is ''truly random'', then all keys are equally likely (by definition)
* 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. Several others have proofs of security against an enemy whose resources (memory, computational effort or available data) are bounded, but no other has a proof that holds even against an unbounded opponent.
 
Shannon also proved that any cipher with this security property must use a key at least as long as the message.
 
== Not quite a one-time pad ==
All three of the conditions above are absolutely required for the proof. Small changes which violate those conditions generally do not just weaken the cipher a little; quite often they destroy its security completely.
 
* Without ''truly random numbers'', the security proof is not valid.
 
* It must be a ''one-time'' pad. Reusing any part of the pad, even once, makes the cipher vulnerable to a [[Stream_cipher#Reusing_pseudorandom_material|simple attack]].
 
* The key must be ''as long as the message''. If it is shorter, then you must either 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.
 
The one-time pad proof requires that all possible pads be equally likely; to achieve this, the key must be completely random and as long as the message. There are 2<sup>padsize</sup> possible pads, but a deterministic algorithm to generate pads from keys can only generate 2<sup>keysize</sup> of those, so with keysize < padsize ''no deterministic algorithm can possibly meet the required condition''. A non-deterministic algorithm to generate a pad from a key would not give a useful cipher; the recipient, even with the key, would have no way to generate the same pad and decrypt the message.
 
Using ''any'' algorithmic method to generate "random numbers" gives a [[stream cipher]], ''not a one-time pad''. A well-designed and well-implemented stream cipher may be secure, but it cannot be proven secure by the one-time pad proof. Evaluating the security of a stream cipher requires an analysis of the [[random number generator]], and 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. <ref name=Goldwasser2008>{{citation
| contribution = Chapter 3, Pseudo-random bit generators
| url = http://www.cs.ucsd.edu/~mihir/papers/gb.pdf
| title = Lecture Notes on Cryptography
| first1=Shafi | last1 = Goldwasser | first2 =  Mihir | last2 = Bellare
| date = July 2008}}</ref> One of these might be used to build a stream cipher with provable security, but it would likely be far too slow for practical use and it ''still'' would not be a one-time pad.
 
Re-using any of the pad material creates a substantial weakness; see this [[Stream_cipher#Reusing_pseudorandom_material | 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]]<ref name=NSA-Venona>{{citation
| url = http://www.nsa.gov/venona/
| author = National Security Agency
| title = VENONA}}</ref>.
 
One sometimes sees woefully insecure crytosystems with extravagant marketing claims; these are often described as [[Snake (animal)_oil_(cryptography)|snake oil]]. One common sign of snake oil is that the vendor claims one-time pad security for something that is not actually a one-time pad.
 
==One-time pad generation==
{{quotation|Choosing random quantities to foil a resourceful and motivated adversary is surprisingly difficult.|IETF Best Current Practice 106<ref name=RFC4086>{{citation
| id = RFC 4086; IETF Best Current Practice 106
| title = Randomness Requirements for Security
| first1 = D. 3rd | last1 = Eastlake | first2 = J. |last2 = Schiller | first3 = S. | last3 = Crocker
| date = June 2005
| url = http://www.ietf.org/rfc/rfc4086.txt}}</ref>}}
The content of a one-time pad must be truly random. This immediately rules out a function such as UNIX/LINUX <code>random()</code>, 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 [[Computer simulation#Pitfalls in computer simulation|pitfalls in computer simulation]].


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.
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. The measurement may be self-similar in a way that can be exploited statistically; see [[Fractal]] for a specific type of self-similarity.


There are, however, several problems with this "perfect" cipher.
See [[random number generator]] for techniques used to generate such pads.


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


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.
== 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 <ref>{{citation|author=Bruce Schneier|title=One-Time Pads|date=October 2002|url=http://www.schneier.com/crypto-gram-0210.html#7}}</ref> of the difficulties. He also has more recent comments <ref>{{citation|author=Bruce Schneier|title=The History of One-Time Pads and the Origins of SIGABA|date=September 2009|url=http://www.schneier.com/blog/archives/2009/09/the_history_of.html}}</ref>.


* 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.
{{quotation|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 [http://www.ranum.com/security/computer_security/papers/otp-faq/ One-time-pad FAQ]}}
* 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.
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
| title =  Moscow's Still Holding
| journal = New York Times
| first = Webster | last = Stone
| date = September 18, 1988
| url =http://query.nytimes.com/gst/fullpage.html?res=940DEFDC1339F93BA2575AC0A96E948260&sec=&spon=&pagewanted=all}}</ref><ref>Kahn, pp. 715-716</ref>


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


In general then, despite its theoretical perfection, the one-time-pad has very limited practical application.
All the possible attacks on a one-time pad (plus some others) apply to stream ciphers. For more on these attacks, see [[Stream_cipher#Restrictions_and_weaknesses | stream cipher]].


There is a useful [http://www.ranum.com/security/computer_security/papers/otp-faq/ one time pad FAQ] available.
==References==
{{reflist|2}}[[Category:Suggestion Bot Tag]]

Latest revision as of 12:01, 28 September 2024

This article may be deleted soon.
To oppose or discuss a nomination, please go to CZ:Proposed for deletion and follow the instructions.

For the monthly nomination lists, see
Category:Articles for deletion.


A one-time pad 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 of which is only ever used once, and only to encrypt one particular item — a character of text in a manual system, a byte or computer word in an electronic version. The receiver has an identical pad to use in decryption. One-time pad is often abbreviated OTP, which unfortunately also occurs as the abbreviation for another cryptographic concept, the one-time password.

The great advantage of a one-time pad is that, properly used, it is provably secure against all passive attacks. However, the requirement that each part be used only once means the key must be as long as the total volume of all traffic to be sent or received, which makes it logistically impractical in high-volume applications. The technique is useful only in certain niches, and then only if a number of precautions are observed in its use.

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 destroyed. Computer implementations typically use exclusive-or (XOR) to combine plaintext and pad bit-by-bit.

Bell Labs researcher Gilbert Vernam effectively invented the stream cipher, obtaining U.S. Patent 1,310,719 on a device that took key and plaintext on paper tape in Baudot code and combined them with exclusive OR to produce ciphertext. Vernam's device was not completely secure since the key tape ran in a loop. Shortly thereafter, in 1918, US Army signals expert Joseph Mauborgne suggested using a truly random non-repeating key. effectively inventing the mechanised one-time-pad.[1] However, since the best key storage mechanism of the time was punched paper tape, the volume was infeasible for military applications of the time. [2]

Proof

The proof that a one-time pad, correctly used, is unbreakable was published just after the Second World War, by Claude Shannon. [3]

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[4]
  • never re-used, not even in part

Given those three conditions, it can be 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 (from properties of the XOR operation used)
  • if the key is truly random, then all keys are equally likely (by definition)
  • 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. Several others have proofs of security against an enemy whose resources (memory, computational effort or available data) are bounded, but no other has a proof that holds even against an unbounded opponent.

Shannon also proved that any cipher with this security property must use a key at least as long as the message.

Not quite a one-time pad

All three of the conditions above are absolutely required for the proof. Small changes which violate those conditions generally do not just weaken the cipher a little; quite often they destroy its security completely.

  • Without truly random numbers, the security proof is not valid.
  • It must be a one-time pad. Reusing any part of the pad, even once, makes the cipher vulnerable to a simple attack.
  • The key must be as long as the message. If it is shorter, then you must either 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.

The one-time pad proof requires that all possible pads be equally likely; to achieve this, the key must be completely random and as long as the message. There are 2padsize possible pads, but a deterministic algorithm to generate pads from keys can only generate 2keysize of those, so with keysize < padsize no deterministic algorithm can possibly meet the required condition. A non-deterministic algorithm to generate a pad from a key would not give a useful cipher; the recipient, even with the key, would have no way to generate the same pad and decrypt the message.

Using any algorithmic method to generate "random numbers" gives a stream cipher, not a one-time pad. A well-designed and well-implemented stream cipher may be secure, but it cannot be proven secure by the one-time pad proof. Evaluating the security of a stream cipher requires an analysis of the random number generator, and 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. [5] One of these might be used to build a stream cipher with provable security, but it would likely be far too slow for practical use and it still would not be a one-time pad.

Re-using any of the pad material creates a substantial weakness; 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[6].

One sometimes sees woefully insecure crytosystems with extravagant marketing claims; these are often described as snake oil. One common sign of snake oil is that the vendor claims one-time pad security for something that is not actually a one-time pad.

One-time pad generation

Choosing random quantities to foil a resourceful and motivated adversary is surprisingly difficult. — IETF Best Current Practice 106[7]

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

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 [8] of the difficulties. He also has more recent comments [9].

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.[10] 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.[11][12]

If an adversary can obtain a one-time pad, he can send deceptive messages, called a rewrite attack.[13]. 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. [14].

All the possible attacks on a one-time pad (plus some others) apply to stream ciphers. For more on these attacks, see stream cipher.

References

  1. Kahn, David (second edition, 1996), The Codebreakers: the story of secret writing, Scribners p. 398
  2. Kahn, pp. 397-398
  3. Shannon, Claude E., Communication Theory of Secrecy Systems
  4. Knuth, Donald (3rd Edition, 1998), Chapter III, Random Numbers, The Art of Computer Programming, Volume II: Seminumerical Algorithms, Addison-Wesley
  5. Goldwasser, Shafi & Mihir Bellare (July 2008), Chapter 3, Pseudo-random bit generators, Lecture Notes on Cryptography
  6. National Security Agency, VENONA
  7. Eastlake, D. 3rd; J. Schiller & S. Crocker (June 2005), Randomness Requirements for Security, RFC 4086; IETF Best Current Practice 106
  8. Bruce Schneier (October 2002), One-Time Pads
  9. Bruce Schneier (September 2009), The History of One-Time Pads and the Origins of SIGABA
  10. Kahn, p.663-666
  11. Stone, Webster (September 18, 1988), "Moscow's Still Holding", New York Times
  12. Kahn, pp. 715-716
  13. Smith, Richard E. (1997), Internet Cryptography, Addison-Wesley pp. 69-70
  14. Miller, Laura, "Her life as a spy", Salon.com