One-time pad: Difference between revisions
imported>Sandy Harris |
John Leach (talk | contribs) m (Text replacement - "{{subpages}}" to "{{PropDel}}<br><br>{{subpages}}") |
||
(87 intermediate revisions by 5 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 — 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 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 | 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. | ||
[[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 | | first = David | last = Kahn | ||
| title = The Codebreakers: the story of secret writing | | title = The Codebreakers: the story of secret writing | ||
| date = second edition, 1996 | | date = second edition, 1996 | ||
| publisher = Scribners}} p. 398</ref> | | 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> | ||
== 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 | | 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> | ||
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 | ||
* a sequence of | * a sequence of genuinely [[random number]]s<ref name=Knuth-II>{{citation | ||
| first = Donald | last = Knuth | | first = Donald | last = Knuth | ||
| title = The Art of Computer Programming, Volume II: Seminumerical Algorithms | | title = The Art of Computer Programming, Volume II: Seminumerical Algorithms | ||
| chapter = Chapter III, Random Numbers | | chapter = Chapter III, Random Numbers | ||
| date = 3rd Edition, 1998 | publisher = Addison-Wesley}} </ref> | | date = 3rd Edition, 1998 | publisher = Addison-Wesley}} </ref> | ||
* never re-used | * 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/ | | url = http://www.nsa.gov/venona/ | ||
| author = National Security Agency | | author = National Security Agency | ||
| title = VENONA}}</ref> | | 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== | ==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 | {{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 | | id = RFC 4086; IETF Best Current Practice 106 | ||
Line 65: | Line 75: | ||
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]]. | 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]]. | ||
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 | 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. | ||
===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 | 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 <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>. | |||
{{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]}} | |||
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> | |||
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 | ||
| url = http://www. | | 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>. | |||
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]]. | |||
==References== | ==References== | ||
{{reflist|2}} | {{reflist|2}} |
Latest revision as of 05:48, 8 April 2024
This article may be deleted soon. | ||
---|---|---|
![]() 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] ProofThe 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:
Given those three conditions, it can be proven that the cipher is perfectly secure. The proof is that
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 padAll 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.
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
The content of a one-time pad must be truly random. This immediately rules out a function such as UNIX/LINUX 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 generationIn 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. ApplicationsWhile 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].
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
|
- Pages using RFC magic links
- Articles for deletion September
- CZ Live
- Computers Workgroup
- Military Workgroup
- Mathematics Workgroup
- Security Subgroup
- Articles written in American English
- Advanced Articles written in American English
- All Content
- Computers Content
- Military Content
- Mathematics Content
- Military tag
- Security tag