One-time pad Guide, Meaning , Facts, Information and Description
In cryptography, the one-time pad (OTP), sometimes known as the Vernam cipher, is a theoretically unbreakable method of encryption where the plaintext is combined with a random "pad" the same length as the plaintext. It is of central importance in cryptography because of this, though not widely used in practice. The "pad" part of the name comes from early implementations of the key material as a pad of gummed paper (for easy concealment, the pad was often physically very small, e.g. [1]).![[1]](http://www.ranum.com/security/computer_security/papers/otp-faq/otp.jpg){kind=link}
The cipher is often described in such terms as "perfectly secure" and "provably, absolutely, unbreakable". This is quite correct in theory; the method was proven unbreakable in an information-theoretic sense by Claude Shannon. However, it has several drawbacks in practice: it requires secure exchange of the one-time pad material, which must be as long as the message; and careful treatment to make sure that it is disposed of correctly and never reused — hence "one time". These implementation difficulties have led to examples of one-time pad messages being broken (for example, VENONA), and are so serious that they have prevented the one-time pad from being adopted as a widespread tool in information security.
The one-time pad was invented in 1917 and patented (US patent 1310719) just after World War I by Gilbert Vernam (of AT&T;) and Joseph Mauborgne (USA, later chief of the US Army Signal Corps).
| Table of contents |
|
2 Example 3 Security 4 Universal unbreakability 5 Problems and limitations 6 Historical uses 7 Implementation pitfalls of one-time pads 8 See also 9 External links |
Principle
Basically each character in the message is combined with one from the (random, secret, and used only once) pad. So, in this simple implmentation, the pad must be at least the length of the message. Theoretically there is no way to decipher the message without knowing the contents of the pad, lucky guesses excepted. For this reason it is very important that the pad be protected (ie, secret), random (ie, unpredictable by anyone including an attacked), and used only once (the one-time part), lest the cipher be easily compromisable (some attacks are trivially simple and entirely effective). Example
Suppose Alice wishes to send the momentus message, 'HELLO', to Bob. Two pads of paper containing identical random sequences of letters are (somehow) produced and (somehow) securely issued to both. The 26-letter alphabet consisting of "A" through "Z" is used, each letter corresponding to a numerical value: "A" is 0, "B" is 1, and so on through "Z", equalling 25. When she wants to send the example message, Alice chooses the appropriate unused page from the pad (arranged for in advance, as for instance 'use the 12th sheet on Labor Day', or 'use the next available sheet for the next message'). The material on that sheet is the key for this message. Each letter from the pad will be combined in a predetermined way with one letter of the message. Assuming for this example that the technique is to add the numerical values of the key and the message using modular arithmetic, we will have the following. If key material is, X M C K L
and the message is "HELLO", then the numerical values of corresponding letters (using their order in the English alphabet (the ASCII character set values are equally usable as are many others) are added together, modulo 26, as follows:
23 (X) 12 (M) 2 (C) 10 (K) 11 (L) key + 7 (H) 4 (E) 11 (L) 11 (L) 14 (O) message = 30 16 13 21 25 key+message = 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) key+message (mod 26)(If a number is larger than 25, in modular arithmetic fashion, 26 is subtracted from the number to make it less than 26.)
The ciphertext to be sent to Bob is thus "EQNVZ." Bob uses the same process, but in reverse, to obtain the plaintext. Here, the key is subtracted from the ciphertext using modular arithmetic:
4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) ciphertext - 23 (X) 12 (M) 2 (C) 10 (K) 11 (L) key = -19 4 11 11 14 ciphertext-key = 7 (H) 4 (E) 11 (L) 11 (L) 14 (O) ciphertext-key (mod 26)(Similar to above, if a number is negative, 26 is added to make the number positive)
Thus, Bob produces Alice's plaintext, the vital message, "HELLO". Both Alice and Bob destroy the key sheet immediately after use, thus preventing reuse and an essentially trivial attack against the cipher. The KGB often issued its agents one-time pads printed on tiny sheets of "flash paper"—paper chemically converted to nitrocellulose, which burns almost instantly and leaves no ash.
The typical one-time pad implementation is probably no longer actual pads of minuscule paper and a sharp pencil with some mental arithmetic, but rather a software program using data files as input (plaintext) and output (ciphertext) and key material (the required random sequence). The central part of such a program is so simple that one-time pad implementations are early exercises in many a computer programming course; generating the random sequences required is not at all elementary and is usually left for more advanced courses. Ensuring that the key material is used only once and completely destroyed after use is also not very elementary. The auxiliary parts of a software one-time pad implementation (eg, secure handling of plaintext, actual random key material, assurance of one-time-only use of the key material, ...) are quite difficult for even the most skilled software designers.
Security
One-time pads are "information-theoretically secure'" in that, if all the previously mentioned conditions are properly met, then the encrypted message (ie, the ciphertext) provides no information about the original message to a cryptanalyst. This is a very strong notion of security, and it was first proven, mathematically, by Claude Shannon during WWII. His result was published in the Bell Labs Technical Journal in 1949. Properly used one-time pads are secure in this sense even against cryptanalysts with infinite computational power. To continue the example from above, Eve intercepts Alice's ciphertext: "EQNVZ", if Eve had infinite computing power, she would quickly find that the key: "XMCKL" would produce the plaintext "hello". However, she would try the key material sequence "TQURI" giving the plaintext "LATER", an equally plausible message:
4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) ciphertext - 19 (T) 16 (Q) 20 (U) 17 (R) 8 (I) possible key = -15 0 -7 4 17 ciphertext-key = 11 (L) 0 (A) 19 (T) 4 (E) 17 (R) ciphertext-key (mod 26)In fact, it's possible to "decrypt" any message whatsoever with the same number of characters out of the ciphertext simply by using a different key.
The one-time pad would not be made less secure by a proof that P=NP, one of the central outstanding unsolved problems of computer science; many other encryption algorithms are likely to have their security brought into question if P=NP (it is widely believed that P≠NP). This very desirable proof of security is the basis of many a wishful, deluded, or merely mendacious (snake oil) cryptosystem.
Universal unbreakability
Claude Shannon's work can be interpreted as showing that any information-theoretically secure cipher will be effectively equivalent to the one-time pad algorithm. Hence one-time pads offer the best possible mathematical security of any encryption scheme, anywhere and anytime. An astonishing result!
At the same time, when implementing a one-time pad system, there are a number of problems and limitations which have the potential to greatly reduce security in practice.
Firstly, they require an amount of key material equal to the total volume of messages to be sent. It is truly difficult (in theory and in practice) to carry out each of the required steps:
Problems and limitations
There are several problems with using one-time pads in practice.
Key management is a tricky and crucial problem in every cryptosystem. For the one-time pad, the large quantity of key material required makes it still more problematic.
Also, 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 easily discover the pad (ie, the key material used).
- This will not matter if the attacker is just a passive eavesdropper. It gives him no plaintext he didn't already know, and neither Alice nor Bob will care that he learns a pad which will never be re-used.
- However, an active attacker who knows the plaintext can recover the pad (or some part of it) and then use it to encode whatever he chooses. If he can get his version delivered and accepted instead of yours, disaster may result. If you send "attack at dawn", the delivered message can be anything of 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, on perhaps only a portion of the message. If the guess were correct, this will work and the attacker's altered message can perhaps be substituted. If the guess is wrong, a garbled message is delivered, which may be itself helpful to the attacker.
The recent development of quantum cryptography has provided a way, theoretically, to securely transmit key material between two locations in such a way that no eavesdropper can determine their contents without the eavesdropping being both detectable and destroying the information being transferred. This assurance seems to be based on the fundamental nature of the universe (ie, some aspects of quantum mechanics). If practicable, this may eventually provide a better way to distribute one-time pad key material than anything known before. It is not yet clear whether this will ever be convenient enough to see widespread use, and so to be of any practical importance in using the one-time pad.
Historical uses
In a few diplomatic or espionage situations, the one-time pad is useful because it can be computed by hand with less effort than other high quality ciphers. Indeed, nearly all other high quality ciphers are entirely impractical without computers. In addition, in diplomatic situations, the key can be transmitted by diplomatic pouch.
It can be useful to use very simple "one time" signals—a signal, used only once, of "A" for "mission completed" and "B" for "mission failed" cannot be "decrypted" in any reasonable sense of the word. Understanding the message will require additional information, often 'depth' of repetition, or some traffic analysis. However, such strategies (though often used by real operatives) are not a cryptographic one-time pad in any significant sense. An example seems to have been the (used only once) message sent to President Truman at an end of WWII conference announcing the success of the Trinity test in New Mexico.
One-time pads have been used in special circumstances since the early 1900s. For instance, the Weimar Republic Diplomatic Service began using the method in about 1920. The breaking of poor Soviet cryptography by the British, with messages made public for political reasons in two instances in the 1920s, appear to have induced the USSR to adopt one-time pads for some purposes by around 1930. KGB spies are also known to have used pencil and paper one-time pads more recently. Examples include Colonel Rudolf Abel, who was arrested and convicted in New York City in the 1950s, and the 'Krogers' (ie, Morris and Lona Cohen), who were arrested and convicted of espionage in the United Kingdom in the early 1960s. Both were found with physical one-time pads in their possession.
The World War II voice scrambler SIGSALY was a one-time pad system. It added (analog) noise to the signal at one end and removed it at the other end. The noise was distributed to the channel ends in the form of large shellac records of which only two were made. There were both starting synchronization and longer term phase drift problems which arose and were solved before the system could be used.
Beginning in the late 1940s, U.S. and U.K. intelligence agencies were able to break some of the Soviet one-time pad traffic to Moscow during WWII as a result of errors made in generating and distributing the key material. One suggestion is that Moscow Centre personnel were somewhat rushed by the presence of German troops just outside Moscow in late 1941 and early 1942, and they produced more than one copy of same key material during that period. This decades-long effort was finally codenamed VENONA (BRIDE had been an earlier name); it produced a considerable amount of information, including more than a little about some of the Soviet atom spies. Even so, only a small percentage of the intercepted messages were either fully or partially decrypted (a few thousand out of several hundred thousand).
In 1945 the U.S. discovered that Canberra-Moscow messages were being encrypted first using a code-book and then using a one-time pad. However the one-time pad used was the same one used by Moscow for Washington, DC-Moscow messages. Combined with the fact that some of the Canberra-Moscow messages included known British government documents, this allowed some of the encrypted messages to be broken.
The Cold War "hot line" between the White House and the Kremlin is said to have used a one-time pad. The line was used so infrequently that key material exhaustion was a minor concern in comparison to the required security of messages. In addition, both sides had access to all the tools of modern nations when exchanging key material: armed couriers carrying diplomatic bags, military aircraft to carry the couriers, and so on.
Implementation pitfalls of one-time pads
If the key material is generated by a deterministic program then it is not actually random and should never be used in a one-time pad cipher. If so used, the method becomes a stream cipher; these usually employ a short key that is used to generate a long pseudorandom stream, which is then combined with the message using some such mechanism as those used in one-time pads. Stream ciphers can be secure in practice, but they cannot be absolutely secure in the same provable sense as the one-time pad. The Fish ciphers used by the German military in WWII turned out to be insecure stream ciphers, not practical automated one-time pads as their designers had intended. Bletchley Park broke one of them, the Lorenz cipher machine, regularly. No stream cipher has the absolute, information-theoretical security of a one-time pad, but there exist stream ciphers that so far are not publicly known to have been broken (except through access to the key).
The similarity between stream ciphers and one-time pads often leads the cryptographically unwary to invent insecure stream ciphers under the mistaken impression that they have developed a practical version of the one-time pad. An especially insecure approach is to use any of the random number generators that are distributed in many (perhaps most) computer programming language runtime support packages or as operating system system calls. These typically produce sequences that pass some (or even many) statistical tests, but are nonetheless more or less predictable. For some time the ANSI C standard restricted the C language random number routine output to a single precision integer, for most implementations that would be 16-bits, giving at most 32000 different values before repeating. This is entirely insecure being egregiously non random in the sense of being easily breakable by exhaustive test. They are useless for cryptographic purposes, specifically including the one-time pad. In particular, the relatively newly developed and widely admired Mersenne twister algorithm, while sufficiently "random" for most research or simulation uses, better than most any other such generator, and quite fast as well, should not be used to generate one-time pad key material. One reason this and similar algorithms are useful in research is that they are deterministic; another researcher can seed the algorithm with the same values and get the same results. This is a useful property for checking research results, but it is an extremely serious problem for cryptography.
As well, publicly known values such as the terminal digits of marathon race times, closing stock prices from any bourse however obscure, daily temperatures or atmospheric pressures, etc, though seemingly random, are predictable -- after the fact. Indeed, even truly random sequences which have been published cannot be used as they are now predictable if identified. An example is the Rand Corp 1950s publication of a million random number table; it has passed every statistical test for randomness thus far and is thought to be actually random. But, having been published, it is fully predictable. So are the digits of pi, e, phi, and other irrational, or transcendental, numbers; the sequences may be random (an open question, actually), but are fully predictable nonetheless.
In Linux (and some other Unix-like systems) the kernel's random number generator, /dev/random, uses environmental noise to generate random data and is better than many such system call designs. It is intended to be, and is widely thought to actually be, better than most such generators, and if so is rather closer to satisfactorily random. But this process will be slow on systems which have few usable noise sources. The Operating System also provides /dev/urandom which uses a deterministic algorithm to generate the data while environmental noise is unavailable. One-time pad key material generated in this way (ie, from deterministic random number generators) is dangerous, as discussed above, as all security of the ciphertext may be lost.
Though cryptographically secure pseudo-random number generators exist that serve as the basis for practically secure (insofar as publicly known thus far) stream ciphers, even these do not provide the random data required for one-time pad use. The information-theoretic security of a one-time pad is not trivially obtainable.
This is an Article on One-time pad. Page Contains Information, Facts Details or Explanation Guide About One-time pad See also
External links