One-Time Pad Reuse — Venona's Fatal Production Failure

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 Venona Project — A Real OTP Failure

The Venona project was a long-running US counterintelligence effort that intercepted Soviet diplomatic and intelligence communications. The Soviets used one-time pads, but in 1942-43, due to a shortage of carbon paper for key duplication, they reused some key pages. The NSA's cryptanalysts, led by Meredith Gardner, discovered the reuse by noticing that two intercepted messages had the same statistical fingerprint when XORed. Over decades, they painstakingly reconstructed the plaintexts, exposing dozens of Soviet spies, including Julius and Ethel Rosenberg, Klaus Fuchs, and Harry Gold.

This is the classic cautionary tale in cryptography: a perfectly secure cipher made completely insecure by a single operational error. The recovery of the plaintexts required enormous manual effort, but modern tools can exploit key reuse in minutes.

import os

def xor_bytes(a: bytes, b: bytes) -> bytes:
    return bytes(x ^ y for x, y in zip(a, b))

# Simulate two plaintexts intercepted
msg1 = b'TOP SECRET: LAUNCH CODES 1234'
msg2 = b'REPORT: AGENT STATUS GREEN'

# Both encrypted with the SAME key (violation!)
shared_key = os.urandom(len(msg1))

ct1 = xor_bytes(msg1, shared_key)
ct2 = xor_bytes(msg2, shared_key)

# Attacker: XOR the two ciphertexts → XOR of plaintexts
xor_pts = xor_bytes(ct1, ct2)
print(f'XOR of plaintexts: {xor_pts}')
print(f'   (Spaces become 0x00, letters XOR to other letters)')

# With known plaintext (e.g., space is common), recover parts
# If we guess 'REPORT' appears in msg2 at start:
guess = b'REPORT'
# XOR guess with xor_pts to reveal corresponding part of msg1
recovered = xor_bytes(xor_pts[:len(guess)], guess)
print(f'Recovered start of msg1: {recovered}')

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.

Key Distribution and Storage Challenges at Scale

Even if you accept the key distribution problem, OTP at scale introduces massive logistical issues. Imagine a diplomatic network with 10 stations, each exchanging 10 MB of messages daily. That's 100 MB of key material each day, all of which must be generated, printed, shipped via diplomatic pouch, inventoried, secured, and destroyed after use. The storage alone for a year's keys exceeds 36 GB — and that's for a small network.

Modern solutions like quantum key distribution (QKD) promise to solve the distribution problem by using quantum physics to share keys over fibre links. But QKD is range-limited and still experimental. In practice, OTP remains a niche tool for scenarios where the key can be pre-shared physically — think of submarines at sea for months, or one-time communication with a remote station.

Frequently Asked Questions