One-Time Pad — Perfect Secrecy Explained

In 1949, Claude Shannon published 'Communication Theory of Secrecy Systems' and proved something remarkable: the one-time pad achieves perfect secrecy. Given a ciphertext, every possible plaintext of the same length is equally probable — an attacker with infinite computational power learns exactly nothing. This is not a computational hardness assumption (like RSA or AES). It is an information-theoretic proof. No algorithm, no quantum computer, no advance in mathematics can break a correctly used one-time pad.

The one-time pad was used for the Moscow-Washington hotline during the Cold War. It secures communications between heads of state today when cost is no object. Understanding why it is perfectly secure — and why it is almost never used — is a fundamental lesson in the gap between theoretical security and practical cryptography.

Shannon's Perfect Secrecy Proof

A cipher achieves perfect secrecy if P(plaintext | ciphertext) = P(plaintext) — knowing the ciphertext gives you no information about the plaintext. The one-time pad achieves this when: (1) key is truly random, (2) key length = message length, (3) key is never reused.

For any ciphertext C and any plaintext P of the same length, there exists exactly one key K = C XOR P that would produce C from P. Since all keys are equally probable, all plaintexts are equally probable given C. An adversary cannot distinguish between any two plaintexts.

import os

def otp_encrypt(plaintext: bytes) -> tuple[bytes, bytes]:
    """Encrypt using one-time pad. Returns (ciphertext, key)."""
    key = os.urandom(len(plaintext))  # truly random key
    ciphertext = bytes(p ^ k for p, k in zip(plaintext, key))
    return ciphertext, key

def otp_decrypt(ciphertext: bytes, key: bytes) -> bytes:
    return bytes(c ^ k for c, k in zip(ciphertext, key))

msg = b'ATTACK AT DAWN'
ct, key = otp_encrypt(msg)
print(f'Ciphertext: {ct.hex()}')
print(f'Decrypted:  {otp_decrypt(ct, key)}')

# Perfect secrecy demonstration:
# The SAME ciphertext can decrypt to ANY message with the 'right' key
forged_key = bytes(c ^ m for c, m in zip(ct, b'DEFEND AT DUSK'))
print(f'Alternative decryption: {otp_decrypt(ct, forged_key)}')
# Both are valid — the ciphertext reveals nothing

Why OTP is Impractical

The one-time pad fails the practical cryptography test on three counts:

Key distribution problem: You must securely share a key as long as every message you will ever send. If you have a secure channel to share the key, why not use that channel to send the message itself?

Key storage: Keys must be stored securely and destroyed after use. A 1GB key file protects 1GB of messages. At scale, this is logistically untenable.

No reuse: Reusing a key is catastrophic. In WWII, Soviet intelligence used OTP-encrypted messages for the Venona project. Due to a one-time pad shortage in 1942-43, some pages were duplicated and reused. The NSA's SIGINT program spent decades exploiting those reused pads, exposing Soviet agents including Julius Rosenberg. The same attack — XORing two ciphertexts encrypted with the same key — reveals the XOR of the two plaintexts, which leaks enough information to reconstruct both.

The Vernam Cipher and Stream Ciphers

Gilbert Vernam patented the electrical OTP in 1917 for use with teletype machines, using punched paper tape for keys. His original patent used a repeating key (which is insecure — essentially a Vigenère cipher). OTP security requires the key to be truly random and non-repeating.

Modern stream ciphers (ChaCha20, AES-CTR) are computationally secure approximations of OTP: they generate a cryptographically random-looking keystream from a small seed (the key). The keystream is indistinguishable from random to any polynomial-time adversary. This gives computational security (not perfect secrecy) with practical key sizes.

Frequently Asked Questions