User talk:Ciphergoth/One-time pad

From Wikipedia, the free encyclopedia

Excerpt from a one-time pad.
Excerpt from a one-time pad.

In cryptography, the one-time pad (OTP) is an encryption algorithm which has been proven, from theoretical first principles, to be unbreakable when properly deployed. It was invented in 1917.

In the one-time pad the plaintext is combined with a random key or "pad" that is as long as the plaintext and used only once. 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]).

Contents

[edit] 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. 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 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: eg, "A" is 0, "B" is 1, and so on through "Z", 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 would be 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 would be subtracted from the number to make it less than 26.

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:

    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 recovers Alice's plaintext, the vital message "HELLO". Both Alice and Bob destroy the key sheet immediately after use, preventing reuse or recovery by the enemy.

[edit] Security

The Vernam-Mauborgne one-time pad was recognized early on as very difficult to break, but its special status was only realized by Claude Shannon some 25 years later. He proved, using information theory considerations, that the one-time pad has a property he termed perfect secrecy: that is, the ciphertext gives absolutely no additional information about the plaintext. Thus, the a priori probability of a plaintext message M is the same as the a posteriori probability of a plaintext message M given the corresponding ciphertext. And in fact all plaintexts are equally probable. This is the strongest possible notion of cryptanalytic difficulty.

With a conventional cryptosystem, given an intercepted encrypted message one plaintext is generally far more likely than any of the others. These cryptosystems rely for their security on the hope that the computational effort required to discover which plaintext is most likely is beyond the reach of the adversary; in some cases, beyond the reach of the combined computing resources of all of humanity for millenia or more. However, no cryptosystem has been proven to require significant computing resources to break.

The one time pad does not provide any mechanism to ensure message integrity, and in practice an active attacker who knows the message or part of the message can straightforwardly substitute that part for any other part of their choosing. If the one-time-pad is to be used, it should be combined with a perfect message authentication code using universal hashing to provide authentication. Again, one-time use of key material will be necessary for comparably strong security guarantees.

[edit] History

[edit] Technical development

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 (U.S. Patent 1,310,719 ) a cipher based on teletype machine technology. Each character in a message was electrically combined with a character on a paper tape key. Captain Joseph Mauborgne (then a captain in the United States Army and later chief of the Signal Corps) recognized that the character sequence on the key tape could be completely random and that, if so, cryptanalysis would be more difficult. Together they invented the first one-time tape system.

The second development was the paper pad system. Diplomats had long used codes and ciphers for confidentiality and to minimize telegraph costs. For the codes, words and phrases were converted to groups of numbers (typically 4 or 5 digits) using a 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 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 suspected at the time that it was already known in the highly compartmentalized world of cryptography, as for instance at Bletchley Park.

The one-time pad is also sometimes referred to as the Vernam cipher, after Gilbert Vernam, one of its inventors. Vernam's system was a cipher that combined a message with a key read from paper tape. In its original form, Vernam's system was not unbreakable in the same way as the actual OTP — this came a little later when Joseph Mauborgne recognized that if the key tape were random, cryptanalytic difficulty would be increased. Some authors use the term "Vernam cipher" as a synonym for "one-time-pad", while others use it for any additive stream cipher, including those based on a cryptographically secure pseudorandom number generator; we use it in the latter sense below.

The final discovery was by Claude Shannon in the 1940s who recognized and proved the theoretical significance of the one-time pad system.

[edit] Espionage application

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 of course not "truly" random, as it makes certain convenient key sequences more likely than others, yet it proved to be generally effective. Without copies of the key material used, only some defect in the generation method offered much hope of cryptanalysis.

Burglaries are said to have been carried out by the FBI during WWII against Soviet offices in the US which yielded copies of some key material. There are some claims that the material copied was helpful cryptanalytically. [citation needed]

Additionally, it seems that the generator system for Soviet one-time pad key material broke down for a period around the end of 1941. Some pages of the material were reused, opening a very small vulnerability. Analysists at the Army Signals Service at arlington Hall noticed clues to this, which led to a decades long effort to read intercepted messages in that cipher. That effort eventually was called the VENONA project, and proved several thousand full or partial decrypts out of several hundred thousand intercepts protected by this cryptosystem.

[edit] 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 first developed during WWII by Claude Shannon and proved, mathematically, to be true of the one-time pad by Shannon about the same time. His result was published in the Bell Labs Technical Journal in 1949. Properly used one-time pads are secure in this sense even against adversaries with infinite computational power. To continue the example from above, suppose Eve intercepts Alice's ciphertext: "EQNVZ". If Eve had infinite computing power, she would quickly find that the key "XMCKL" would produce the plaintext "HELLO", but she would also find that the key "TQURI" would produce the plaintext "LATER", an equally plausible message:

    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) ciphertext
−  19 (T)  16 (Q)  20 (U)  17 (R)   8 (I) possible key
= −15       0      −7       4      17     ciphertext-key
=  11 (L)   0 (A)  19 (T)   4 (E)  17 (R) ciphertext-key (mod 26)

In fact, it is possible to "decrypt" any message whatsoever with the same number of characters out of the ciphertext simply by using a different key and there is no information in the ciphertext which will allow Eve to choose amongst the various possible readings of the ciphertext.

Most conventional encryption algorithms both symmetric and asymmetric, use complex patterns of substitution and transpositions. For the best of these currently in use, it is not known whether there can be a cryptanalytic procedure which can reverse (or, usefully, partially reverse) these transformations without knowing the key used during encryption.

In practical terms, for the best of these, no such procedures are known, though there may exist computer algorithms which could do so in a 'reasonable' time. One of the central outstanding unsolved problems of computer science bears on this problem; if P=NP then it would be at least possible that such algorithms might be found, and they would surely be sought even more vigorously than they are today. Even if not, individual present cryptosystems might still be broken. However, the one-time pad would not be made less secure by a proof that P=NP. At present, most informed observers believe that P≠NP and so many doubt this question has any practical relevance to cryptanalysis or encryption algorithm design.

[edit] Applicability of one-time-pads

Common consumer items that can be used to transport one-time pad data.
Common consumer items that can be used to transport one-time pad data.

The theoretical perfect security of the one-time-pad applies only in a theoretically perfect setting; No real-world implementation of any cryptosystem can provide perfect security because practical considerations introduce potential vulnerabilities. The one-time-pad is in practice little-used, because the practical difficulties of using it can not only cause great inconvenience to its users but actually reduce the security below conventional cryptographic best practice, so the circumstances where it can provide improved security are few.

  • One-time pads solve few current practical problems in cryptography; the security of modern high quality ciphers is not considered a major worry at present, and such ciphers are essentially always easier to employ than one-time pads; the amount of key material which must be properly generated and securely distributed is far smaller, and public key cryptography makes the problem easier.
  • High quality random numbers are hard to generate. The random number generation functions in programming language libraries are not suitable for cryptographic use. Even those generators that are suitable for normal cryptographic use, including /dev/random and hardware random number generators, generally make use of cryptographic functions whose security is unproven. In fact, one can argue that while there is uncertainty about the physics of the world, no provable way of generating true random numbers exist.
  • Distributing the random numbers is inconvenient. Storage media such as DVD-Rs or personal digital audio players can be used to carry a very large one-time-pad from place to place in a non-suspicious way, but even so the need to transport the pad physically introduces a huge inconvenience compared to the key negotiation protocols of a modern cryptosystem. In addition the risk of compromise during transit (for example, a pickpocket swiping, copying and replacing the pad) is probably 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 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 only two persons, or a star network topology, this is somewhat less of a problem.
  • The key material must be securely disposed of after use, to ensure the key material is never reused and to protect the messages sent. Because the key material must be transported from one endpoint to another, and persist until the message is sent or received, it can be more vulnerable to forensic recovery than the (possibly transient) plaintext that it protects. See also: data remanence.
  • 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; few or none have been subject to extensive review by competent observers, unlike many standard methods. See: snake oil cryptography.

Nonetheless, the one-time-pad is well-suited to some practical applications.

  • A classic example is the red telephone between Moscow and Washington D.C.. The military have the means to transport key material with greater security than is generally available to private citizens. In addition, the link can be superencrypted with a standard cipher; both must be compromised in order to decipher the message.
  • 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 can have important security benefits in some situations, especially given the many vulnerabilities frequently found in standard computer operating systems
  • The one-time-pad is the only cryptosystem proven secure. Though we have enough confidence in them for practical purposes, we cannot be certain that a future cryptanalytic breakthrough, or a breakthrough in computer hardware such as quantum computing, will not render standard cryptosystems trivally breakable.
  • Making and using a one-time pad has educational value. No special equipment is required and it serves as a good introduction to several cryptographic ideas.

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

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.

In 1944–1945, the US Army's Signal Security Agency was able to solve a one-time pad system used by the German Foreign Office for its high-level traffic, codenamed GEE (Erskine, 2001). GEE was insecure because the pads were not completely random — the machine used to generate the pads produced predictable output.

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 numbers stations on shortwave radio suggests one-time pads are still used by spies.

A related notion is the one-time code—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.

The British Army's BATCO tactical communication code is a pencil-and-paper one-time-pad system. Key material is provided on paper sheets that are kept in a special plastic wallet with a sliding pointer that indicates the last key used. New sheets are provided daily (though a small series of "training BATCO" is usually recycled on exercise) and the old ones destroyed. BATCO is used on battlefield voice nets; the most sensitive portions of a message (typically grid references) are encoded and the ciphertext is read out letter by letter.

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 often required actual paper pads (often minuscule for ease of concealment), a sharp pencil and the use of some mental arithmetic) can be implemented as a software program using data files as input (plaintext) and output (ciphertext) and key material (the required random sequence). The XOR operation is often used to combine the plaintext and the key elements, and is especially attractive on computers since it is usually a native machine instruction and is therefore very fast. However, ensuring that the key material is actually random, is used only once, never becomes known to the opposition, and is completely destroyed after use is 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.

[edit] 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).

[edit] Methods that may offer empirical security, but do not have 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 generally use a short key which is used to seed a long pseudorandom stream, which is then combined with the message using some such mechanism as those used in one-time pads (eg, XOR). 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 block cipher like AES in counter mode. There would appear to be little reason to invent new stream ciphers, yet it has long been thought that NSA and its comparable agencies devote considerable effort to stream ciphers for their government customers.

[edit] 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 (for perspective, a 1 GHz computer which takes 10,000 clock cycles to check an offset within the RNG's cycle (a ridiculously high number) would take under a third of a second to check every possible offset). Standard computer random number generators are not suitable for cryptographic purposes, specifically including the 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 source however obscure, daily temperatures or atmospheric pressures, etc, though seemingly random, are predictable -- after the fact. Indeed, even truly random sequences which have been published cannot be used as they are now predictable if identified. An example is the Rand 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.

[edit] 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. Von Neumann whitening (as described in E VIA C3 NRNG (pdf)) is as follows:

input bits output
00 no output
01 output "1" bit
10 output "0" bit
11 no output

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 by reading from an attached noise generating 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 Triple DES.

To minimize the risk of virus infection, 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. For the same reason, 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. OTP generation would be 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.

[edit] Making one-time pads by hand

One-time pads were originally made without the use of a computer and this is still possible today. The process can be tedious, but if done correctly and the pad used only once, the result is unbreakable.

There are two components needed to make a one-time pad: a way to generate letters at random and a way to record two copies of the result. The traditional way to do the latter was to use a typewriter and carbon paper. Typewriters are scarce these days and add a requirement to destroy the carbon paper and typewriter ribbon, from which the pad data can often be recovered. A more modern approach is to hand write the letters neatly in groups of five on two part carbonless copy paper sheets, which can be purchased at office supply stores. Each sheet should be given a serial number or some other unique marking.

The simplest way to generate random letters is to obtain 26 identical objects with each letter of the alphabet marked on one object. Tiles from the game Scrabble can be used as long as only one of each letter is selected. Kits for making name charm bracelets are another possibility. One can also write the letters on 26 pennies with a marking pen. The objects are placed in a box or cup and shaken vigorously, then one object is withdrawn and its letter is recorded. The object is returned to the box and the process is repeated.

[edit] See also

[edit] References

  • Ralph Erskine, "Enigma's Security: What the Germans Really Knew", in "Action this Day", edited by Ralph Erskine and Michael Smith, pp 370–386, 2001.

[edit] External links

de:One-Time-Pad fr:Masque jetable it:Cifrario di Vernam nl:One-time-pad ja:???????? pl:One Time Pad pt:One-time pad