History of invention
Frank Miller in 1882 was the first to describe the one-time pad system for securing telegraphy.
The next one-time pad system was electrical. In 1917, Gilbert Vernam (of AT&T Corporation) invented and later patented in 1919 (U.S. Patent 1,310,719) a cipher based on teleprinter technology. Each character in a message was electrically combined with a character on a paper tape key. Joseph Mauborgne (then a captain in the U.S. Army and later chief of the Signal Corps) recognized that the character sequence on the key tape could be completely random and that, if so, cryptanalysis would be more difficult. Together they invented the first one-time tape system.
The next development was the paper pad system. Diplomats had long used codes and ciphers for confidentiality and to minimize telegraph costs. For the codes, words and phrases were converted to groups of numbers (typically 4 or 5 digits) using a dictionary-like codebook. For added security, secret numbers could be combined with (usually modular addition) each code group before transmission, with the secret numbers being changed periodically (this was called superencryption). In the early 1920s, three German cryptographers (Werner Kunze, Rudolf Schauffler and Erich Langlotz), who were involved in breaking such systems, realized that they could never be broken if a separate randomly chosen additive number was used for every code group. They had duplicate paper pads printed with lines of random number groups. Each page had a serial number and eight lines. Each line had six 5-digit numbers. A page would be used as a work sheet to encode a message and then destroyed. The serial number of the page would be sent with the encoded message. The recipient would reverse the procedure and then destroy his copy of the page. The German foreign office put this system into operation by 1923.
A separate notion was the use of a one-time pad of letters to encode plaintext directly as in the example below. Leo Marks describes inventing such a system for the British Special Operations Executive during World War II, though he suspected at the time that it was already known in the highly compartmentalized world of cryptography, as for instance at Bletchley Park.
The final discovery was by Claude Shannon in the 1940s who recognized and proved the theoretical significance of the one-time pad system. Shannon delivered his results in a classified report in 1945, and published them openly in 1949. At the same time, Vladimir Kotelnikov had independently proven absolute security of the one-time pad; his results were delivered in 1941 in a report that apparently remains classified.
Suppose Alice wishes to send the message “HELLO” to Bob. Assume two pads of paper containing identical random sequences of letters were somehow previously produced and securely issued to both. Alice chooses the appropriate unused page from the pad. The way to do this is normally arranged for in advance, as for instance ‘use the 12th sheet on 1 May’, or ‘use the next available sheet for the next message’. The material on the selected 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. It is common, but not required, to assign each letter a numerical value: e.g. “A” is 0, “B” is 1, and so on. In this example, the technique is to combine the key and the message using modular addition. The numerical values of corresponding message and key letters are added together, modulo 26. If key material begins with “XMCKL” and the message is “HELLO”, then the coding would be done as follows:
H E L L O message
7 (H) 4 (E) 11 (L) 11 (L) 14 (O) message
+ 23 (X) 12 (M) 2 (C) 10 (K) 11 (L) key
= 30 16 13 21 25 message + key
= 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) message + key (mod 26)
E Q N V Z → ciphertext
If a number is larger than 26, then the remainder after subtraction of 26 is taken in modular arithmetic fashion. This simply means that if the computations “go past” Z, the sequence starts again at A.
The ciphertext to be sent to Bob is thus “EQNVZ”. Bob uses the matching key page and the same process, but in reverse, to obtain the plaintext. Here the key is subtracted from the ciphertext, again using modular arithmetic:
E Q N V Z ciphertext
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)
H E L L O → message
Similar to the above, if a number is negative then 26 is added to make the number positive.
Thus Bob recovers Alice’s plaintext, the message “HELLO”. Both Alice and Bob destroy the key sheet immediately after use, thus preventing reuse and an 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 classical one-time pad of espionage used actual pads of minuscule, easily concealed paper, a sharp pencil, and some mental arithmetic. The method can be implemented now as a software program, using data files as input (plaintext), output (ciphertext) and key material (the required random sequence). The XOR operation is often used to combine the plaintext and the key elements, and is especially attractive on computers since it is usually a native machine instruction and is therefore very fast. However, ensuring that the key material is actually random, is used only once, never becomes known to the opposition, and is completely destroyed after use is hard to do. The auxiliary parts of a software one-time pad implementation present real challenges: secure handling/transmission of plaintext, truly random keys, and one-time-only use of the key.
Attempt at cryptanalysis
To continue the example from above, suppose Eve intercepts Alice’s ciphertext: “EQNVZ”. If Eve had infinite computing power, she would instantly find that the key “XMCKL” would produce the plaintext “HELLO”, but she would also find that the key “TQURI” would produce 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 is possible to “decrypt” out of the ciphertext any message whatsoever with the same number of characters, simply by using a different key, and there is no information in the ciphertext which will allow Eve to choose among the various possible readings of the ciphertext.
One-time pads are “information-theoretically secure” in that the encrypted message (i.e., the ciphertext) provides no information about the original message to a cryptanalyst (except the maximum possible length of the message). This is a very strong notion of security first developed during WWII by Claude Shannon and proved, mathematically, to be true for the one-time pad by Shannon about the same time. His result was published in the Bell Labs Technical Journal in 1949. Properly used one-time pads are secure in this sense even against adversaries with infinite computational power.
Claude Shannon proved, using information theory considerations, that the one-time pad has a property he termed perfect secrecy; that is, the ciphertext C gives absolutely no additional information about the plaintext. This is because, given a truly random key which is used only once, a ciphertext can be translated into any plaintext of the same length, and all are equally likely. Thus, the a priori probability of a plaintext message M is the same as the a posteriori probability of a plaintext message M given the corresponding ciphertext. Mathematically, this is expressed as H(M)=H(M|C), where H(M) is the entropy of the plaintext and H(M|C) is the conditional entropy of the plaintext given the ciphertext C. Perfect secrecy is a strong notion of cryptanalytic difficulty.
Conventional symmetric encryption algorithms use complex patterns of substitution and transpositions. For the best of these currently in use, it is not known whether there can be a cryptanalytic procedure which can reverse (or, usefully, partially reverse) these transformations without knowing the key used during encryption. Asymmetric encryption algorithms depend on mathematical problems that are thought to be difficult to solve, such as integer factorization and discrete logarithms. However there is no proof that these problems are hard, and a mathematical breakthrough could make existing systems vulnerable to attack.
Given perfect secrecy, in contrast to conventional symmetric encryption, OTP is immune even to brute-force attacks. Trying all keys simply yields all plaintexts, all equally likely to be the actual plaintext. Even with known plaintext, like part of the message being known, brute-force attacks cannot be used, since an attacker is unable to gain any information about the parts of the key needed to decrypt the rest of the message.
Despite Shannon’s proof of its security, the one-time pad has serious drawbacks in practice:
• it requires perfectly random one-time pads, which is a non-trivial software requirement.
• secure generation and exchange of the one-time pad material, which must be at least as long as the message. (The security of the one-time pad is only as secure as the security of the one-time pad key-exchange). Non information-theoretic-secure ciphers typically only require a cryptographic key, a short string of characters, to be exchanged.
• careful treatment to make sure that it continues to remain secret from any adversary, and is disposed of correctly preventing any reuse in whole or part — hence “one time”. See data remanence for a discussion of difficulties in completely erasing computer media.
The theoretical perfect security of the one-time-pad applies only in a theoretically perfect setting; no real-world implementation of any cryptosystem can provide perfect security because practical considerations introduce potential vulnerabilities. These practical considerations of security and convenience have meant that the one-time-pad is, in practice, little-used. Implementation difficulties have led to one-time pad systems being broken, and are so serious that they have prevented the one-time pad from being adopted as a widespread tool in information security.
One-time pads solve few current practical problems in cryptography. High quality ciphers are widely available and their security is not considered a major worry at present. Such ciphers are almost always easier to employ than one-time pads; the amount of key material which must be properly generated and securely distributed is far smaller, and public key cryptography overcomes this problem.
Because the pad, like all shared secrets, must be passed and kept secure, and the pad has to be at least as long as the message, there is often no point in using one-time padding, as one can simply send the plain text instead of the pad (as both can be the same size and have to be sent securely). However, once a very long pad has been securely sent (e.g., a computer disk full of random data), it can be used for numerous future messages, until the sum of their sizes equals the size of the pad. Quantum key distribution also solves this problem.
Distributing very long one-time pad keys is inconvenient and usually poses a significant security risk. The pad is essentially the encryption key, but unlike keys for modern ciphers, it must be extremely long and is much too difficult for humans to remember. Storage media such as thumb drives, DVD-Rs or personal digital audio players can be used to carry a very large one-time-pad from place to place in a non-suspicious way, but even so the need to transport the pad physically is a burden compared to the key negotiation protocols of a modern public-key cryptosystem, and such media cannot reliably be erased securely by any means short of physical destruction (e.g., incineration). A 4.7 GB DVD-R full of one-time-pad data, if shredded into particles 1 mm² in size, leaves over 100 kibibits of (admittedly hard to recover, but not impossibly so) data on each particle. In addition, the risk of compromise during transit (for example, a pickpocket swiping, copying and replacing the pad) is likely much greater in practice than the likelihood of compromise for a cipher such as AES. Finally, the effort needed to manage one-time pad key material scales very badly for large networks of communicants—the number of pads required goes up as the square of the number of users freely exchanging messages. For communication between only two persons, or a star network topology, this is less of a problem.
The key material must be securely disposed of after use, to ensure the key material is never reused and to protect the messages sent. Because the key material must be transported from one endpoint to another, and persist until the message is sent or received, it can be more vulnerable to forensic recovery than the transient plaintext it protects (see data remanence).
As traditionally used, one-time pads provide no message authentication, the lack of which can pose a security threat in real-world systems. The straightforward XORing with the keystream, or the use of any invertible function known to the attacker, such as mod 26 addition, creates a potential vulnerability in message integrity. For example, an attacker who knows that the message contains “meet jane and me tomorrow at three thirty pm” at a particular point can replace that content by any other content of exactly the same length, such as “three thirty meeting is cancelled, stay home”, without having access to the one-time pad, a property of all stream ciphers known as malleability. See also stream cipher attack. Standard techniques to prevent this, such as the use of a message authentication code can be used along with a one-time pad system to prevent such attacks, as can classical methods such as variable length padding and Russian copulation, but they all lack the perfect security the OTP itself has. Universal hashing provides a way to authenticate messages up to an arbitrary security bound (i.e. for any p>0, a large enough hash ensures that even a computationally unbounded attacker’s likelihood of successful forgery is less than p), but this uses additional random data from the pad, and removes the possibility of implementing the system without a computer.
High-quality random numbers are difficult to generate. The random number generation functions in most programming language libraries are not suitable for cryptographic use. Even those generators that are suitable for normal cryptographic use, including /dev/random and many hardware random number generators, make some use of cryptographic functions whose security is unproven.
In particular, one-time use is absolutely necessary. If a one-time pad is used just twice, simple mathematical operations can reduce it to a running key cipher. If both plaintexts are in a natural language (e.g. English or Russian or Irish) then, even though both are secret, each stands a very high chance of being recovered by heuristic cryptanalysis, with possibly a few ambiguities. Of course the longer message can only be broken for the portion that overlaps the shorter message, plus perhaps a little more by completing a word or phrase. The most famous exploit of this vulnerability occurred with the VENONA project.