One-time pad
One-time pad
Main page
2319943

One-time pad

logo
Community Hub0 subscribers
Read side by side
from Wikipedia
A format of one-time pad used by the U.S. National Security Agency, code named DIANA. The table on the right is an aid for converting between plaintext and ciphertext using the characters at left as the key.

The one-time pad (OTP) is an encryption technique that cannot be cracked in cryptography. It requires the use of a single-use pre-shared key that is larger than or equal to the size of the message being sent. In this technique, a plaintext is paired with a random secret key (also referred to as a one-time pad). Then, each bit or character of the plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition.[1]

The resulting ciphertext is impossible to decrypt or break if the following four conditions are met:[2][3]

  1. The key must be at least as long as the plaintext.
  2. The key must be truly random.
  3. The key must never be reused in whole or in part.
  4. The key must be kept completely secret by the communicating parties.

These requirements make the OTP the only known encryption system that is mathematically proven to be unbreakable under the principles of information theory.[4]

Digital versions of one-time pad ciphers have been used by nations for critical diplomatic and military communication, but the problems of secure key distribution make them impractical for many applications.

First described by Frank Miller in 1882,[5][6] the one-time pad was re-invented in 1917. On July 22, 1919, U.S. Patent 1,310,719 was issued to Gilbert Vernam for the XOR operation used for the encryption of a one-time pad.[7] One-time use came later, when Joseph Mauborgne recognized that if the key tape were totally random, then cryptanalysis would be impossible.[8] To increase security, one-time pads were sometimes printed onto sheets of highly flammable nitrocellulose, so that they could easily be burned after use.

History

[edit]

Frank Miller in 1882 was the first to describe the one-time pad system for securing telegraphy.[6][9]

The next one-time pad system was electrical. In 1917, Gilbert Vernam (of AT&T Corporation) invented[10] 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 punched 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.[11]

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.[11]

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.[12]

The final discovery was made by information theorist 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.[4] At the same time, Soviet information theorist Vladimir Kotelnikov had independently proved the absolute security of the one-time pad; his results were delivered in 1941 in a report that apparently remains classified.[13]

There also exists a quantum analogue of the one time pad, which can be used to exchange quantum states along a one-way quantum channel with perfect secrecy, which is sometimes used in quantum computing. It can be shown that a shared secret of at least 2n classical bits is required to exchange an n-qubit quantum state along a one-way quantum channel (by analogue with the result that a key of n bits is required to exchange an n bit message with perfect secrecy). A scheme proposed in 2000 achieves this bound. One way to implement this quantum one-time pad is by dividing the 2n bit key into n pairs of bits. To encrypt the state, for each pair of bits i in the key, one would apply an X gate to qubit i of the state if and only if the first bit of the pair is 1, and apply a Z gate to qubit i of the state if and only if the second bit of the pair is 1. Decryption involves applying this transformation again, since X and Z are their own inverses. This can be shown to be perfectly secret in a quantum setting.[14]

Example

[edit]

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, not unlike the Vigenère cipher. The numerical values of corresponding message and key letters are added together, modulo 26. So, 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 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 zero or higher.

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.[15]

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 exclusive or (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. It is, however, difficult to ensure that the key material is actually random, is used only once, never becomes known to the opposition, and is completely destroyed after use. 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

[edit]

To continue the example from above, suppose Eve intercepts Alice's ciphertext: EQNVZ. If Eve tried every possible key, she would 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 that will allow Eve to choose among the various possible readings of the ciphertext.[16]

If the key is not truly random, it is possible to use statistical analysis to determine which of the plausible keys is the "least" random and therefore more likely to be the correct one. If a key is reused, it will noticeably be the only key that produces sensible plaintexts from both ciphertexts (the chances of some random incorrect key also producing two sensible plaintexts are very slim).

Perfect secrecy

[edit]

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[note 1] 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 at about the same time. His result was published in the Bell System Technical Journal in 1949.[17] If properly used, one-time pads are secure in this sense even against adversaries with infinite computational power.

Shannon proved, using information theoretic 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.[note 2] This is because (intuitively), given a truly uniformly random key that 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.

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 that can efficiently reverse (or even 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 or the discrete logarithm. However, there is no proof that these problems are hard, and a mathematical breakthrough could make existing systems vulnerable to attack.[note 3]

Given perfect secrecy, in contrast to conventional symmetric encryption, the one-time pad is immune even to brute-force attacks. Trying all keys simply yields all plaintexts, all equally likely to be the actual plaintext. Even with a partially known plaintext, 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. The parts of the plaintext that are known will reveal only the parts of the key corresponding to them, and they correspond on a strictly one-to-one basis; a uniformly random key's bits will be independent.

Quantum cryptography and post-quantum cryptography involve studying the impact of quantum computers on information security. Quantum computers have been shown by Peter Shor and others to be much faster at solving some problems that the security of traditional asymmetric encryption algorithms depends on. The cryptographic algorithms that depend on these problems' difficulty would be rendered obsolete with a powerful enough quantum computer. One-time pads, however, would remain secure, as perfect secrecy does not depend on assumptions about the computational resources of an attacker.

Problems

[edit]

Despite Shannon's proof of its security, the one-time pad has serious drawbacks in practice because it requires:

  • Truly random, as opposed to pseudorandom, one-time pad values, which is a non-trivial requirement. Random number generation in computers is often difficult, and pseudorandom number generators are often used for their speed and usefulness for most applications. True random number generators exist, but are typically slower and more specialized.
  • Secure generation and exchange of the one-time pad values, which must be at least as long as the message. This is important because the security of the one-time pad depends on the security of the one-time pad exchange. If an attacker is able to intercept the one-time pad value, they can decrypt messages sent using the one-time pad.[16]
  • Careful treatment to make sure that the one-time pad values continue to remain secret and are disposed of correctly, preventing any reuse (partially or entirely)—hence "one-time". Problems with data remanence can make it difficult to completely erase computer media.

One-time pads solve few current practical problems in cryptography. High-quality ciphers are widely available and their security is not currently considered a major worry.[18] Such ciphers are almost always easier to employ than one-time pads because the amount of key material that must be properly and securely generated, distributed and stored is far smaller.[16] Additionally, public key cryptography overcomes the problem of key distribution.

True randomness

[edit]

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, may make some use of cryptographic functions whose security has not been proven. An example of a technique for generating pure randomness is measuring radioactive emissions.[19]

In particular, one-time use is absolutely necessary. For example, if and represent two distinct plaintext messages and they are each encrypted by a common key , then the respective ciphertexts are given by:

where means XOR. If an attacker were to have both ciphertexts and , then simply taking the XOR of and yields the XOR of the two plaintexts . (This is because every bitstream XORed with itself gives 0, the identity element of XOR) is then the equivalent of a running key cipher.[citation needed]

If both plaintexts are in a natural language (e.g., English or Russian), each stands a very high chance of being recovered by heuristic cryptanalysis, with possibly a few ambiguities. Of course, a longer message can only be broken for the portion that overlaps a 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.[20]

Key distribution

[edit]

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 a one-time pad, 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).[16] 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 the messages' sizes equals the size of the pad. Quantum key distribution also proposes a solution to this problem, assuming fault-tolerant quantum computers.

Distributing very long one-time pad keys is inconvenient and usually poses a significant security risk.[2] The pad is essentially the encryption key, but unlike keys for modern ciphers, it must be extremely long and is far 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 the need to transport the pad physically is a burden compared to the key negotiation protocols of a modern public-key cryptosystem. 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 mm2 (0.0016 sq in) in size, leaves over 4 megabits of data on each particle. [citation needed] In addition, the risk of compromise during transit (for example, a pickpocket swiping, copying and replacing the pad) is likely to be 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.[2] 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 (because of possible data remanence).

Authentication

[edit]

As traditionally used, one-time pads provide no message authentication, the lack of which can pose a security threat in real-world systems. For example, an attacker who knows that the message contains "meet jane and me tomorrow at three thirty pm" can derive the corresponding codes of the pad directly from the two known elements (the encrypted text and the known plaintext). The attacker can then replace that text by any other text of exactly the same length, such as "three thirty meeting is cancelled, stay home". The attacker's knowledge of the one-time pad is limited to this byte length, which must be maintained for any other content of the message to remain valid. This is different from malleability[21] where the plaintext is not necessarily known. Without knowing the message, the attacker can also flip bits in a message sent with a one-time pad, without the recipient being able to detect it. Because of their similarities, attacks on one-time pads are similar to attacks on stream ciphers.[22]

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 some of these techniques remove the possibility of implementing the system without a computer.

Common implementation errors

[edit]

Due to its relative simplicity of implementation, and due to its promise of perfect secrecy, one-time-pad enjoys high popularity among students learning about cryptography, especially as it is often the first algorithm to be presented and implemented during a course. Such "first" implementations often break the requirements for information theoretical security in one or more ways:

  • The pad is generated via some algorithm, that expands one or more small values into a longer "one-time-pad". This applies equally to all algorithms, from insecure basic mathematical operations like square root decimal expansions, to complex, cryptographically secure pseudo-random random number generators (CSPRNGs). None of these implementations are one-time-pads, but stream ciphers by definition. All one-time pads must be generated by a non-algorithmic process, e.g. by a hardware random number generator.
  • The pad is exchanged using non-information-theoretically secure methods. If the one-time-pad is encrypted with a non-information theoretically secure algorithm for delivery, the security of the cryptosystem is only as secure as the insecure delivery mechanism. A common flawed delivery mechanism for one-time-pad is a standard hybrid cryptosystem that relies on symmetric key cryptography for pad encryption, and asymmetric cryptography for symmetric key delivery. Common secure methods for one-time pad delivery are quantum key distribution, a sneakernet or courier service, or a dead drop.
  • The implementation does not feature an unconditionally secure authentication mechanism such as a one-time MAC.
  • The pad is reused (exploited during the Venona project, for example).[23]
  • The pad is not destroyed immediately after use.

Uses

[edit]

Applicability

[edit]

Despite its problems, the one-time-pad retains some practical interest. In some hypothetical espionage situations, the one-time pad might be useful because encryption and decryption can be computed by hand with only pencil and paper. Nearly all other high quality ciphers are entirely impractical without computers. In the modern world, however, computers (such as those embedded in mobile phones) are so ubiquitous that possessing a computer suitable for performing conventional encryption (for example, a phone that can run concealed cryptographic software) will usually not attract suspicion.

  • The one-time-pad is the optimum cryptosystem with theoretically perfect secrecy.[17]
  • The one-time-pad is one of the most practical methods of encryption where one or both parties must do all work by hand, without the aid of a computer. This made it important in the pre-computer era, and it could conceivably still be useful in situations where possession of a computer is illegal or incriminating or where trustworthy computers are not available.
  • One-time pads are practical in situations where two parties in a secure environment must be able to depart from one another and communicate from two separate secure environments with perfect secrecy.
  • The one-time-pad can be used in superencryption.[24]
  • The algorithm most commonly associated with quantum key distribution is the one-time pad.[25]
  • The one-time pad is mimicked by stream ciphers.[22]
  • Numbers stations often send messages encrypted with a one-time pad.[2]

Quantum and post-quantum cryptography

[edit]

A common use of the one-time pad in quantum cryptography is being used in association with quantum key distribution (QKD). QKD is typically associated with the one-time pad because it provides a way of distributing a long shared secret key securely and efficiently (assuming the existence of practical quantum networking hardware). A QKD algorithm uses properties of quantum mechanical systems to let two parties agree on a shared, uniformly random string. Algorithms for QKD, such as BB84, are also able to determine whether an adversarial party has been attempting to intercept key material, and allow for a shared secret key to be agreed upon with relatively few messages exchanged and relatively low computational overhead. At a high level, the schemes work by taking advantage of the destructive way quantum states are measured to exchange a secret and detect tampering. In the original BB84 paper, it was proven that the one-time pad, with keys distributed via QKD, is a perfectly secure encryption scheme.[25] However, this result depends on the QKD scheme being implemented correctly in practice. Attacks on real-world QKD systems exist. For instance, many systems do not send a single photon (or other object in the desired quantum state) per bit of the key because of practical limitations, and an attacker could intercept and measure some of the photons associated with a message, gaining information about the key (i.e. leaking information about the pad), while passing along unmeasured photons corresponding to the same bit of the key.[26] Combining QKD with a one-time pad can also loosen the requirements for key reuse. In 1982, Bennett and Brassard showed that if a QKD protocol does not detect that an adversary was trying to intercept an exchanged key, then the key can safely be reused while preserving perfect secrecy.[27]

The one-time pad is an example of post-quantum cryptography, because perfect secrecy is a definition of security that does not depend on the computational resources of the adversary. Consequently, an adversary with a quantum computer would still not be able to gain any more information about a message encrypted with a one time pad than an adversary with just a classical computer.

Historical uses

[edit]

One-time pads have been used in special circumstances since the early 1900s. In 1923, they were employed for diplomatic communications by the German diplomatic establishment.[28] 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 (ARCOS case), appear to have caused the Soviet Union 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' (i.e., 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.

A number of nations have used one-time pad systems for their sensitive traffic. Leo Marks reports that the British Special Operations Executive used one-time pads in World War II to encode traffic between its offices. One-time pads for use with its overseas agents were introduced late in the war.[12] A few British one-time tape cipher machines include the Rockex and Noreen. The German Stasi Sprach Machine was also capable of using one time tape that East Germany, Russia, and even Cuba used to send encrypted messages to their agents.[29]

The World War II voice scrambler SIGSALY was also a form of one-time system. It added 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 that were manufactured in unique pairs. There were both starting synchronization and longer-term phase drift problems that arose and had to be solved before the system could be used.[30]

The hotline between Moscow and Washington, D.C., established in 1963 after the 1962 Cuban Missile Crisis, used teleprinters protected by a commercial one-time 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.[31]

U.S. Army Special Forces used one-time pads in Vietnam. By using Morse code with one-time pads and continuous wave radio transmission (the carrier for Morse code), they achieved both secrecy and reliable communications.[32]

Starting in 1988, the African National Congress (ANC) used disk-based one-time pads as part of a secure communication system between ANC leaders outside South Africa and in-country operatives as part of Operation Vula,[33] a successful effort to build a resistance network inside South Africa. Random numbers on the disk were erased after use. A Belgian flight attendant acted as courier to bring in the pad disks. A regular resupply of new disks was needed as they were used up fairly quickly. One problem with the system was that it could not be used for secure data storage. Later Vula added a stream cipher keyed by book codes to solve this problem.[34]

A related notion is the one-time code—a signal, used only once; e.g., "Alpha" for "mission completed", "Bravo" for "mission failed" or even "Torch" for "Allied invasion of French Northern Africa"[35] 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)[36] are not a cryptographic one-time pad in any significant sense.

NSA

[edit]

At least into the 1970s, the U.S. National Security Agency (NSA) produced a variety of manual one-time pads, both general purpose and specialized, with 86,000 one-time pads produced in fiscal year 1972. Special purpose pads were produced for what the NSA called "pro forma" systems, where "the basic framework, form or format of every message text is identical or nearly so; the same kind of information, message after message, is to be presented in the same order, and only specific values, like numbers, change with each message." Examples included nuclear launch messages and radio direction finding reports (COMUS).[37]: pp. 16–18 

General purpose pads were produced in several formats, a simple list of random letters (DIANA) or just numbers (CALYPSO), tiny pads for covert agents (MICKEY MOUSE), and pads designed for more rapid encoding of short messages, at the cost of lower density. One example, ORION, had 50 rows of plaintext alphabets on one side and the corresponding random cipher text letters on the other side. By placing a sheet on top of a piece of carbon paper with the carbon face up, one could circle one letter in each row on one side and the corresponding letter on the other side would be circled by the carbon paper. Thus one ORION sheet could quickly encode or decode a message up to 50 characters long. Production of ORION pads required printing both sides in exact registration, a difficult process, so NSA switched to another pad format, MEDEA, with 25 rows of paired alphabets and random characters. (See Commons:Category:NSA one-time pads for illustrations.)

The NSA also built automated systems for the "centralized headquarters of CIA and Special Forces units so that they can efficiently process the many separate one-time pad messages to and from individual pad holders in the field".[37]: pp. 21–26 

During World War II and into the 1950s, the U.S. made extensive use of one-time tape systems. In addition to providing confidentiality, circuits secured by one-time tape ran continually, even when there was no traffic, thus protecting against traffic analysis. In 1955, NSA produced some 1,660,000 rolls of one time tape. Each roll was 8 inches in diameter, contained 100,000 characters, lasted 166 minutes and cost $4.55 to produce. By 1972, only 55,000 rolls were produced, as one-time tapes were replaced by rotor machines such as SIGTOT, and later by electronic devices based on shift registers.[37]: pp. 39–44  The NSA describes one-time tape systems like 5-UCO and SIGTOT as being used for intelligence traffic until the introduction of the electronic cipher based KW-26 in 1957.[38]

Exploits

[edit]

While one-time pads provide perfect secrecy if generated and used properly, small mistakes can lead to successful cryptanalysis:

  • In 1944–1945, the U.S. Army's Signals Intelligence Service was able to solve a one-time pad system used by the German Foreign Office for its high-level traffic, codenamed GEE.[39] GEE was insecure because the pads were not sufficiently random—the machine used to generate the pads produced predictable output.
  • In 1945, the US discovered that CanberraMoscow 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, D.C.–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.[citation needed]
  • One-time pads were employed by Soviet espionage agencies for covert communications with agents and agent controllers. Analysis has shown that these pads were generated by typists using actual typewriters. This method is not truly random, as it makes the pads more likely to contain certain convenient key sequences more frequently. This proved to be generally effective because the pads were still somewhat unpredictable because the typists were not following rules, and different typists produced different patterns of pads. Without copies of the key material used, only some defect in the generation method or reuse of keys offered much hope of cryptanalysis. Beginning in the late 1940s, US and UK 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 the 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. Even so, only a small percentage of the intercepted messages were either fully or partially decrypted (a few thousand out of several hundred thousand).[23]
  • The one-time tape systems used by the U.S. employed electromechanical mixers to combine bits from the message and the one-time tape. These mixers radiated considerable electromagnetic energy that could be picked up by an adversary at some distance from the encryption equipment. This effect, first noticed by Bell Labs during World War II, could allow interception and recovery of the plaintext of messages being transmitted, a vulnerability code-named Tempest.[37]: pp. 89 ff 

See also

[edit]

Notes

[edit]

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia
from Grokipedia
The one-time pad (OTP) is a symmetric-key encryption method that achieves perfect secrecy by combining plaintext with a truly random key of equal length using bitwise XOR (or modular addition in other variants), where the key is used only once and securely distributed beforehand.[1][2] Developed initially by Gilbert Vernam in 1917 for telegraphic use and refined by Joseph Mauborgne to ensure non-repeating randomness, the OTP was later formalized as theoretically unbreakable by Claude Shannon in 1949, who proved that under ideal conditions—no key reuse, perfect randomness, and secrecy—the ciphertext is indistinguishable from random noise, providing information-theoretic security independent of computational power.[3][4][5] Despite its unmatched security guarantees, the one-time pad's practical deployment is severely limited by the necessity of generating, storing, and distributing keys as voluminous as the messages they protect, rendering it inefficient for modern high-volume communications and suitable primarily for low-bandwidth, high-stakes scenarios such as espionage or diplomatic traffic.[5] Violations of its strict protocols, such as key reuse or insufficient randomness, have historically compromised systems purporting to use OTP, as evidenced in cryptanalytic successes against imperfect implementations, underscoring that its invulnerability hinges on flawless adherence to first-principles requirements rather than mere algorithmic design.[2][6]

Fundamentals

Definition and Principles

The one-time pad (OTP) is a symmetric-key encryption technique in which a plaintext message of length n bits is encrypted by combining it bitwise with a secret key of exactly the same length, typically using the exclusive-or (XOR) operation, to produce a ciphertext of identical length.[7] The key must be generated uniformly at random from the set of all possible n-bit strings, independent of the plaintext, and must never be reused for any other message.[6] This method was formalized in its modern binary form by Gilbert Vernam in 1917, though its theoretical foundations were later established by Claude Shannon.[8] The core principles of the OTP rest on four strict conditions for achieving information-theoretic security: the key must be truly random and unpredictable; it must match the message length exactly; it must be used only once; and it must remain secret from adversaries, with secure distribution and disposal after use.[9] Violation of any condition compromises security—for instance, key reuse allows statistical attacks via XOR of ciphertexts to recover plaintext differences, as c₁ ⊕ c₂ = (p₁ ⊕ k) ⊕ (p₂ ⊕ k) = p₁ ⊕ p₂.[10] These principles ensure that the ciphertext is indistinguishable from random noise, providing no partial information about the plaintext even to an adversary with unlimited computational resources.[6] The OTP realizes perfect secrecy, as defined by Shannon in his 1949 paper "Communication Theory of Secrecy Systems," where the mutual information between plaintext and ciphertext is zero: for every possible plaintext m and ciphertext c, the posterior probability Pr[M = m | C = c] equals the prior Pr[M = m].[8] This holds because encryption with a random key maps each plaintext to every possible ciphertext with equal probability, rendering cryptanalysis impossible without the key.[7] Shannon proved that perfect secrecy requires the key space to be at least as large as the message space, a condition uniquely met by the OTP among practical ciphers.[10]

Encryption and Decryption Process

The encryption process for a one-time pad begins with a plaintext message represented as a string of symbols, typically converted to binary bits or numeric values matching the key's domain. A truly random key, equal in length to the plaintext and used only once, is generated and securely shared beforehand. Each ciphertext symbol $ c_i $ is then produced by applying a reversible bitwise operation—most commonly the exclusive OR (XOR, denoted $ \oplus $) for binary data—to the corresponding plaintext symbol $ p_i $ and key symbol $ k_i $: $ c_i = p_i \oplus k_i $.[8][7] For non-binary implementations, such as alphabetic text, the operation may instead use modular addition (e.g., modulo 26 for A-Z), where $ c_i = (p_i + k_i) \mod 26 $, with symbols mapped to integers (A=0, B=1, etc.).[11] The resulting ciphertext appears as random noise, indistinguishable from pure randomness when the key is uniformly random.[12] Decryption reverses the process using the identical key and operation, exploiting the self-inverse property of XOR or modular subtraction. The recipient computes $ p_i = c_i \oplus k_i $ (or $ p_i = (c_i - k_i) \mod 26 $ for modular variants), recovering the exact plaintext bit-by-bit without error, provided the key matches and no transmission errors occur.[8][7] This symmetry ensures that encryption and decryption algorithms are computationally trivial, requiring only $ O(n $ operations for an $ n $-symbol message, but the security hinges entirely on key randomness, uniqueness of use, and secure distribution—flaws in which compromise the system despite the process's simplicity.[12] In practice, the Vernam cipher variant (1917) applied XOR to 5-bit Baudot code for teletype, establishing the binary model still prevalent today.[8]

Illustrative Example

The one-time pad encryption process can be illustrated using binary bits and the exclusive-or (XOR) operation, denoted $ \oplus $. For a plaintext message represented as bits $ p_1, p_2, \dots, p_n $, a key consists of $ n $ truly random bits $ k_1, k_2, \dots, k_n $. The ciphertext bits are computed as $ c_i = p_i \oplus k_i $ for each $ i = 1 $ to $ n $.[13] Decryption recovers the plaintext by $ p_i = c_i \oplus k_i $, exploiting the property that XOR is involutory, meaning applying it twice with the same operand yields the original value.[13] Consider a concrete example with plaintext bits 101 (equivalent to decimal 5). Using key bits 011, the ciphertext is calculated as follows:
PositionPlaintext Bit ($ p_i $)Key Bit ($ k_i $)Ciphertext Bit ($ c_i = p_i \oplus k_i $)
1101
2011
3110
This yields ciphertext 110 (decimal 6). Decryption applies the key again: 1 ⊕ 0 = 1, 1 ⊕ 1 = 0, 0 ⊕ 1 = 1, recovering 101.[14] The one-time requirement is demonstrated by key reuse. Suppose the same key 011 encrypts a second plaintext 110, producing ciphertext 101. XORing the ciphertexts 110 ⊕ 101 = 011, which equals the XOR of the plaintexts 101 ⊕ 110 = 011. An eavesdropper obtaining both ciphertexts can thus derive the XOR of the plaintexts, potentially revealing information if one plaintext is guessed or patterned. This vulnerability underscores that keys must be used only once and securely destroyed after use.

Historical Development

Precursors and Early Ideas

In 1882, Frank Miller, an American banker from Nevada, proposed a cryptographic method for securing telegraph messages that effectively constituted the first description of a one-time pad system.[15] In his self-published pamphlet Telegraphic Code to Insure Privacy and Secrecy in the Transmission of Telegrams, Miller advocated superenciphering plaintext—often abbreviated commercial codes—by adding or substituting characters from a randomly generated key sequence of identical length to the message.[16] He stressed that keys must be prepared in advance in numbered books, used exclusively for one message, and destroyed immediately after to prevent reuse or compromise, rendering the system unbreakable if keys remained secret and truly random.[2] Miller's approach addressed vulnerabilities in contemporaneous telegraphy, where messages were frequently sent in plaintext or weakly enciphered commercial codes susceptible to frequency analysis and interception.[15] By employing random keys, the resulting ciphertext mimicked meaningless noise, eliminating patterns exploitable by adversaries. However, implementation was manual, involving pencil-and-paper operations like modular addition of numeric key values to message characters, which limited scalability for high-volume telegraph traffic.[16] Despite its conceptual rigor, Miller's system achieved minimal practical uptake owing to challenges in generating and distributing large volumes of secure random keys without mechanical aids, as well as the prevailing reliance on simpler ciphers.[2] The idea faded into obscurity for decades, overshadowed by polyalphabetic ciphers like those derived from Blaise de Vigenère's 16th-century tableau method, which reused keys and thus lacked equivalent security.[15] No earlier documented proposals match the one-time pad's core requirements of randomness, equal length, and single use, positioning Miller's work as the foundational precursor.[16]

Invention and Key Contributors

The one-time pad cipher, as an electrical system for securing telegraphic communications, was invented in 1917 by Gilbert Vernam, an engineer at AT&T's research laboratory.[2] [17] Vernam developed a method using perforated paper tape to generate a keystream via a teleprinter's baudot code, where the plaintext characters were XORed with corresponding key characters from the tape, producing ciphertext indistinguishable from random without the key.[18] He filed for a patent on this system in 1918, which was granted as U.S. Patent 1,310,719 on July 22, 1919, marking the first practical implementation of stream encryption with a prepared key sequence.[2] A critical advancement came from Major Joseph Oswald Mauborgne, a U.S. Army Signal Corps officer, who collaborated with Vernam and emphasized that security required the key to be truly random, at least as long as the message, and used only once, eliminating any periodicity that could enable cryptanalytic attacks.[19] [17] Mauborgne's insight, documented in military evaluations around 1917–1919, transformed Vernam's repeating or predictable keystream approach into the unbreakable form proven theoretically secure decades later by Claude Shannon.[18] Their joint work laid the foundation for one-time pad systems, though initial implementations faced logistical challenges in key distribution.[2] While Vernam provided the mechanical innovation and Mauborgne the theoretical rigor on randomness, later cryptanalysts like William Friedman built on these ideas by analyzing the security implications, such as using the index of coincidence to detect key reuse.[18] No single individual claims sole invention, as the concept evolved from manual precursors, but Vernam and Mauborgne's 1917 contributions established the modern one-time pad as a cornerstone of information-theoretic cryptography.[17]

Adoption in 20th-Century Conflicts

The one-time pad found adoption primarily among intelligence and diplomatic entities during the World Wars, valued for its theoretical unbreakability when keys were truly random and used only once, though logistical constraints limited it to low-volume, high-security traffic rather than high-throughput military operations.[20] Following its formalization in the late 1910s, the German Foreign Ministry implemented one-time pads for select diplomatic encipherment starting in 1919, a practice that persisted into World War II; some of this traffic was partially decrypted by Allied codebreakers after recovery of key material from embassies or agents.[21] In World War II, the Soviet Union employed one-time pads extensively for inter-office diplomatic communications and espionage, distributing key booklets to agents via couriers or dead drops to encode short, critical messages such as atomic intelligence reports.[22] This system resisted full cryptanalysis by U.S. and British efforts, including the Venona project initiated in 1943, which succeeded only against a fraction of messages due to Soviet errors like duplicating key pages across pads—errors stemming from wartime production shortages rather than inherent flaws in the cipher.[22] Soviet adherence to single-use keys in most cases preserved secrecy for operations supporting the atomic bomb project and other espionage, underscoring the pad's efficacy against even advanced computational attacks of the era when implemented correctly.[20] Britain's Special Operations Executive shifted to one-time pads in 1943 as its core field cipher, replacing vulnerable poem codes and book ciphers for agent transmissions to resistance networks in Nazi-occupied territories; silk-printed pads were favored for their durability and concealability, enabling secure low-bandwidth radio bursts.[23] Allied forces, including the U.S., occasionally used variants for ultra-sensitive channels but favored rotor machines like SIGABA for volume traffic due to the pad's demands on key logistics. Axis powers such as Japan avoided widespread one-time pad deployment, opting for additive book systems like JN-25 for naval operations, which proved breakable under depth analysis, as true pads required impractical key volumes for fleet-scale use.[24] Post-1945, the cipher's legacy influenced Cold War spy tradecraft, but World War II marked its peak conflict-era application, highlighting trade-offs between theoretical perfection and practical scalability.[2]

Theoretical Foundations

Perfect Secrecy

Perfect secrecy, as defined by Claude Shannon in his 1949 paper, is a cryptographic property where the ciphertext reveals no information about the plaintext to an adversary with unlimited computational power, meaning the a posteriori probability of any plaintext message equals its a priori probability given any ciphertext with positive probability.[25] This condition, equivalent to the mutual information between plaintext and ciphertext being zero, ensures that every possible plaintext of a given length is equally likely regardless of the observed ciphertext.[25] The one-time pad achieves perfect secrecy when the key is drawn uniformly at random from a space at least as large as the message space, is independent of the message, and is used only once.[25] For an nn-bit message mm and key k{0,1}nk \in \{0,1\}^n, encryption via c=mkc = m \oplus k (bitwise XOR) produces a ciphertext cc such that, for any fixed cc and any two messages m1,m2m_1, m_2 of length nn, Pr(C=cM=m1)=Pr(C=cM=m2)=1/2n\Pr(C=c \mid M=m_1) = \Pr(C=c \mid M=m_2) = 1/2^n, since each requires a unique key k1=m1ck_1 = m_1 \oplus c or k2=m2ck_2 = m_2 \oplus c, both equally likely under uniform key distribution.[7] Consequently, the posterior distribution over messages given cc matches the prior, satisfying Shannon's criterion.[25] Shannon proved that perfect secrecy requires the key space size to be at least as large as the message space for the relevant message lengths, establishing the one-time pad as information-theoretically optimal in key entropy for single-use encryption.[25] This security holds unconditionally, independent of computational assumptions, but demands true randomness in key generation to avoid predictability.[6] Violations, such as key reuse, destroy perfect secrecy by enabling recovery of plaintext differences via m1m2=c1c2m_1 \oplus m_2 = c_1 \oplus c_2.[26]

Information-Theoretic Security

The one-time pad achieves information-theoretic security, also known as perfect secrecy, which ensures that no amount of ciphertext observation can yield any probabilistic information about the plaintext without the key, regardless of the adversary's computational resources. This property, formalized by Claude Shannon in his 1949 paper "Communication Theory of Secrecy Systems," requires that the mutual information between the plaintext message MM and ciphertext CC is zero, I(M;C)=0I(M; C) = 0, meaning the ciphertext distribution is independent of the plaintext.[25] Shannon defined perfect secrecy precisely as the condition where, for all plaintexts mm and ciphertexts cc with Pr[C=c]>0\Pr[C = c] > 0, the posterior probability Pr[M=mC=c]\Pr[M = m \mid C = c] equals the prior Pr[M=m]\Pr[M = m], rendering the plaintext statistically indistinguishable from uniform randomness given the ciphertext.[6] For the one-time pad using modular addition (or bitwise XOR) over an alphabet of size qq, with a truly random key KK uniformly distributed over {0,1,,q1}n\{0, 1, \dots, q-1\}^n for an nn-symbol message, encryption C=M+KmodqC = M + K \mod q yields perfect secrecy because, for any fixed cc, every possible mm corresponds to exactly one k=cmmodqk = c - m \mod q, each equally likely under the uniform key distribution.[7] This equiprobability ensures that the adversary's view of CC provides no advantage in guessing MM, as the key masks the plaintext perfectly without patterns or dependencies exploitable by frequency analysis or any statistical test. Shannon proved that any scheme achieving perfect secrecy must have a key length at least as long as the longest plaintext, establishing the one-time pad as optimally efficient for this security level, with no shorter key possible without introducing information leakage.[25] This unconditional security contrasts with computational security in modern ciphers, which rely on hardness assumptions like factoring being intractable; information-theoretic security holds against adversaries with unbounded computation, provided the key remains secret and unreused.[6] However, practical realization demands verifiable key randomness from physical sources (e.g., quantum noise or thermal entropy), as pseudorandom keys would degrade to computational security. Violations like key reuse destroy secrecy, as C1C2=M1M2C_1 \oplus C_2 = M_1 \oplus M_2, allowing recovery of plaintext differences via crib-dragging, but under proper use, the scheme remains provably unbreakable.[7]

Mathematical Proofs

The one-time pad achieves perfect secrecy, a cryptographic notion introduced by Claude Shannon in 1949, wherein the ciphertext reveals no information about the plaintext to an adversary without the key.[25] Perfect secrecy holds if, for every plaintext message mm and ciphertext cc (of compatible lengths with positive probability), the conditional probability satisfies Pr[M=mC=c]=Pr[M=m]\Pr[M = m \mid C = c] = \Pr[M = m].[25] This independence implies zero mutual information I(M;C)=0I(M; C) = 0 between plaintext MM and ciphertext CC.[25] For the one-time pad over binary strings of length nn, encryption is defined as C=MKC = M \oplus K, where \oplus denotes bitwise XOR, MM is the plaintext, and KK is a key drawn uniformly at random from {0,1}n\{0,1\}^n and independent of MM.[6] Decryption recovers M=CKM = C \oplus K. Shannon proved that this scheme provides perfect secrecy provided KM|K| \geq | \mathcal{M} |, where M\mathcal{M} is the message space; equality holds when M=2n|\mathcal{M}| = 2^n.[25] Theorem (Perfect Secrecy of OTP): Assuming uniform priors over messages and keys, Pr[C=cM=m]=1/2n\Pr[C = c \mid M = m] = 1/2^n for all m,c{0,1}nm, c \in \{0,1\}^n.[12] By Bayes' theorem, Pr[M=mC=c]=Pr[C=cM=m]Pr[M=m]Pr[C=c]\Pr[M = m \mid C = c] = \frac{\Pr[C = c \mid M = m] \Pr[M = m]}{\Pr[C = c]}. Since Pr[C=cM=m]=Pr[K=mc]=1/2n\Pr[C = c \mid M = m] = \Pr[K = m \oplus c] = 1/2^n and Pr[M=m]=1/2n\Pr[M = m] = 1/2^n, the marginal Pr[C=c]=mPr[C=cM=m]Pr[M=m]=2n(1/2n1/2n)=1/2n\Pr[C = c] = \sum_{m'} \Pr[C = c \mid M = m'] \Pr[M = m'] = 2^n \cdot (1/2^n \cdot 1/2^n) = 1/2^n. Thus, Pr[M=mC=c]=(1/2n1/2n)/(1/2n)=1/2n=Pr[M=m]\Pr[M = m \mid C = c] = (1/2^n \cdot 1/2^n) / (1/2^n) = 1/2^n = \Pr[M = m], independent of cc.[12] [7] This information-theoretic security holds unconditionally, requiring no computational assumptions, as the adversary cannot distinguish the ciphertext distribution from uniform randomness regardless of resources.[6] Shannon further showed perfect secrecy necessitates KM|K| \geq | \mathcal{M} | in the worst case, achieved precisely by the one-time pad.[25]

Implementation Requirements

True Randomness for Keys

The one-time pad provides information-theoretic security solely when its keys are drawn uniformly at random from the full key space, with each key bit independent and equally likely to be 0 or 1, matching the plaintext length exactly. This ensures that the ciphertext reveals no statistical information about the plaintext, as every possible message is equally probable given the observed ciphertext. Claude Shannon formalized this in his 1949 analysis, proving that perfect secrecy requires the a posteriori probability of any plaintext to equal its a priori probability after observing the ciphertext, a condition met only through such random key selection.[25] Deviations from true randomness, such as biased distributions or correlations in key material, undermine this security by introducing detectable patterns in the ciphertext. For example, if keys derive from non-random sources like excerpts from books or predictable algorithms, adversaries can exploit linguistic redundancies or statistical biases to narrow the space of likely plaintexts, as the key fails to fully entropically mask the message. Analyses of historical implementations using typewriter-generated pads have shown that human typing habits introduce subtle biases, making keys distinguishable from uniform randomness via higher-order statistical tests.[27][28] Generating truly random keys demands sources with entropy at least equal to the key length, typically hardware-based random number generators (RNGs) that harvest unpredictable physical processes, such as thermal noise in resistors, radioactive decay timing, or quantum measurements of photon polarization. These provide the necessary independence, unlike software pseudo-RNGs, which are deterministic functions of a seed and vulnerable to reconstruction if the internal state is compromised or if outputs are analyzed for periodicity. Even minor entropy deficits, quantifiable via tests like NIST SP 800-22 suites, can enable partial key recovery through conditional probability attacks, eroding the scheme's unconditional guarantees.[12]

Key Generation and Storage

The generation of one-time pad keys demands a truly random sequence of bits or symbols, uniformly distributed and unpredictable, matching the length of the message to achieve information-theoretic security.[12] This randomness cannot be approximated by pseudorandom generators, as any detectable bias or pattern in the key stream undermines perfect secrecy by allowing statistical analysis to reveal structure.[12] Historical implementations often fell short; for instance, Soviet one-time pads in the 1940s relied on electromechanical devices like the Venus cipher machine, which produced keys with subtle non-random artifacts exploitable by cryptanalysts.[20] Modern secure generation employs physical entropy sources, such as quantum fluctuations or thermal noise in hardware random number generators (HRNGs), validated against standards like NIST SP 800-90B for entropy estimation.[29] Key production scales poorly due to the volume required—e.g., encrypting a 1 MB message necessitates 1 MB of fresh randomness—necessitating batch generation via specialized equipment like perforated tape machines or punched cards in mid-20th-century military use.[30] To mitigate risks of bias, keys are often derived from multiple independent entropy sources and subjected to post-processing, such as von Neumann debiasing, though this reduces effective throughput.[31] In practice, agencies like the U.S. National Security Agency have historically printed keys in booklet form from certified random processes to support field operations, ensuring each pad's uniqueness through serialized distribution.[20] Storage of one-time pad keys prioritizes physical isolation to prevent unauthorized access or digital interception, typically using tamper-evident media like printed paper pads or microdot film housed in secure vaults with restricted access protocols.[32] Keys must remain confidential to both parties until use, with protocols mandating destruction—often by burning or shredding—immediately after decryption to eliminate reuse risks and retroactive compromise if ciphertext is intercepted.[33] Electronic storage is avoided due to potential side-channel vulnerabilities, such as electromagnetic emanations or malware; instead, physical key-protected systems embed keys in hardware tokens that self-destruct upon improper access.[34] Distribution occurs via trusted couriers or diplomatic pouches, as seen in Cold War-era intelligence operations, where key booklets were exchanged under chain-of-custody logs to verify integrity and prevent substitution attacks.[32] Compromise of storage, as in the 1944 German capture of partially used pads, has historically enabled partial plaintext recovery when combined with traffic analysis.[20]

Secure Distribution Methods

The security of a one-time pad system hinges on the secrecy of the key material, which must be distributed to recipients via channels at least as secure as the encrypted communications it enables. In practice, this often involves physical delivery methods, such as trusted couriers or diplomatic pouches, to minimize interception risks. For instance, during the Cold War, Soviet intelligence agencies distributed compact OTP booklets printed in microfont and concealed within everyday objects like cigarette packs or book bindings to evade detection during transit.[2] Keys are typically generated and paired in advance—one copy retained by the sender and an identical copy delivered to the recipient—ensuring both parties synchronize without electronic transmission vulnerabilities. Historical military applications, such as U.S. diplomatic communications, relied on secure pre-distribution through armored transport or hand-carried by personnel vetted for loyalty, as electronic alternatives were deemed insufficiently tamper-proof prior to widespread digital infrastructure.[29] Contemporary proposals for remote distribution leverage quantum key distribution (QKD) protocols, where photons encode key bits over fiber optics or free space, exploiting the no-cloning theorem and observer effect to detect eavesdropping attempts. However, QKD systems remain constrained by distance limitations (typically under 100 km without repeaters) and require initial trusted setup, rendering them impractical for large-scale OTP deployment outside controlled environments like secure data centers.[35][36] Key distribution poses inherent challenges, including the logistical burden of transporting voluminous random data equivalent in length to anticipated message traffic and the risk of insider compromise during handling. Unlike asymmetric cryptography, OTP lacks a built-in mechanism for key exchange, necessitating a "secure bootstrap" phase that can itself be a single point of failure if the distribution channel is breached.[37]

Practical Challenges and Errors

Avoiding Key Reuse

Key reuse in one-time pad systems eliminates the perfect secrecy guaranteed by Claude Shannon's theorem, which requires that each key segment be applied exclusively to a single plaintext of equal or lesser length.[6][7] When the identical key $ k $ encrypts two plaintexts $ p_1 $ and $ p_2 $, yielding ciphertexts $ c_1 = p_1 \oplus k $ and $ c_2 = p_2 \oplus k $, an eavesdropper computes $ c_1 \oplus c_2 = p_1 \oplus p_2 $, directly exposing the bitwise differences between the plaintexts.[38][17] This XOR difference leaks structural information, especially in messages with linguistic redundancy, enabling attacks such as crib dragging—sliding hypothesized common phrases against the difference stream to identify alignments yielding coherent English in both recovered plaintexts—or statistical analysis of bit patterns to infer content.[39] Even absent known plaintexts, repeated reuse across multiple messages (multi-time pad) amplifies vulnerabilities, reducing effective security to levels comparable to weaker ciphers like Vigenère under equivalent key reuse.[38] Avoidance demands rigorous procedural controls: pre-generate key material exceeding total expected plaintext volume by a margin for errors, distribute via trusted physical means like diplomatic pouches, and employ mechanical or manual tracking (e.g., perforated pads with sequential sheets) to enforce single-use discipline.[40] Keys must be irretrievably destroyed post-decryption—via burning or shredding—to preclude archival recovery, with operational protocols audited to detect inadvertent overlaps, as even partial reuse suffices for compromise.[41] Historical breaches, such as Soviet diplomatic traffic broken via Venona intercepts exploiting book cipher key shortages leading to reuse, underscore that logistical failures in key provisioning often precipitate violations despite awareness of risks.[42]

Authentication Deficiencies

The one-time pad (OTP) achieves perfect secrecy for confidentiality but inherently lacks authentication and integrity assurance, as its XOR-based encryption is fully malleable. An active adversary can arbitrarily modify ciphertext blocks, resulting in predictable changes to the decrypted plaintext without any built-in mechanism for the receiver to detect the alteration. For example, XORing a chosen bit string δ to a ciphertext c = p ⊕ k yields c' = c ⊕ δ, which decrypts to p' = p ⊕ δ, allowing targeted tampering such as bit flips or substitutions that preserve message format while conveying false information.[43][8][44] This malleability stems from the commutative and invertible nature of XOR: modifications propagate directly to plaintext without introducing detectable errors or redundancy, unlike error-correcting codes or structured formats that might flag anomalies in randomized output. Without supplementary measures, such as message authentication codes (MACs) or redundant checks, the receiver has no cryptographic guarantee that the plaintext derives from the intended sender or remains untampered, rendering OTP unsuitable for scenarios requiring verifiable origin or integrity, like command-and-control communications.[42][45] Adding authentication to OTP typically involves prepending or appending integrity tags, but this compromises the scheme's simplicity and unconditional security properties, as tags must themselves be protected against similar attacks or rely on additional keys, potentially introducing reuse vulnerabilities or computational assumptions. Historical analyses confirm that pure OTP deployments, such as in early diplomatic systems, prioritized secrecy over tamper resistance, often necessitating out-of-band verification in practice.[43][46]

Scalability and Usability Issues

The one-time pad requires a secret key of precisely the same length as the plaintext message, necessitating one bit of truly random key material per bit of data encrypted, which severely limits scalability for high-volume communications.[47] For instance, encrypting a 1 gigabyte message demands 1 gigabyte of key storage and generation, rendering it infeasible for bulk data transfers like those in modern networks or file sharing, where key production rates must match or exceed data throughput to avoid bottlenecks.[48] Generating such quantities of high-entropy randomness typically relies on specialized hardware, which operates at limited speeds—often far below gigabit-per-second rates required for practical digital applications—compounding costs and infrastructure demands.[47] Secure key distribution poses a core usability barrier, as exchanging keys of message-equivalent length mirrors the original secrecy challenge, often requiring physical courier methods or pre-established secure channels that undermine the system's efficiency for dynamic or remote communications.[49] In practice, this confines one-time pad deployment to low-bandwidth, high-stakes scenarios, such as diplomatic couriers carrying printed key booklets during the Cold War, where messages were restricted to short bursts to minimize material needs.[50] Digital adaptations exacerbate risks from data remanence, where partially used keys on storage media cannot be reliably erased without specialized sanitization, increasing vulnerability to forensic recovery.[50] For networked environments involving multiple parties, key management scales poorly, as unique pads must be provisioned pairwise to maintain independence, leading to exponential growth in material volume and administrative overhead that overwhelms operational feasibility beyond small, trusted groups.[48] Usability suffers from the absence of inherent authentication or integrity checks, obligating supplementary protocols that add complexity and potential failure points, while manual handling of pads invites human errors like accidental reuse or misalignment during encoding.[48] These factors collectively relegate the one-time pad to niche roles, supplanted by computationally efficient alternatives like AES for scalable, user-friendly encryption in contemporary systems.

Security Evaluation

Resistance to Classical Attacks

The one-time pad provides perfect secrecy against ciphertext-only attacks, meaning that the ciphertext reveals no statistical information about the plaintext to an adversary without the key. This property, established by Claude Shannon in his 1949 paper "Communication Theory of Secrecy Systems," holds because the encryption function—typically bitwise XOR with a truly random key of equal length—ensures that for any fixed plaintext message $ m $ and any ciphertext $ c $, the probability $ \Pr[C = c \mid M = m] $ equals $ \Pr[C = c] $, rendering the posterior distribution over plaintexts uniform regardless of the observed ciphertext.[6][8] Consequently, classical cryptanalytic techniques such as frequency analysis fail, as the randomized output lacks biases or patterns exploitable for partial recovery; each ciphertext symbol is independently uniform over the alphabet, eliminating dependencies that characterize weaker ciphers like substitution or transposition systems.[27] In known-plaintext attacks, where an adversary accesses a specific plaintext-ciphertext pair, the corresponding key segment can be computed as $ k = p \oplus c $, but this yields no advantage against other messages encrypted with distinct, non-reused key material, preserving secrecy for the system as a whole under proper usage.[6] Chosen-plaintext attacks similarly prove futile for information gain beyond the queried pairs, as the one-time nature prevents key extrapolation or pattern detection across encryptions; Shannon's framework demonstrates that the mutual information between plaintext and ciphertext is zero, $ I(M; C) = 0 $, irrespective of adaptive adversary queries, provided keys remain secret and unreused.[8][27] Brute-force exhaustive search over the key space requires enumerating $ 2^{|m|} $ possibilities for an $ |m| $-bit message, each equally plausible and yielding a valid decryption, thus providing no basis for distinguishing the correct plaintext—a computational infeasibility that aligns with the scheme's information-theoretic security rather than mere hardness assumptions.[6] Linear and differential cryptanalysis, effective against block ciphers like DES or AES due to approximations in their pseudorandom permutations, do not apply, as the one-time pad's key randomness ensures no substructure or bias for probabilistic distinguishers to exploit.[8] This unconditional resistance stems from the key's entropy matching or exceeding the message's, satisfying Shannon's necessary and sufficient condition for perfect secrecy: $ |K| \geq |M| $, where $ K $ and $ M $ denote key and message spaces.[27]

Vulnerabilities from Implementation Flaws

The one-time pad's theoretical perfect secrecy assumes keys are generated with true randomness from high-entropy sources, such as physical processes like radioactive decay or thermal noise; deviations, such as employing pseudorandom number generators (PRNGs), introduce predictability, as PRNG outputs are deterministic and vulnerable to reverse-engineering if the seed or algorithm is compromised or insufficiently seeded.[51][52] For instance, software-based PRNGs relying on system clocks or low-entropy inputs can produce detectable biases or correlations, enabling statistical attacks that distinguish ciphertext from random noise.[31] Key storage flaws, including inadequate physical or digital protection, expose pads to theft, interception, or insider access; paper pads, historically common, risk duplication or loss during handling, while digital equivalents stored on insecure media can be extracted via side-channel attacks like cold boot memory recovery.[23][53] Distribution errors compound this, as transmitting keys over insecure channels—even once—negates secrecy if the channel lacks independent protection, potentially allowing adversaries to obtain keys before encryption occurs.[54] Operational implementation lapses, such as synchronization failures between parties or errors in key excision (selecting incorrect segments), result in decryption mismatches or unintended reuse of key material, transforming the system into a malleable cipher susceptible to known-plaintext recovery.[30] Additionally, encoding inconsistencies—like non-uniform message padding or failure to account for header metadata—can leak structural information, aiding traffic analysis despite the pad's randomness.[31] These flaws underscore that OTP security hinges on flawless execution, where even minor procedural deviations enable exploitation without brute-force computation.

Known Historical Exploits

The primary historical exploit of the one-time pad stemmed from Soviet operational errors during World War II and the early Cold War, enabling partial decryption under the U.S. Venona project. Soviet communications, including espionage traffic to and from New York, were first enciphered with a numeric codebook and then superenciphered using additive one-time pads generated from random number tables.[55] Due to wartime shortages, Soviet printing facilities duplicated approximately 35,000 pages of these pads in 1941–1942, distributing identical copies to multiple diplomatic outposts, which led to inadvertent reuse across distinct messages.[56] This violation transformed the system into a set of two-time pads, allowing U.S. Army Signal Intelligence Service cryptanalysts, starting in 1943 under Frank Rowlett and later Meredith Gardner, to exploit the redundancy via crib-based attacks, depth analysis, and known-plaintext assumptions on codebook structures.[57] By 1946–1948, Venona yielded partial recoveries of over 3,000 messages, exposing Soviet agents like Klaus Fuchs and the Rosenbergs in the Manhattan Project, though full decryption rates remained below 15% due to the pads' residual randomness.[58] A related incident involved Soviet-Australian diplomatic traffic intercepted in 1945, where codebook-superenciphered messages using reused one-time pads were partially broken by Allied cryptanalysts, confirming espionage links but contributing less to Venona's broader revelations.[30] These exploits did not undermine the one-time pad's theoretical information-theoretic security—proven unbreakable by Claude Shannon in 1949 when keys are truly random, non-reused, and secret—but highlighted practical vulnerabilities from human and logistical failures in key management.[20] No verified cryptographic breaks of properly implemented one-time pads have occurred, as confirmed by declassified analyses emphasizing misuse over inherent flaws.[55]

Applications

Military and Diplomatic Uses

The one-time pad was extensively utilized in military operations during World War II by special operations teams, resistance groups, and intelligence agencies across both Allied and Axis powers, providing a means for secure, short-message encryption in field conditions where mechanical devices were impractical.[23][59] German forces, for instance, implemented OTP systems starting around 1947 according to declassified documents, though earlier adoptions occurred for high-value transmissions.[60] In the Cold War era, military applications extended to espionage and secure command communications, with Eastern Bloc agents employing OTP booklets for covert messaging and Western powers using it in systems like the Washington-Moscow hotline for verifiable perfect secrecy in diplomatic-military channels.[2][61] Diplomatic services adopted the one-time pad as early as the 1910s for confidential telegraphic reporting, with formalized systems emerging in the 1920s to replace vulnerable ciphers amid rising interception risks.[30] The German Foreign Office pioneered a standardized single-use pad variant during this period, deriving its name from disposable paper sheets that ensured non-reusability and theoretical unbreakability. By the interwar years, embassies worldwide relied on OTP for end-to-end secure cables, as it offered diplomats the first historically verifiable unbreakable encryption against cryptanalytic attacks, provided keys were randomly generated and securely distributed via couriers.[40] In contemporary military and diplomatic practice, OTP persists for niche top-secret exchanges where key distribution is feasible, such as between high-level commands or isolated outposts, due to its proven resistance to all known classical cryptanalysis when protocols are strictly followed.[62] Logistics, including physical key transport by secure means like diplomatic pouches or naval vessels, have historically enabled its use in navies and forward deployments, though scalability limits it to low-volume, ultra-sensitive traffic rather than routine operations.[20][63]

Research and Theoretical Contexts

The one-time pad cipher originated from research into secure telegraphic communication systems. In 1917, Gilbert Vernam, an engineer at AT&T, developed and patented an additive stream cipher for teletype machines, which encrypted messages by combining plaintext characters with a key stream of equal length using modulo-26 addition.[64] This system initially relied on predictable key generation from repeating phrases, limiting its security, but Vernam's work laid the groundwork for random-key variants. Concurrently, U.S. Army Major Joseph Mauborgne advanced the concept by insisting on truly random keys generated independently of the message, ensuring non-reusability and enhancing resistance to cryptanalysis; their collaboration produced the foundational one-time pad mechanism recognized today.[2] Theoretical validation emerged in the mid-20th century through information theory. In his 1949 paper "Communication Theory of Secrecy Systems," Claude Shannon formalized the conditions for perfect secrecy, proving that a one-time pad achieves it when the key is uniformly random, at least as long as the plaintext, used only once, and kept secret from adversaries.[6] Perfect secrecy implies that the mutual information between plaintext and ciphertext is zero, rendering the ciphertext statistically independent of the plaintext and indistinguishable from random noise without the key; formally, for any plaintexts $ m_0, m_1 $ and ciphertext $ c $, the probability $ \Pr[M = m_0 | C = c] = \Pr[M = m_0] $. This information-theoretic security holds against computationally unbounded attackers, establishing the one-time pad as the unattainable ideal for secrecy proofs in cryptography.[6] In academic research, the one-time pad serves as a benchmark for evaluating cryptographic primitives under information-theoretic models, influencing fields like secure multi-party computation and quantum key distribution. Studies contrast its unconditional security with computational schemes like AES, highlighting how OTP's requirements—perfect randomness and key length equality—expose fundamental trade-offs in scalable encryption.[65] Ongoing theoretical work explores approximations, such as weakly universal hash functions mimicking OTP properties for shorter keys, but these sacrifice perfect secrecy for practicality, reaffirming OTP's role as the sole provably secure system under Shannon's criteria.[66] Empirical analyses in cryptology texts verify that deviations, like key reuse, collapse security to statistical attacks, underscoring the precision of Shannon's model.[7]

Integration with Quantum Systems

Quantum key distribution (QKD) protocols integrate with the one-time pad by enabling the secure generation and exchange of truly random keys over quantum channels, mitigating the classical challenge of distributing keys as long as the plaintext without compromising secrecy. In QKD systems, such as those based on the BB84 protocol introduced by Charles Bennett and Gilles Brassard in 1984, a sender transmits qubits (e.g., photons in different polarization states) to a receiver, who measures them in randomly chosen bases; subsequent classical communication reconciles bases, estimates error rates to detect eavesdropping via quantum state disturbances, and applies privacy amplification to distill a shared secret key. This key, confirmed to contain negligible information accessible to interceptors due to quantum no-cloning and measurement principles, serves directly as the one-time pad for encrypting subsequent classical messages via bitwise XOR, achieving unconditional information-theoretic security.[67][68] The combination of QKD and one-time pad encryption provides composable security guarantees, where formal proofs demonstrate that the overall system remains secure even when embedded in larger protocols, as the OTP's perfect secrecy holds provided the key remains uniformly random and unused. Experimental implementations, including high-speed QKD systems capable of generating keys at rates supporting one-time pad applications like encrypted video transmission, have demonstrated practical viability over fiber optic or free-space links, with error-corrected keys verified against quantum threats. For instance, NIST-developed QKD prototypes have integrated OTP for robust, sustainable key streams in real-world scenarios.[69][70] Beyond key distribution, quantum variants of the one-time pad extend the framework to protect quantum states, using classical random bits to apply Pauli operators (X, Z, or both) for encryption, allowing secure transmission of qubits over public quantum channels while detecting tampering. Security analyses confirm that such quantum one-time pads resist eavesdropping even with quantum adversaries, though they require shared classical keys initially distributed via QKD. This integration enhances quantum communication networks, as seen in proposals for homomorphic encryption schemes built on quantum one-time pads for non-Clifford gate circuits.[71][72][73]

Comparisons and Limitations

Versus Stream Ciphers and AES

The one-time pad (OTP) achieves information-theoretic security, meaning it conceals the plaintext perfectly from any adversary, regardless of computational resources, provided the key is truly random, as long as the message, and used only once, as proven by Claude Shannon in 1949.[74] In contrast, stream ciphers and the Advanced Encryption Standard (AES) offer computational security, relying on the assumption that certain mathematical problems (e.g., distinguishing pseudorandom from truly random sequences) are intractable with current or foreseeable computing power, but they provide no unconditional guarantees against unlimited computation or advances like quantum algorithms.[75][76] Stream ciphers, such as those based on pseudorandom number generators (PRNGs) seeded by a short key, approximate the OTP by generating a keystream via XOR with the plaintext, but they sacrifice perfect secrecy for practicality; security holds only if the PRNG resists cryptanalytic attacks and key reuse (mitigated by nonces or initialization vectors), yet flaws like those in RC4 have led to real-world breaks.[8] AES, a block cipher standardized by NIST in 2001, operates on fixed 128-bit blocks and can emulate stream-like behavior in counter (CTR) mode, but its 128-, 192-, or 256-bit keys enable efficient encryption of arbitrary-length data without per-message key expansion matching OTP's randomness requirement.[77] Unlike OTP, both are vulnerable to side-channel attacks, implementation errors, or brute-force if key sizes prove insufficient against future hardware, as evidenced by AES's resistance to classical attacks but potential susceptibility to Grover's algorithm reducing effective key strength by half on quantum computers.[78]
AspectOne-Time PadStream CiphersAES (in CTR mode)
Security BasisInformation-theoretic (unbreakable)Computational (PRNG hardness)Computational (block diffusion)
Key LengthEqual to message lengthFixed short (e.g., 128–256 bits)Fixed (128/192/256 bits)
EfficiencySimple XOR, but key distribution bottleneckHigh-speed keystream generationHardware-optimized, ~10 Gbps throughput
Practical UseLimited to low-volume, secure channelsReal-time data (e.g., Wi-Fi WPA2)General-purpose (e.g., TLS, disk encryption)
OTP's key distribution demands secure, high-entropy material matching data volume—impractical for gigabytes, as in modern networks—whereas stream ciphers and AES leverage short, reusable keys transmissible via asymmetric protocols like Diffie-Hellman, enabling scalability without compromising core secrecy assumptions under current threats.[77][79] However, OTP avoids reliance on unproven primitives; stream ciphers risk keystream biases if the PRNG fails (e.g., linear feedback shift registers vulnerable to algebraic attacks), and AES, while unbroken in practice since its selection over competitors like Rijndael variants, assumes no novel attacks on its substitution-permutation network.[8] Neither provides OTP's malleability resistance inherently—OTP and plain stream XOR allow undetectable alterations—but AES modes like GCM integrate authentication, addressing a gap in pure confidentiality systems.[80]

Economic and Logistical Barriers

The one-time pad demands a truly random key equivalent in length to the plaintext, imposing severe logistical constraints on generation and secure storage, as producing high-entropy key material at scale requires specialized hardware like hardware random number generators, which are resource-intensive and susceptible to implementation flaws if entropy sources are inadequate.[81] Storage further complicates matters, as keys must be safeguarded against compromise or data remanence in digital media, often necessitating tamper-resistant physical devices or isolated analog methods for large volumes, limiting applicability to low-throughput scenarios.[82] Key distribution represents a primary logistical barrier, requiring pre-sharing via channels at least as secure as the encrypted communication itself, historically achieved through physical couriers carrying printed pads in military and diplomatic contexts, such as naval operations where secure lockers facilitated transfer from central facilities.[20] This method proves impractical for modern high-bandwidth needs, as distributing keys for terabyte-scale data would entail prohibitive synchronization efforts to prevent reuse or desynchronization, alongside risks of interception during transit.[81] Economically, these requirements amplify costs proportionally to data volume; for instance, securing a single gigabyte message doubles resource demands for key handling alone, including generation hardware, secure transport, and personnel, far exceeding the efficiencies of shorter-key alternatives like AES, which amortize fixed costs over repeated uses.[82] In scalable systems, such as network traffic exceeding petabytes daily, the expense of equivalent key infrastructure renders deployment uneconomical, confining OTP to niche, low-volume applications where perfect secrecy justifies the overhead.[83]

Myths and Misconceptions

A prevalent misconception holds that the one-time pad achieves perfect secrecy even when keys are generated using pseudorandom number generators rather than truly random sources. In practice, such keys introduce predictable patterns exploitable by cryptanalysis, effectively transforming the system into a stream cipher susceptible to attacks like those targeting linear feedback shift registers or other deterministic algorithms.[84][85] Another falsehood is the belief that one-time pad encryption inherently provides message authentication or integrity protection. Ciphertexts remain malleable; an adversary can flip specific bits to alter the underlying plaintext in predictable ways without invalidating the decryption process, as the operation is reversible via XOR with the same key. This vulnerability persists because the scheme offers no mechanism to detect tampering, unlike modern authenticated encryption modes.[53] It is often erroneously assumed that partial key reuse or stretching a shorter key across multiple messages maintains security. Reuse, even of segments, enables known-plaintext attacks where cribs—guessed common phrases—reveal key material through XOR operations on multiple ciphertexts, as demonstrated in the 1943–1980 Venona project where Soviet reuse of pads allowed U.S. cryptanalysts to recover approximately 3,000 messages.[86][87] Some claim one-time pads are obsolete or impracticable solely due to key distribution challenges, overlooking their continued use in niche, high-stakes scenarios like diplomatic hotlines where physical key exchange is feasible. However, scalability issues—requiring keys equal in length to all transmitted data—render them inefficient for high-volume communications compared to asymmetric systems.[61][48] A further myth posits that encrypting identical or similar plaintexts multiple times with independent pads leaks information via statistical analysis. Provided each pad is uniformly random and unused, the resulting ciphertexts appear indistinguishable from random noise, preserving perfect secrecy even for repeated messages, as Shannon's information theory proves no probabilistic advantage exists for the attacker.[88][89]

References

User Avatar
No comments yet.