The One-Time Pad

Why the one-time pad matters

Almost every cipher you use — AES, RSA, ChaCha20 — is computationally secure. It is safe because breaking it would take more work than any attacker can afford, given today's hardware and today's best-known algorithms. That is a bet against progress. The one-time pad makes no such bet. Its security is unconditional: even an adversary with infinite time, infinite computers, and a working quantum machine cannot recover the plaintext, because the information simply is not present in the ciphertext.

That makes the pad the theoretical ceiling of cryptography — the yardstick every other scheme is measured against. It also makes it a beautifully sharp illustration of a deep idea: secrecy is a resource that must be moved, not manufactured. The pad does not create confidentiality out of a short password; it demands that you already possess as much secret key as the total volume of secret message. Understanding why that trade is unavoidable is understanding the central limit of secret-key cryptography.

How the one-time pad works, step by step

The construction is almost embarrassingly simple. Represent everything as bits.

• Key generation. Alice and Bob share a secret key K — a string of n truly random bits, one for each bit of the message. "Truly random" means every bit is an independent fair coin flip, from a physical entropy source, not a pseudo-random generator.
• Encryption. To send an n-bit message M, compute the ciphertext bit by bit: C = M ⊕ K, where ⊕ is XOR (addition modulo 2).
• Decryption. Bob computes M = C ⊕ K. This works because XOR is its own inverse: (M ⊕ K) ⊕ K = M ⊕ (K ⊕ K) = M ⊕ 0 = M.
• Destroy the key. Both parties erase the used portion of K. It is never reused for anything, ever. Hence the name: each pad page is used once, then burned.

The whole cipher is n XOR operations to encrypt and n to decrypt — O(n) time, O(1) extra space, trivially parallel and constant-time by construction. There are no rounds, no S-boxes, no key schedule. All the difficulty lives in producing and delivering the key.

Shannon's perfect secrecy — the proof sketch

Shannon defined perfect secrecy precisely: a cipher is perfectly secret if, for every plaintext m and every ciphertext c,

Pr[M = m | C = c] = Pr[M = m].

In words: seeing the ciphertext does not change your beliefs about the message at all. The ciphertext and plaintext are statistically independent. Equivalently, the mutual information I(M; C) = 0.

The pad satisfies this. Fix any ciphertext c. For a candidate message m to produce it, the key must be exactly k = c ⊕ m — a unique key. Since the key is uniformly random over all 2ⁿ possibilities, that specific key occurs with probability 2⁻ⁿ, independent of what m is. So Pr[C = c | M = m] = 2⁻ⁿ for every message. Because that likelihood is the same for all messages, observing c tells the attacker nothing about which message was sent. Every plaintext of length n is a valid decryption of c under some key, and all are equally likely.

Shannon also proved the converse — his impossibility theorem: any perfectly secret cipher must use a key at least as large as the message space entropy, i.e. H(K) ≥ H(M). So the pad's enormous key is not an implementation clumsiness you can optimize away; it is mathematically required of any scheme that hopes to be perfectly secret. You cannot get perfect secrecy on the cheap.

One-time pad vs. computational ciphers

	One-Time Pad	Stream Cipher (ChaCha20)	Block Cipher (AES)	RSA
Security model	Information-theoretic (perfect)	Computational	Computational	Computational
Key size	= message length	256-bit fixed	128/256-bit fixed	2048–4096-bit
Keystream source	True randomness	PRNG from short seed	PRNG (in stream modes)	Modular arithmetic
Breakable with infinite compute?	No	Yes	Yes	Yes
Quantum-safe?	Yes	Yes (256-bit)	Yes (256-bit)	No (Shor's algorithm)
Key reuse tolerated?	No (fatal)	No (fatal — same flaw)	Yes (fresh IV)	Yes
Practical for the internet?	No (key distribution)	Yes	Yes	Yes

Notice the middle column: a stream cipher is a one-time pad in which the truly random key has been replaced by the pseudo-random output of a PRNG seeded with a short key. It inherits the pad's XOR structure — and the pad's absolute prohibition on keystream reuse — while giving up perfect secrecy in exchange for a 256-bit distributable key. Every practical stream cipher is a deliberate, security-for-convenience downgrade of the pad.

Implementation in Python

import os

def keygen(n_bytes: int) -> bytes:
    # Truly random key from the OS entropy pool — NOT a seeded PRNG.
    # In a real pad this key is pre-shared out of band and never reused.
    return os.urandom(n_bytes)

def otp(data: bytes, key: bytes) -> bytes:
    # Encryption and decryption are the same operation: XOR.
    if len(key) < len(data):
        raise ValueError("key must be at least as long as the message")
    return bytes(d ^ k for d, k in zip(data, key))

# --- usage ---
message = b"ATTACK AT DAWN"
key = keygen(len(message))          # 14 random bytes, used exactly once

ciphertext = otp(message, key)      # C = M XOR K
recovered  = otp(ciphertext, key)   # M = C XOR K   (same function)

assert recovered == message
# After this, `key` must be destroyed and never used again.

Two lines carry the whole security story. os.urandom pulls from the operating system's cryptographic entropy source — if you swap it for a seeded random.Random, you have silently built a stream cipher and thrown away perfect secrecy. And the length check enforces the non-negotiable rule that key ≥ message. There is no separate decrypt function because XOR is an involution: the same otp call recovers the plaintext.

Common misconceptions and pitfalls

• "It's unbreakable, so it's the best cipher." Perfect secrecy is only about confidentiality. The pad is completely malleable: flip ciphertext bit i and you flip plaintext bit i, no key required. Without a separate MAC, an attacker can edit your message even without reading it.
• Reusing a key page ("two-time pad"). If C₁ = M₁ ⊕ K and C₂ = M₂ ⊕ K, then C₁ ⊕ C₂ = M₁ ⊕ M₂ — the key vanishes and the redundancy of natural language does the rest (crib-dragging). This single mistake is what the VENONA project exploited against Soviet cables.
• Using a PRNG for the key. A software PRNG has at most as much entropy as its seed. Feed it a 256-bit seed and the "pad" has only 256 bits of real randomness no matter how long it is — that is a stream cipher wearing a pad's clothes, and it is computationally, not perfectly, secure.
• Assuming length is hidden. Perfect secrecy hides the content, not the length. The ciphertext is the same size as the plaintext, so the message length always leaks. Pad your messages to a fixed size if length is sensitive.
• Forgetting to destroy the key. Compromise of the pad after the fact reveals every message ever sent under it. Forward secrecy comes from actually erasing consumed key material.

A worked history — Vernam, VENONA, and the hotline

In 1919 Gilbert Vernam of AT&T patented an automatic telegraph cipher (U.S. Patent 1,310,719) that XOR-ed the 5-bit Baudot code of each character with a key tape. Joseph Mauborgne of the Army Signal Corps supplied the missing insight: only if the key tape is truly random and used a single time does the scheme become unbreakable. (Frank Miller had sketched a similar idea for telegraphy back in 1882.) For thirty years the "unbreakable" claim was folklore — until Claude Shannon's 1949 paper Communication Theory of Secrecy Systems proved it rigorously and defined perfect secrecy, founding modern cryptography in the process.

The pad's Achilles' heel showed up in practice, not theory. During and after World War II, overwhelmed Soviet cipher clerks reused pad pages. Starting in 1943 the U.S. Army's VENONA program detected the duplicate keys and, over decades, decrypted thousands of messages — exposing espionage networks. The pad had not failed; its operators had. Where discipline held, the pad reigned: the Moscow–Washington "red telephone" hotline, established in 1963, ran on one-time pads whose key material was hand-carried between the capitals by trusted couriers. That is the pad's true niche — small volumes of the highest-value traffic between parties who can physically pre-share bulk key.

The key distribution problem — the unbeatable catch

Here is the circularity that keeps the pad out of everyday use. To send n secret bits, you must first deliver n secret key bits over a secure channel. But a channel secure enough to move n key bits could have carried the n-bit message itself. The pad never generates secrecy — it merely relocates the confidentiality requirement from the message to a key of identical size. For two people who exchange gigabytes of traffic, that means pre-sharing gigabytes of key by courier, then never running out.

This is precisely the gap that public-key cryptography was invented to close. Diffie–Hellman and RSA let strangers agree on a short key over an insecure line, trading the pad's perfect secrecy for computational security — but buying the ability to communicate without a courier. And quantum key distribution (BB84) attacks the problem from the other side: it uses the laws of physics to deliver fresh random key that an eavesdropper cannot copy, which is then consumed by a genuine one-time pad. The pad remains the gold standard; the entire history of practical cryptography is the search for a cheaper way to get its key where it needs to go.