One-time pad
|
|
In cryptography, the one-time pad (OTP) is the only theoretically unbreakable method of encryption: the plaintext is combined with a random "pad" the same length as the plaintext. 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] (http://www.ranum.com/security/computer_security/papers/otp-faq)).
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 the only unbreakable cipher in an information-theoretic sense by Claude Shannon. However, it has drawbacks in practice: it requires perfectly random one-time pads, secure generation and exchange of the one-time pad material, which must be at least 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.
| Contents |
Principle
Each character in the message is combined with one from the (random, secret, and used only once) pad in the manner of a Vernam cipher. So 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. For this reason it is very important that the pad be protected (ie, secret), random (ie, unpredictable by anyone), and used only once, lest the cipher be easily compromised.
History
The history of the one time pad is marked by four separate but closely related discoveries.
The first one time pad system was electrical. In 1917, Gilbert Vernam (of AT&T) invented and later patented (Template:US patent) a cipher based on teletype machine technology. Each character in a message was combined with a character on a paper tape key. Captain Joseph Mauborgne (then a Captain in the United States Army and later chief of the Signal Corps) recognized that the character on the key tape could be completely random. Together they invented the first one time tape system.
The second development was the paper pad system. Diplomats had long used codes for confidentiality and to minimize telegraph costs. 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 added to each code group before transmission, with the secret numbers being changed periodically. 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 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 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 suspects it was already known in the highly compartmentalized world of cryptography.
The final discovery was by Claude Shannon in the 1940s who recognized and proved the theoretical significance of the one time pad system.
Example
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. When she wants to send the example message, 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 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. The 26-letter alphabet consisting of "A" through "Z" is used, and every letter is given a numerical value: "A" is 0, "B" is 1, and so on through "Z", equalling 25. 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,
X M C K L
and the message is "HELLO", then the coding is done 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)
Note that if a number is larger than 25, then in modular arithmetic fashion, 26 is subtracted from the number to make it less than 25.
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, again 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 classical one-time pad of espionage (which might have required actual pads of minuscule paper, a sharp pencil and the use of some mental arithmetic) can be translated into a software program using data files as input (plaintext) and output (ciphertext) and key material (the required random sequence). XOR can be used to combine the plaintext and the key. Ensuring that the key material is used only once and completely destroyed after use is not elementary. 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.
Security
One-time pads are "information-theoretically secure" in that 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 World War II. 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. 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 also 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 and many doubt this question has any practical relevance to cryptography).
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.
Controversy about one time pads in practice
PersonalStorageDevices.agr.jpg
Some argue that one-time pads are not practical for use in real-world systems:
- It is argued that one time pads solve few current practical problems in cryptography, that the security of modern ciphers is not considered a major worry at present and that such ciphers are almost always easier to employ than one time pads.
- All too often people are misled by the presence of "random number generator" functions in computer programming languages and assume they can be used to make an unbreakable encryption system using the one time pad principle. Such functions are almost always pseudorandom number generators, and cryptographically weak ones at that.
- Many vendors selling proprietary encryption schemes use "one time pad" as an advertising slogan. Such systems often fail to meet the exacting standards needed to be a true one time pad. Most are just another stream cipher, but have not been subject to extensive review of standard methods. See: snake oil cryptography.
- The key management needed for one time pads scales badly for large networks. The number of pads required goes up as the square of the number of users exchanging messages freely amongst each other. For communication between two persons or a star network topology, this is less of a problem.
- Most of the interesting new research and applications in cryptography lie in other areas, such as public key cryptography.
But many criticisms of the one time pad apply in some degree to other cryptosystems as well:
- One time pads require a large amount of trustworthy random key material, at least equal to the total volume of messages to be sent. Most modern cryptosystems require some random number generation for ongoing security, though in much smaller quantities. Solutions for properly producing small quantities often can be scaled up if copious sources of entropy are available. Common sound cards and webcams are good candidates to supply this entropy. See: hardware random number generator.
- The key material must be exchanged securely between the users before sending a one-time enciphered message. Advances in data storage make this more manageable than it was in the past. Devices like CD-Rs, DVD-Rs, USB keydrives, digital cameras, and personal digital audio players all can hold large amounts of one time pad material, yet attract little suspicion. 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. However, at present such devices require expensive, dedicated fibre optic channels and auditing them is not straightforward. It is not yet clear whether quantum transmission will ever be convenient enough to see widespread use, and so to be of any practical importance in using the one-time pad.
- Both copies of the key material for each message must be kept securely until they are used. Again, all encryption systems require some secret be kept. As noted above, storage of one time pads is no longer a problem in terms of physical size. While keys long enough to use with strong ciphers can be memorized as passphrases, most people find this onerous and choose weak passphrases. Passphrases are vulnerable as they are being entered and while they are in use. In some respects, short keys are more difficult to protect. See: side channel attack
- The key material must be securely disposed of after use, to ensure the key material is never reused and to protect the messages sent. Simple erasure of used keys is something computer are well suited to. Complete erasure that is immune to forensic recovery is a major problem, but one that applies as well to any system that stores sensitive plaintext. See also: data remanence
- Even if a one-time pad is implemented and used correctly, it is normally vulnerable to a substitution attack. If an attacker knows some plaintext and its position in a message and can mount a man in the middle attack, he can alter the meaning of the message. If one sends "attack at dawn", the delivered message can be anything of the same length -- perhaps "retreat to east" or "shoot generals". However this vulnerability applies to all stream ciphers. See: stream cipher attacks. The risk can be reduced by the traditional method of message padding or more modern techniques such as keyed message authentication codes. One simple (yet inefficient) scheme would be to use the message an index into a second one-time pad and transmit that part of the pad, destroying the rest unused. For example if you want to sign the digit 3 and your second one-time pad contains the string "knpqjejsma", you would transmit "q" as authentication. In this case the attacker would have a one in 26 chance of modifying the message without the receipient being able to detect it.
- The one time pad does not provide traffic-flow security. Again this is true of any crypto system unless additional measures are taken. An eavesdropper can determine when messages are sent, their sources, destinations and message lengths, allowing traffic analysis. Techniques to reduce this vulnerability include padding, steganography, continuous transmission and secret broadcast.
The one time pad does have a couple of real advantages:
- Future mathematical breakthroughs or practical quantum computing could render systems, now considered secure, vulnerable. One time pads implemented and used properly are provably safe.
- Most encryption systems available to the public are implemented in computer software. Computer operating systems today are horribly insecure, particularly when networked. The one time pad is the only practical strong encryption system that can be implemented entirely using pencil and paper. Making the required pad material by hand is tedious, but doable for protecting short text messages between two persons. On the other hand, carrying one time pad material can get you into very serious trouble in some countries.
- Making and using a one time pad has educational value. No special equipment is required and it serves as a good introduction to cryptographic ideas.
At the end of this controversy one may say: "I want to use a theoretically secure cipher, but my high throughput OTP RNG could get an undetected failure." "Why can't I use both kinds of cipher ?" (i.e. use a conventional cipher and then add an OTP layer).
- You can. Using 2 ciphers is called superencryption. Adding an OTP layer is a special case of superencryption where it is easy to prove that, provided you use keys that are statistically independents for each layer (e.g. independent RNGs), this combination would be at least as strong as the strongest layer.
Historical uses
In some diplomatic or espionage situations, the one-time pad is useful because it can be computed by hand with only pencil and paper. Indeed, nearly all other high quality ciphers are entirely impractical without computers. Spies can receive their pads in person from their "handlers." Embassies can receive theirs 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, and baseball coaches) 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. 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 U.S. and Britain used one time pad systems for their most sensitive traffic in World War II and through the 1950s. The NSA describes one time tape systems like SIGTOT and 5-UCO as being used for intelligence traffic until the introduction of the electronic cipher based KW-26. Leo Marks reports that the British Special Operations Executive used one time pads to encode traffic between its offices. One time pads for use with its overseas agents were introduced late in the war.
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 used a one-time pad. Providing an adequate supply of key material to cover communication in a crisis was a minor concern in comparison to the required security of messages and the reluctance of either country to reveal more sensitive cipher methods. 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.
During the 1983 Invasion of Grenada, U.S. forces found a supply of pairs of one time pad books in a Cuban warehouse. The continued presence of number stations on shortwave radio suggests one time pads are still used by spies.
True randomness requirements
In discussing the one time pad, two notions of security have to be kept distinct. The first is the theoretical security of the one-time pad system as proved by Shannon (Shannon security). The second is the security offered by state-of-the-art 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 later is unproven but relied upon by most governments to protect their most vital secrets (insofar as publicly known thus far).
Methods that offer empirical security but not Shannon security
If the key material is generated by a deterministic program then it is not random and the encryption system cannot claim the theoretical security of the one-time pad system. Instead it is called a stream cipher. These employ a short key that is used to seed 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.
However, if a modern so-called cryptographically secure pseudo-random number generators is used, it can form the basis for an empirically secure stream cipher. There are many well-vetted designs in the public domain, ranging from the simplicity of RC4 to using a top-secret rated block cipher like AES in counter mode. There is little reason to invent new stream ciphers.
Methods that offer neither empirical security nor Shannon security
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 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 16-bits, giving at most 32768 different values before repeating. This is entirely insecure and is easily breakable by exhaustive test. Standard computer random number generators are not suitable 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. The algorithm is deterministic and was not designed for cryptographic security.
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.
Achieving Shannon security
To achieve Shannon security, a source of perfectly unpredictable random data is needed. 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, real-world 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 one time 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. 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 Von Neumann whitening and can allow the practical generation of random data suitable for use in one time pads.
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 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, say from a sound card connected to a noise source, by writing to the device.
Linux also provides /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. One-time pad key material generated in this way (ie, from deterministic random number generators) lacks the information-theoretic security of a one-time pad. Yarrow offers at least as much strength as a block cipher based on 3DES.
A computer used to generate one time pad key material should never be connected to any computer network and preferably should not be used for any other purpose. Key material should be collected on new, blank media (e.g. floppy disks or CD-Rs). If paper pads are to be produced, the printer should be dedicated as well. The computer and any peripherals (the fewer the better) should be stored in a safe when not generating pads. This is a good use for an older laptop, purged and rebuilt with a fresh, traceable copy of an open source operating system such as Linux or BSD.
See also
External links
- Marcus Ranum's One-Time Pad FAQ (http://www.ranum.com/security/computer_security/papers/otp-faq/)
- A FAQ by a company selling one time pad software (http://www.vadiumtech.com/VDM3-RL.html)
- Arguments against one-time pad systems (http://www.schneier.com/crypto-gram-0210.html#7) — comments by Bruce Schneier
- The FreeS/WAN glossary entry (http://www.freeswan.org/freeswan_trees/freeswan-2.06/doc/glossary.html#OTP) with a discussion of OTP weaknesses
- US patent 1310719 (http://patft.uspto.gov/netacgi/nph-Parser?patentnumber=1310719) — Note that some browsers may not be able to display these TIFF images.
- A clock-jitter based One-Time Pad generator (http://www.fgerlach.com/clock_otp.html)de:One-Time-Pad