One time pads

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

The cipher is often described in such terms as "perfectly secure" and "provably, absolutely, unbreakable". This is quite correct in theory; the method has been mathematically proved unbreakable in an information-theoretic sense. 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).

Principle

The fundamental features of this cipher are that the sender and receiver each have a copy of an encryption key that is as long as the message to be encrypted, and which is discarded after it is used. That key must be truly random (i.e. not generated by a deterministic algorithm) and must remain unknown to any attacker. The key must never be reused as messages protected by the cipher become trivially breakable if two messages enciphered with the same key come into the hands of an attacker.

Example

Suppose Alice wishes to send the vital 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 send our example message, Alice chooses the appropriate unused page from the pad (arranged 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; for instance, if the key is the following:

and the message is "HELLO", then the numerical values of corresponding letters are added together, modulo 26, as follows:

(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:

(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 almost 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. 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. 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; other types of encryption algorithm might 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. 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.

Problems and limitations

There are several problems with using one-time pads 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:

1. Generate a large number of random bits,
2. Exchange the key securely between the users before sending a one-time enciphered message,
3. Keep both copies of the key material for each message secure until they are needed, and
4. Securely dispose of the key material after use, and thereby ensure the key material is not reused.

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

In general then, despite its theoretical perfection, the one-time-pad has very limited practical application.

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 for 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 (often used by real operatives) are not a cryptographic one-time pad in any significant sense.

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, resulting in the USSR adopting 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 in the United Kingdom in the 1960s. Both parties 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 December 1941, and they produced more than one copy of same key material during late 1941 and early 1942. This decades-long effort was codenamed VENONA; 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-Moscow messages. Combined with the fact that some of the Canberra-Moscow messages included known British government documents, this allowed for the encryption system to be broken for some messages.

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 is generated by a deterministic program then it is not actually random and should not be used in a one-time pad cipher. If so used, the method is called 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 a one-time pad. 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 Lorenz cipher machine messages regularly. No stream cipher has the absolute, information-theoretical security of a one-time pad, but there exist stream ciphers that so far have not 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 and in operating system call libraries. These typically produce sequences that pass some (or even many) statistical tests, but are nonetheless more or less predictable. This makes them 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, 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 random number generator, /dev/random, uses environmental noise to generate random data and can be used to generate one-time pad key material. It is intended to be, and is widely thought to actually be, better than most such generators. But this process may 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 all security of the ciphertext may be lost.

Though cryptographically secure pseudo-random number generators exist that serve as the basis for computationally secure 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.

See also

• Hardware random number generator