In cryptography, the onetime pad (OTP) is a type of encryption, and the only one which has been proven to be absolutely impossible to crack if used correctly. The plaintext is encrypted with a substitution cipher using a secret random key (or pad) as long as the plaintext, resulting in a ciphertext of random data. If the key is truly random, as large as the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key. It has also been proven that any cipher with the perfect secrecy property must use keys with effectively the same requirements as OTP keys^{[1]}. However, practical problems have prevented onetime pads from being widely used.
The onetime pad was invented in 1917 and patented a couple of years later. It is derived from the Vernam cipher, named after Gilbert Vernam, one of its inventors. Vernam's system was a cipher that combined a message with a key read from a paper tape loop. In its original form, Vernam's system was not unbreakable because the key could be reused. Onetime use came a little later when Joseph Mauborgne recognized that if the key tape were totally random, cryptanalytic difficulty would be increased.
The "pad" part of the name comes from early implementations where the key material was distributed as a pad of paper, so the top sheet could be easily torn off and destroyed after use. For easy concealment, the pad was sometimes reduced to such a small size that a powerful magnifying glass was required to use it. Photos accessible on the Internet show captured KGB pads that fit in the palm of one's hand,^{[2]} or in a walnut shell.^{[3]} To increase security, onetimepads were sometimes printed onto sheets of highly flammable nitrocellulose.
There is some ambiguity to the term due to the fact that some authors use the term "Vernam cipher" synonymously for the "onetimepad", while others refer to any additive stream cipher as a "Vernam cipher", including those based on a cryptographically secure pseudorandom number generator (CSPRNG).^{[4]}
Contents 
The history of the onetime pad is marked by four separate but closely related discoveries.
The first onetime pad system was electrical. In 1917, Gilbert Vernam (of AT&T) invented and later patented in 1919 (U.S. Patent 1,310,719) a cipher based on teletype machine technology. Each character in a message was electrically combined with a character on a paper tape key. Joseph Mauborgne (then Captain (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 onetime tape system.^{[4]}
The second 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 dictionarylike 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 up with lines of random number groups. Each page had a serial number and eight lines. Each line had six 5digit 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.^{[4]}
A separate notion was the use of a onetime 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.^{[5]}
The final discovery was by Claude Shannon in the 1940s who recognized and proved the theoretical significance of the onetime pad system. Shannon delivered his results in a classified report in 1945, and published them openly in 1949.^{[1]} At the same time, Vladimir Kotelnikov had independently proven absolute security of the onetime pad; his results were delivered in 1941 in a report that apparently remains classified.^{[6]}
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 25, then the remainder after subtraction of 26 is taken in modular arithmetic fashion. This simply means that if your computations "go past" Z, you start 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 onetime pads printed on tiny sheets of "flash paper"—paper chemically converted to nitrocellulose, which burns almost instantly and leaves no ash.^{[7]}
The classical onetime pad of espionage used actual pads of minuscule, easilyconcealed 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 onetime pad implementation present real challenges: secure handling/transmission of plaintext, truly random keys, and onetimeonly use of the key.
To continue the example from above, suppose 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", 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 ciphertextkey = 11 (L) 0 (A) 19 (T) 4 (E) 17 (R) ciphertextkey (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.
Onetime pads are "informationtheoretically secure" in that the encrypted message (i.e., the ciphertext) provides no information about the original message to a cryptanalyst (except the 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 of the onetime pad by Shannon about the same time. His result was published in the Bell Labs Technical Journal in 1949. Properly used onetime pads are secure in this sense even against adversaries with infinite computational power.
Claude Shannon proved, using information theory considerations, that the onetime pad has a property he termed perfect secrecy; that is, the ciphertext C gives absolutely no additional information about the plaintext. 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.^{[1]}
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.
Despite Shannon's proof of its security, the onetime pad has serious drawbacks in practice:
The theoretical perfect security of the onetimepad applies only in a theoretically perfect setting; no realworld 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 onetimepad is, in practice, littleused. Implementation difficulties have led to onetime pad systems being broken, and are so serious that they have prevented the onetime pad from being adopted as a widespread tool in information security.
Onetime 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 onetime pads; the amount of key material which must be properly generated and securely distributed is far smaller, and public key cryptography overcomes this problem.^{[8]}
Because the pad 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 onetime padding, as you can simply send the plain text instead of the pad (as both are 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.
Distributing very long onetime 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, DVDRs or personal digital audio players can be used to carry a very large onetimepad from place to place in a (somewhat) nonsuspicious way, but even so the need to transport the pad physically is a burden compared to the key negotiation protocols of a modern publickey cryptosystem, and such media cannot reliably be erased securely by any means short of physical destruction (eg, incineration). A 4.7 GB DVDR full of onetimepad data, if shredded into particles 1 mm² in size, leaves over 100 kilobits 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 onetime 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 exchanging messages freely amongst each other. For communication between only two persons, or a star network topology, this is somewhat 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 also: data remanence.
As traditionally used, onetime pads provide no message authentication, the lack of which can pose a security threat in realworld systems. The straightforward XORing with the keystream creates a potential vulnerability in message integrity especially simple to exploit — for example, an attacker who knows that the message contains "Meet Jane and me tomorrow at 3:30 pm" at a particular point can replace that content by any other content of the exact same length, such as "3:30 meeting is cancelled, stay home", without having access to the onetime pad. Standard techniques to prevent this, such as the use of a message authentication code, can be used along with a onetime pad system, but they 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 can be hard 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, onetime use is absolutely necessary. If a onetime 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 Gaelic) 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 is the VENONA project.^{[9]}
Despite its problems, the onetimepad retains some practical interest. In some hypothetical espionage situations, the onetime pad might be useful because it can be computed by hand with only pencil and paper. Indeed, nearly all other high quality ciphers (such as Solitaire) are entirely impractical without computers. Spies can receive their pads in person from their "handlers." In the modern world, however, computers (such as those embedded in personal electronic devices such as mobile phones) are so ubiquitous that possessing a computer suitable for performing conventional encryption (for example, a phone which can run concealed cryptographic software) will usually not attract suspicion.
Onetime pads have been used in special circumstances since the early 1900s. 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 U.S.S.R. to adopt onetime pads for some purposes by around 1930. KGB spies are also known to have used pencil and paper onetime 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 onetime pads in their possession.
A number of nations have used onetime pad systems for their sensitive traffic. Leo Marks reports that the British Special Operations Executive used onetime pads in World War II to encode traffic between its offices. Onetime pads for use with its overseas agents were introduced late in the war.^{[5]} Other onetime tape cipher machines include the British machines Rockex and Noreen.
The World War II voice scrambler SIGSALY was also a form of onetime 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 longerterm phase drift problems which arose and were solved before the system could be used.
The NSA describes onetime tape systems like SIGTOT and 5UCO as being used for intelligence traffic until the introduction of the electronic cipher based KW26 in 1957.^{[12]}
The hotline between Moscow and Washington D.C., established in 1963 after the Cuban missile crisis, used teleprinters protected by a commercial onetime tape system. Each country prepared the keying tapes used to encode its messages and delivered them via their embassy in the other country. A unique advantage of the OTP in this case was that neither country had to reveal more sensitive encryption methods to the other.^{[13]}
During the 1983 Invasion of Grenada, U.S. forces found a supply of pairs of onetime pad books in a Cuban warehouse.
The British Army's BATCO tactical communication code is a pencilandpaper onetimepad system. Key material is provided on paper sheets that are kept in a special plastic wallet with a sliding pointer that indicates the last key used. New sheets are provided daily (though a small series of "training BATCO" is usually recycled on exercise) and the old ones destroyed. BATCO is used on battlefield voice nets; the most sensitive portions of a message (typically grid references) are encoded and the ciphertext is read out letter by letter.
A related notion is the onetime code—a signal, used only once, eg "Alpha" for "mission completed" and "Bravo" 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, and baseball coaches) are not a cryptographic onetime pad in any significant sense.
While onetime pads provide perfect secrecy if generated and used properly, small mistakes can lead to successful cryptanalysis:
In discussing the onetime pad, two notions of security have to be kept distinct. The first is the perfect secrecy of the onetime pad system as proved by Shannon (Shannon security). The second is the security offered by stateoftheart ciphers (e.g. AES) designed with principles learned in the long history of code breaking and subjected to extensive testing in a standardization process, either in public or by a top notch security service (empirical security). The former is mathematically proven, subject to the practical availability of random numbers. The latter is unproven but relied upon by most governments to protect their most vital secrets (insofar as publicly known thus far).
If the key material is generated by a deterministic program, then it is not random and the encryption system no longer has perfect secrecy. Such a system is called a stream cipher. These generally use a short key which is used to seed a long pseudorandom stream, which is then combined with the message using some such mechanism as those used in onetime pads (eg, XOR). Stream ciphers can be secure in practice, but they cannot achieve perfect secrecy like the onetime pad does.
The Fish ciphers used by the German military in WWII turned out to be insecure stream ciphers, not practical automated onetime pads as their designers had intended. Bletchley Park broke one of them, the Lorenz cipher machine, regularly.
However, if a modern socalled cryptographically secure pseudorandom number generator is used, it can form the basis for an empirically secure stream cipher. There are many wellvetted designs in the public domain, ranging from the simplicity of RC4 to using a block cipher like AES in counter mode. There would appear to be little reason to invent new stream ciphers, yet it has long been thought that NSA and its comparable agencies devote considerable effort to stream ciphers for their government customers.
The similarity between stream ciphers and onetime pads often leads the cryptographically unwary to invent insecure stream ciphers under the mistaken impression that they have developed a practical version of the onetime 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 breakable by cryptoanalytic techniques. 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 16bits, giving at most 32768 different values before repeating (assuming a cyclical algorithm, as is common, but not mandatory). This is entirely insecure and is easily breakable by exhaustive test (for perspective, a 1 GHz computer which takes 10,000 clock cycles to check an offset within the RNG's cycle would take under a third of a second to check every possible offset). Standard computer random number generators are not suitable for cryptographic purposes, specifically including the onetime pad. In particular, the relatively newly developed and widely admired Mersenne twister algorithm, while sufficiently "random" for most research or simulation uses, better than almost any other such generator, and quite fast as well, should not be used to generate onetime pad key material. The algorithm is deterministic and was not designed for cryptographic security. Some programs use a usersupplied key to uniquely scatter the output of a pseudorandom number generator in a way that requires knowledge of the key and any initialization vectors used, to predict the final output.
As well, publicly known values such as the terminal digits of marathon race times, closing stock prices from any source 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 Corporation's 1950s publication of a million random digits; 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 statistically random (an open question, actually), but are fully predictable nonetheless.
To achieve Shannon security, a source of perfectly unpredictable random data is needed. Typically these random bits are produced by a hardware random number generator.
One theoretical basis for the physical existence of unpredictability is quantum mechanics. Its assertions of unpredictability are subject to experimental test. See: Bell test experiments. Another basis is the theory of unstable dynamical systems and chaos theory. These theories suggest that even in the deterministic world of Newtonian mechanics, realworld systems evolve in ways that cannot be predicted in practice because one would need to know the initial conditions to an accuracy that grows exponentially over time.
For use in a onetime pad, data should exhibit perfect randomness. Most practical sources exhibit some imperfection or bias. The quality of randomness is measured by entropy. A perfectly random bit has an entropy of one bit. An idea due to Von Neumann is to use an algorithm to combine multiple, imperfectly random bits, each with entropy less than one, to create a single bit with entropy equal to one. This process is called entropy distillation or entropy extraction. Von Neumann proposed the following method, called "Von Neumann whitening":^{[15]}
Input bits  Output 

00  No output. 
01  Output "0" bit. 
10  Output "1" bit. 
11  No output. 
This will produce uniformly random output bits if the input bits are statistically independent and all drawn from the same distribution. However, that is not a realistic assumption since most physical randomness sources may have some correlation in the output, and the distribution may change with the device temperature, etc. In 2003, Boaz Barak, Ronen Shaltiel, and Eran Tromer stated some reasonable security criteria for entropy distillation and constructed an algorithm for doing it.^{[16]}
In many Unixlike 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 attempts to estimate the amount of entropy it collects and blocks if the entropy pool is exhausted. 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. It can, however, be fed additional entropy by reading from an attached noise generating device.
Many Unixlike systems also provide /dev/urandom which uses a deterministic algorithm to generate the data whenever environmental noise is unavailable. Improved designs, such as the Yarrow algorithm, are available. Onetime pad key material generated in this way (ie, from deterministic random number generators) lacks the informationtheoretic security of a onetime pad. Yarrow offers at least as much strength as a block cipher based on triple DES.
If a computer used for onetime pad generation is compromised, by a computer virus or other malware or by an adversary gaining physical access, the software can be modified to leak the pad data or generate apparently random data that is in fact predictable. See random number generator attack. One way to reduce this risk is to generate pads on a machine that is never connected to any computer network and preferably not used for any other purpose. Collecting key material on new, blank media (e.g. floppy disks or CDRs) eliminates another route for malware infection. If paper pads are to be produced, the printer is best dedicated as well. One approach might be to use an older laptop for OTP generation, purged and rebuilt with a fresh, traceable copy of an open source operating system, such as Linux or BSD. The smaller size would allow it to be easily locked up in a safe when not in use.
Onetime pads were originally made without the use of a computer and this is still possible today. The process can be tedious, but if done correctly and the pad used only once, the result is unbreakable.
There are two components needed to make a onetime pad: a way to generate letters at random and a way to record two copies of the result. The traditional way to do the latter was to use a typewriter and carbon paper. The carbon paper and typewriter ribbon would then be destroyed since it may be possible for the pad data to be recovered from them. As typewriters have become scarce, it is also acceptable to hand write the letters neatly in groups of five on two part carbonless copy paper sheets, which can be purchased at office supply stores. Each sheet should be given a serial number or some other unique marking.
The simplest way to generate random letters is to obtain 26 identical objects with each letter of the alphabet marked on one object. Tiles from the game Scrabble can be used (as long as only one of each letter is selected). Kits for making name charm bracelets are another possibility. One can also write the letters on 26 otherwise identical coins with a marking pen. The objects are placed in a box or cup and shaken vigorously, then one object is withdrawn and its letter is recorded. The object is returned to the box and the process is repeated.

