The One-Time Pad (OTP) has been invented, and re-invented several times over the years. The technique was first described in 1882 by US banker Frank Miller, and later re-discovered in 1917 and eventually patented by Gilbert Vernam, of Bell Telephone Laboratories. Vernam’s cipher combined a message with a key that was read from a punch tape. In the original form of the cipher, the encoded messages could eventually be cracked since the key tape was setup on a loop that resulted in the key being reused making the cipher open to cryptanalysis. The “one-time” aspect of the cipher came into play a bit later when Joseph Mauborgne, then a captain in the US Army and later chief of the Signal Corps, recognized that the character sequence on the key tape could be completely random, and if so, breaking the code would be significantly more difficult. He worked with Vernam to create the first One-Time Pad tape system.1
The “pad” of the One-Time Pad name originated from the early implementations of the cipher, where the key materials were given to personnel on a pad of paper. This was to allow the top sheet of the pad to be torn off and destroyed easily after use. Many times, the pad would be reduced to an extremely small size that would require the use of a magnifying glass to use it. Often, OneTime Pads would be printed onto extremely flammable nitrocellulose paper to allow for easy disposal.
By 1923, the One-Time Pad system was introduced in the German foreign office to protect its diplomatic messages. For the first time in history, diplomats could have had truly unbreakable encryption at their disposal. Unfortunately, they made a fatal decision to produce the random digits for their keys with a simple mechanical machine. By doing so, they degraded a perfectly secure One-Time Pad system to a weak pseudo-random stream cipher.2
Efforts by British scientists to thwart Russian cryptographic cyphers in the 1920s and 1930s was declassified in 2018, providing fascinating insights into an obscure part of the history of code breaking. In response to a Freedom of Information Act request, America’s National Security released papers from one of Britain’s top cryptanalysts during the Second World War, John Tiltman, describing his work in breaking Russian codes.
In his papers, Tiltman stated that the Russians started using One-Time Pads in 1928, however, they made the same grave cryptographic error of allowing these pads to be used twice, creating TwoTime Pads. By reusing One-Time Pads, Russian agents accidentally leaked enough information for eavesdroppers in Britain to figure out the encrypted message’s plaintext. Two separate messages encrypted reusing the same key from a pad could be compared to ascertain the differences between their unencrypted forms, and from there it was not difficult, using stats and knowledge of the language, to work out the original words.
The practice of reusing One-Time Pads continued into the Cold War, and helped British spies unravel the contents of supposedly secret Kremlin communications.
The US started Operation Venona in 1943, to decrypt messages where One-Time Pads had been reused, and this later became one of the first applications of computers to cryptanalysis, leading to the exposure of spies such as Blunt and Cairncross, two of the infamous Cambridge 5 British spy ring, that sold secrets to the KGB during the cold war.
It has been speculated that the development of decryption techniques to exploit the Russians’ use of Two-Time Pads may have fueled post-WWII work by Claude Shannon the “Father of Information Theory”, on the mathematical basis of cryptography.3
The theory developed by Claude Shannon in 1948, while working as an electrical engineer at Bell Labs in the 1940s, defines information from the perspective of communication. The underlying model developed by Shannon characterizes information as a message transmitted from a sender to a receiver in a way that the message can be understood by the receiver. In the Shannon model, the actual content of the message is not important, nor is it concerned with whether the message is true or false. The only point of importance is the integrity of the transmission. Because all electronic transmission systems add some level of noise to the signal representing the message, Shannon’s theory is primarily focused on developing efficient methods for encoding and decoding messages so that they are more resilient to transmission noise.
In 1948, Shannon published an article in the Bell System Technical Journal titled The Communications Theory of Secrecy Systems. Shannon was one of the first modern cryptographers to apply advanced mathematical techniques to the study of cryptography. Although the use of frequency analysis for solving substitution encryption began many years earlier, Shannon’s work demonstrated several important features about the statistical nature of language that made the solution to nearly all previous codes very straightforward. Perhaps the most important result of Shannon’s famous paper is the development of a measure of cryptographic strength called the “unicity distance”.
The unicity distance is a number that indicates the amount or quantity of an encrypted message that is required in order to decrypt that message. It is a function of the length of the key used to encrypt the message and the statistical nature of the language in which the original message was written. Given enough time, it is guaranteed that any encrypted message can be broken if the unicity distance is One (1). For example, any time the length of all messages sent under a particular key in English exceeds 2.6 times the length of that key, the key and the original messages eventually can be determined. Encryption systems with an infinite length random key have a unicity distance that is infinite. Shannon found that a message created with an alphabetic substitution encryption system where:
- the key is truly random;
- the key is as large as the plaintext;
- the key is never be reused in whole or part;
- and the key is kept secret, then the message cannot be decrypted from the cipher text alone.
Shannon also introduced the concept of “workload,” which is the difficulty in decrypting a message given the availability of enough ciphertext to theoretically break a code. He showed that an alternative to increasing the unicity distance is the use of systems that increase the workload required to decrypt the message. Two important concepts provided by Shannon in his paper are the “diffusion” and “confusion” properties of encryption. These form the basis for many modern cryptosystems because they tend to increase the workload of cryptanalysis.
Diffusion is the dissipation of the statistical structure behind the language being transmitted. For example, making a different symbol for each English word makes statistical occurrence for many words difficult to detect in the short run, and increases the quantity of data needed to decrypt messages. This difficulty occurs because meaningful words are rarely repeated, and common words such as “the,” “and,” “or,” are frequently repeated. The random use of obscure synonyms for frequently repeated words tends to dissipate the ability to decipher them. Strange sentence structures have a similar effect on the cryptanalysis process.
Confusion is the obscuring of the relationship between the original message, the key, and the encrypted message. For example, if any bit of the key has a 50% chance of affecting any bit in the encrypted message, statistical attacks on the key require solving a large number of simultaneous equations.
Extensions to Shannon’s basic theories include the derivation of an “index of coincidence” that allows approximations of key length to be determined purely from statistical data, the development of semiautomated techniques for attacking cryptosystems, and the concept of using computational complexity for assessing the quality of cryptosystems.4
If done correctly, Shannon called it “perfect secrecy” and further stated in the Bell System Technical Journal, “If properly used, One-Time Pads are secure in the sense even against adversaries with infinite computational power.”
Shannon clarified the fundamentals of cryptography as follows:
- The more random the pattern of a cipher, the more difficult it is for code breakers to decode the message, making it more secure.
- The more random the pattern of a cipher, the more difficult it becomes to share, making it difficult to distribute and less scalable.5
These two factors create a trade-off that defines the science of cryptography and the tug-of-war between security and scalability.
For 75 years, the One-Time Pad has been accepted as the “perfect” unbreakable cipher, but unfortunately it has not been scalable across today’s communications infrastructure, making it unusable for commercial use.
In an effort to describe how a One-Time Pad works, if we were trying to transmit the five-letter word “hello” to a friend using an OTP cipher key, the OTP cipher would transpose the letters. Each letter could be transposed to any of the 26 letters of the alphabet, creating 26 x 26 x 26 x 26 x 26 or almost 12 million unique ways the message could be encoded.
In trying to decode the OTP encoded message, the only piece of information a hacker would know is that the message was five letters long.
The hacker wouldn’t know if the message was hello, later, buzzy, jazzy or any five-letter word that exists, as every one of the 12 million decodings would have an equal probability of being the original message. This equal probability or equal likely outcome to be any five-letter word makes the OTP cipher a perfect cipher, as it doesn’t provide a hacker sufficient information to accurately determine the original message, “hello”.
Any cipher that meets Shannon’s four requirements is not only impossible to break by computing application, as Shannon proved mathematically, is also theoretically impossible to break. Even with unlimited time and unlimited computing power, a hacker would only end up with 12 million possible outcomes, and all of them would have an equal probability of being the message. This equal likely outcome makes the OTP cipher a perfect unbreakable cipher.
