ZipKit
Glossary

OTP (One-Time Pad)

OTP stands for one-time pad, a cipher that combines a message with a truly random key as long as the message, and uses that key only once. It is the only cipher proven to give perfect secrecy, shown by Claude Shannon in 1949. In developer circles OTP also means one-time password, as in TOTP codes, which is a different thing entirely.

How it works

Encryption is XOR, bit by bit, of plaintext and key. Decryption is the same XOR with the same key. Three conditions must hold at once:

  • Truly random key: every key bit is independent and unbiased. A pseudorandom generator does not qualify, since then it is a stream cipher.
  • Key as long as the message: a 14-byte message needs a 14-byte key. There is no shorter-key shortcut.
  • Never reused: each key byte encrypts exactly one plaintext byte, ever.

Gilbert Vernam of AT&T filed the patent for the XOR teleprinter system on September 13, 1918, and it was granted as US 1,310,719 on July 22, 1919. The reason the secrecy is perfect: for any ciphertext, every plaintext of the same length is equally possible, because some key maps to it. The example shows this with one 14-byte ciphertext.

pt = b"ATTACK AT DAWN"
key = bytes.fromhex("5d1c0b7a93e24f6618d0aa3c7e41")
ct = bytes(a ^ b for a, b in zip(pt, key))
print(ct.hex())
for guess in (b"ATTACK AT DAWN", b"RETREAT AT SIX"):
    k2 = bytes(a ^ b for a, b in zip(ct, guess))
    print(guess.decode(), k2.hex())
1c485f3bd0a96f274cf0ee7d290f
ATTACK AT DAWN 5d1c0b7a93e24f6618d0aa3c7e41
RETREAT AT SIX 4e0d0b6995e83b070da4ce2e6057

The ciphertext decrypts to "RETREAT AT SIX" under a different, equally plausible key. An attacker cannot tell which key is right, so brute force reveals nothing.

What happens if you reuse a one-time pad key?

The pad stops being unbreakable at once. XORing two ciphertexts made with the same key cancels the key and leaves the XOR of the two plaintexts. With the key above, "ATTACK AT DAWN" and "RETREAT AT SIX" gave 13110013060a7461157464121e16 for both the ciphertext XOR and the plaintext XOR. From that, an analyst can guess words and recover both messages. This reuse is the weakness that let the US Venona project read some Soviet traffic (via search summary).

Why isn't OTP used everywhere?

Because the key must be exchanged securely and is as large as all the data. To protect 1 GB you must safely deliver and store 1 GB of random key, and destroy each part after use. Modern ciphers such as AES-CTR and ChaCha20 replace the random pad with a short key and a keystream generator, trading perfect secrecy for practicality.

Common pitfalls

  • Generating the pad with a PRNG: Math.random or a seeded generator gives a predictable pad and no perfect secrecy. Use physical randomness or an OS CSPRNG, and know that this is then computational security only.
  • Reusing any part of a pad: a repeated stretch leaks the XOR of the plaintexts for that stretch.
  • No authentication: XOR is malleable. Flipping a ciphertext bit flips the same plaintext bit, so an attacker can change a payment amount without knowing the key. Add a MAC.
  • Shorter key repeated: repeating a short key over a long message is the Vigenere cipher, which is breakable.
  • Confusing it with one-time passwords: TOTP and HOTP codes are HMAC-based and unrelated to the pad.

Related terms

  • AES-CTR — a stream mode that stretches a short key into a keystream.
  • ChaCha20 — a stream cipher with a computational, not perfect, security guarantee.
  • Caesar Cipher — a one-letter-key shift cipher.
  • Vigenere Cipher — repeating-key cipher that a short key makes breakable.
  • AES — the block cipher behind practical stream modes.

See also