One-time pad

Sponsor with the world's largest charity for orphans

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.

The cipher is often described in such terms as "perfectly secure" and "provably, absolutely, unbreakable". The method has been proved unbreakable in an information-theoretic sense, but 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 the one-time pad being broken (for example, VENONA), and 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

1 Principle
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

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 or the cipher becomes trivially breakable if two messages enciphered with the same key come into the hands of an attacker.

Example

Two identical pads of paper with random letters are exchanged between sender and receiver. Later, when they wish to send a message, the sender uses the key in the pad to encipher a message. Each letter on the pad must be combined with its corresponding letter on the message. One technique is to XOR the first character of the key with the first character of the plaintext, the second character of the key with the second character of the plaintext, etc. Even a simple letter-substitution cipher, known since long before Julius Caesar's time, can be used. The encrypted message can then be sent to the receiver, even through a non secure channel. The receiver decrypts the message with the corresponding sheet of his copy of the pad. Both now destroy the used key page, having used it only one time; in thrillers, this is often by swallowing the key sheet. 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 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. 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.

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 by Claude Shannon in 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. Also, unlike many public-key algorithms, it would not be made less secure by an affirmative solution of P vs. NP, one of the central outstanding unsolved problems of computer science.

This very desirable proof is the basis of many a wishful, deluded, or merely mendacious snake oil (cryptography) 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. At the same time, when implementing the 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:

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

Key management is a tricky and crucial problem for every cryptosystem. For the one-time pad, the large quantity of key material required makes it still less tractable.

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.

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 is delivered. 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. 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, forced the USSR to improve their systems, and they seem to have used one-time pads for certain 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 Cohens, 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 initial 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, 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 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). 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 truly random and it should not be used in a one-time pad cipher. If so used, the method is called a stream cipher; these usually begin with a short key that is used to generate a long pseudorandom stream, which is then combined with the message using a mechanism similar to that 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 which so far have not been broken without having 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 pads. 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 statistical tests, but that are nonetheless highly predictable. This makes them useless for cryptographic purposes, specifically including the one time pad. In particular, the relatively newly developed Mersenne twister algorithm, while sufficiently "random" for almost any research or simulation use, 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.

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.

External links

Marcus Ranum's One Time Pad FAQ
The FreeS/WAN glossary entry with a discussion of OTP weaknesses
US patent 1310719 — Note that some browsers may not be able to display these TIFF images.