One time pads
The one-time pad (or Vernam cipher) is an information-theoretically secure cipher, and one of the simplest of all ciphers. It was invented in 1917 and patented just after World War I by Gilbert Vernam (of AT&T) and Joseph Mauborgne (USA, later chief of the Signal Corps). The fundamental features of this cipher are that the sender and receiver each have a copy of an encryption key, which is as long as the message to be encrypted, and each key is used for only one message and then discarded. That key must be random (ie, without pattern), unpredictable, and must remain unknown to any attacker. In addition, the key must never be reused, or the cipher becomes trivially breakable if two messages encrypted with the same key come into the hands of an attacker.
For example, two identical pads of paper with random letters can be exchanged between sender and receiver. Later, when they wish to send a message, the sender uses the (random) key in the pad (say that on the first page of his pad) to encrypt a message. One technique is to XOR (ie, combine in a particular way) the first character of the key with the first character of the plaintext, the second character of the key with the second character of the plaintext, etc. Even a simple letter-substitution cipher -- as has been known at least since Julius Caesar's time -- can be used, as long as there is a different, random offset for each letter, determined by the corresponding letter of the key. He then sends the encoded message to the receiver, who decrypts it with his copy of the first page of the pad. Both now destroy the used key page, having used it only 'one-time'. Chewing and swallowing the discarded page is 'traditional' particularly in thrillers, but any non-recoverable destruction will do.
One-time pads are information-theoretically secure, in that if all the conditions are met properly (i.e., the keys are chosen randomly, are unpredictable, are at least as long as the message, and are never reused), then the ciphertext provides no information about the message to a cryptanalyst. This is a very strong notion of security, and implies that one-time pads are secure even against cryptanalysts with infinite computational power. Also, they are one of very few cryptosystems which can be implemented on a deterministic computer which would provably survive an affirmative solution of P vs. NP, one of the central outstanding unsolved problems of computer science.
The disadvantages of the one-time pad are that it requires very large keys, requires that they be exchanged in advance and kept in synchrony when used, be entirely without pattern and unpredictable, never be reused, and that the key material be secret from all attackers. It is therefore impractical for most users without a secure physical channel to exchange the keys.
Key material distribution is still sufficiently difficult that except for rare circumstances (e.g. spies who must encrypt short messages without access to other quality encryption methods), one-time pads are currently mostly of theoretical interest. In some diplomatic or espionage situations, the one-time pad is useful because it can be computed by hand with less effort than for most other high quality ciphers; indeed, many others are entirely impractical without computers.
It can be useful to use very simple "one time" signals - a signal, used only once, of "A" for "mission completed" and "B" for "mission failed" cannot be "decrypted" in any reasonable sense of the word. However, such strategies (often used by real operatives) are not a cryptographic one-time pad in any real sense.
The recent development of quantum cryptography has provided a way, theoretically, to securely transmit key material between two locations, in such a way that eavesdroppers cannot determine their contents without the eavesdropping being both detectable and destroying the information being transferred. This may eventually provide a better way to distribute one-time pad key materials. It is not yet clear whether this will ever be convenient enough to see widespread use and so to be of any practical importance.
Nevertheless, one-time pads have been used in special circumstances since the early 1900s. For instance, the Weimar Republic Diplomatic Service began using the algorithm about 1920. The breaking of poor Soviet cryptography by the British, with messages made public for political reasons in two instances in the 1920s), forced the USSR to improve their systems, and they seem to have used one-time pads for certain purposes around 1930. KGB spies are also known to have used pencil and paper one-time pads more recently. Examples include 'Colonel Rudoph Abel', arrested and convicted in New York City in the 50's, and the Cohens, arrested and convicted in the UK in the 60's. 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 near the end of 1941 in generating/distributing the key material. This huge, decades long effort was codenamed VENONA and included information about, for example, the Soviet 'atom spies'. The "hot line" from the White House to the Kremlin during the Cold War reportedly used a one time pad; this line was used so infrequently that pad exhaustion was a minor concern relative to providing the necessary security.
The information-theoretic security of one-time pads is wholly dependent upon the randomness (or unpredictability) and secrecy of the key pad material. If the key material is perfectly random (and never becomes known to an attacker), then it is information-theoretically secure. If the pad material is generated by a deterministic program, then it is not, and cannot be, a one-time pad; it is a stream cipher. A stream cipher takes a short key, and uses it to generate a long pseudorandom stream, which is combined with the message using a mechanism similar to that used in a one-time pad. Stream ciphers can be secure in practice, but cannot be absolutely secure in the same provable sense. At least one of the Fish cyphers used by the German military in WWII turned out to be an insecure stream cipher, not a practical automated one-time pad as was intended by its designers. Bletchley Park broke Lorenz machine messages regularly. None of these stream ciphers have the absolute, information-theoretical security of a one-time pad, although there exist stream ciphers which (so far) appear to be unbreakable in practice without access to the key.
The similarity between stream ciphers and one-time pads often leads cryptographic novices to invent stream ciphers under the mistaken impression that they are using one-time pads; these are nearly always seriously insecure. An especially insecure approach is to use any of the random number generators that are distributed with most computer programming languages and in operating system call libraries. These typically produce sequences that pass statistical tests but that are nonetheless highly predictable given a sample of their output—making them useless for cryptographic purposes. In particular, the Mersenne twister algorithm, while sufficiently "random" for almost any research or simulation use, cannot be used to generate one-time pad key material. One reason this, and similar algorithms, are useful in research is that they are deterministic - and therefore an independent researcher can seed the algorithm with the same values and get the same result. Predictability is a extremely serious problem for cryptographic use.
Though cryptographically secure pseudo-random number generators exist that serve as the basis for computationally secure stream ciphers, even these do not provide the information-theoretic security of a one-time pad. Any claim that a particular stream cipher is equivalent in strength to the one-time pad is typically viewed, with justice, as a sign of snake oil by professional cryptographers.
Shannon's work can be interpreted as showing that any information-theoretically secure cipher will be effectively equivalent to the one-time pad algorithm. If so, one-time pads offer the best possible security of any encryption, anywhere and under any circumstances.
External links
|
