Perfect secrecy: Unbreakable, provably: the one-time pad

Every cipher of the last two chapters fell because the ciphertext carried some trace of the plaintext: letter frequencies, a repeating key, a letter that never encrypts to itself. Is there a cipher whose ciphertext carries no trace at all? In 1882 a Californian banker, Frank Miller, published a telegraph code that added a list of random numbers to the message and threw the list away after use. Nobody noticed. In 1917 Gilbert Vernam, an engineer at AT&T, built the electrical version: the five-bit codes of a teleprinter combined, bit by bit, with the codes of a punched key tape. Army captain Joseph Mauborgne added the two conditions that make it perfect: the tape must be random, and it must never be reused. The result is the one-time pad.

The one-time pad

On bits, the combination is the exclusive or, $\oplus$ : $0 \oplus 0 = 1 \oplus 1 = 0$ and $0 \oplus 1 = 1 \oplus 0 = 1$ . It is its own inverse, $(m \oplus k) \oplus k = m$ , so encryption and decryption are the same operation:

c = m \oplus k, m = c \oplus k, k uniformly random, | k | = | m |, used once.

On letters, the same idea is Vigenère with a random key as long as the message: a key that never repeats leaves Kasiski and Friedman nothing to measure.

The one-time pad on bytes. Top: your message XOR a random pad gives the ciphertext. Bottom: type any other message of the same length; the figure shows the pad that would turn the same ciphertext into it. That pad is exactly as likely as the real one, so the ciphertext alone cannot tell the two messages apart. This is perfect secrecy.

Shannon's definition

During the war Claude Shannon, at Bell Labs, worked on the SIGSALY secure telephone and wrote a classified report on the theory of secrecy, published in 1949 as Communication Theory of Secrecy Systems. It made cryptography a branch of mathematics. Model the message $M$ , the key $K$ and the ciphertext $C$ as random variables.

Definition (perfect secrecy)

A cipher is perfectly secret if seeing the ciphertext does not change what an adversary believes about the message: for every message $m$ and every ciphertext $c$ with $\Pr [C = c] > 0$ ,

\Pr [M = m ∣ C = c] = \Pr [M = m] .

Theorem (the one-time pad is perfectly secret)

If the key $K$ is uniform over ${0, 1}^{n}$ and independent of $M$ , then $C = M \oplus K$ is uniform over ${0, 1}^{n}$ and independent of $M$ .

Proof

For any $m$ and $c$ , $C = c$ given $M = m$ happens exactly when $K = m \oplus c$ , which has probability $2^{- n}$ whatever $m$ is. So $\Pr [C = c ∣ M = m] = 2^{- n} = \Pr [C = c]$ , and by Bayes' rule $\Pr [M = m ∣ C = c] = \Pr [C = c ∣ M = m] \Pr [M = m] / \Pr [C = c] = \Pr [M = m]$ .

No computer, now or ever, quantum or not, can do better than guess. The proof does not depend on any assumption about the attacker's power; this is information-theoretic security. But it has a price.

Theorem (Shannon, 1949)

In any perfectly secret cipher there are at least as many keys as possible messages: $| 𝒦 | \geq | ℳ |$ . In particular, to send $n$ random bits with perfect secrecy you need $n$ bits of key.

Proof

Fix a ciphertext $c$ that can occur. Each key decrypts $c$ to exactly one message, so at most $| 𝒦 |$ messages are possible given $c$ . If $| 𝒦 | < | ℳ |$ , some message $m$ with $\Pr [M = m] > 0$ is impossible given $c$ : $\Pr [M = m ∣ C = c] = 0 \neq \Pr [M = m]$ .

That is why the one-time pad is rare. The key must be generated truly at random, carried to the other side in advance by a trusted courier, stored safely, and destroyed after use. It was used where the cost was worth it: the Washington–Moscow hotline of 1963 ran on one-time tapes, as did spies' radio messages, read from tiny pads of random digits.

The two-time pad

The pad must never be reused, and the reason is one line of algebra:

c_{1} \oplus c_{2} = (m_{1} \oplus k) \oplus (m_{2} \oplus k) = m_{1} \oplus m_{2} .

The key cancels, and what remains is the combination of two natural-language texts, which is full of redundancy. Guess a likely word in one message (a crib), XOR it into $m_{1} \oplus m_{2}$ at every position, and where the guess is right a readable fragment of the other message appears. Each fragment suggests a longer guess.

Breaking a reused pad. Two messages were encrypted with the same random pad; the attacker only has c₁ and c₂. Their XOR does not depend on the pad. Drag a guessed word along it: at the right offsets the other message shows through (highlighted rows are readable). Try short common words, then longer guesses.

This happened. Under wartime pressure the Soviet pad factory printed some pages twice in 1942. Starting in 1943, the US Army's Signal Intelligence Service (Gene Grabeel first, then the linguist Meredith Gardner) exploited the duplicates in the Venona project, eventually reading parts of about 3,000 messages and exposing Soviet spies in the Manhattan Project, among them Klaus Fuchs. The same mistake reappears in modern systems whenever a stream cipher or CTR mode reuses a nonce: in 2017 the KRACK attack forced Wi-Fi devices to reinstall a key and reuse their nonces.

Entropy and the unicity distance

Shannon also measured how much a ciphertext reveals when the key is shorter than the message. The tool is the entropy he had just defined for communication: for a random variable with probabilities $p_{i}$ ,

H (X) = - \sum_{i} p_{i} \log_{2} p_{i} bits,

the average number of bits needed to describe it. A uniformly random letter carries $\log_{2} 26 \approx 4.7$ bits, but English carries only about $1.0$ to $1.5$ bits per letter, because it is highly predictable: the rest, about $3.2$ bits per letter, is redundancy $D$ . Each ciphertext letter therefore gives the attacker about $D$ bits of information about the key.

Estimate (unicity distance, Shannon)

For a cipher whose keys are uniformly random, the length of ciphertext beyond which only one key gives a meaningful plaintext is about

U \approx \frac{H (K)}{D} .

For monoalphabetic substitution, $H (K) = \log_{2} 26! \approx 88.4$ bits and $D \approx 3.2$ , so $U \approx 28$ letters: any longer substitution ciphertext has, in principle, a unique solution.

For a one-time pad $H (K)$ grows with the message and $U$ is infinite; for a 128-bit AES key, a couple of blocks of English already determine the key in principle. Determine it, not find it: finding it would still take $2^{128}$ trials. That difference is the whole of modern cryptography.

From perfect to computational security

Since perfect secrecy needs impractical keys, practical ciphers aim at something weaker: being infeasible to break for an attacker with bounded resources, even though breaking them is possible in principle. Shannon gave the two design principles that every block cipher of the next chapter follows:

Confusion: make the relation between the key and the ciphertext as complex as possible, so that statistics of the ciphertext say nothing simple about the key (non-linear substitutions).
Diffusion: spread the influence of each plaintext bit over many ciphertext bits, so that the redundancy of the language is dissipated (permutations and mixing).

In 1982 Shafi Goldwasser and Silvio Micali gave the modern definition, semantic security: whatever an efficient adversary can compute about the message from the ciphertext, it could compute without it. It is Shannon's definition with “every adversary” replaced by “every efficient adversary”, and it underlies every security proof since.

§The one-time pad

§Shannon's definition

§The two-time pad

§Entropy and the unicity distance

§From perfect to computational security

§Further reading

The one-time pad

Shannon's definition

The two-time pad

Entropy and the unicity distance

From perfect to computational security

Further reading