Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 40 ยท Symmetric Encryption

XOR and the One-Time Pad

Learn how XOR encryption works, why the one-time pad is the only cipher with perfect secrecy, and how reusing a key lets attackers recover messages.

The XOR operation (exclusive or) is the quiet workhorse of symmetric cryptography. Almost every stream cipher, block-cipher mode and hash function mixes data with XOR somewhere inside. It is cheap, it never loses information, and it undoes itself. If you XOR a message with a key, you get a ciphertext; XOR the ciphertext with the same key and the message is back.

Used with a key that is truly random, as long as the message and never reused, XOR gives the one-time pad, which is provably unbreakable. Used carelessly, it falls apart in minutes. This lesson shows both sides and sets up the rest of the Symmetric Encryption chapter. If bytes and hex are unfamiliar, review encoding, hashing and encryption first.

How XOR works

XOR compares two bits and outputs 1 when they are different, 0 when they are the same:

a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

In Python the operator is ^. On whole bytes it works bit by bit. Four facts make it useful: a ^ a = 0, a ^ 0 = a, it is commutative and associative, and therefore (m ^ k) ^ k = m.

Python XOR as an encryption step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the last line: XOR does not hide the relationship between the plaintext, the ciphertext and the key. Any two of them give you the third. If an attacker knows a piece of plaintext (a "crib"), they recover the matching key bytes. This is the weakness that everything below revolves around.

A key shorter than the message that repeats is the weak repeating-key XOR cipher, effectively a Vigenere cipher over bytes: it is broken by guessing the key length and then solving each position by frequency analysis, as in classical ciphers. The fix is a key as long as the message.

The one-time pad

The one-time pad (OTP), patented by Gilbert Vernam in 1917, applies XOR with a key that satisfies four conditions:

  1. The key is truly random (not a pseudorandom stream; see randomness and entropy).
  2. The key is at least as long as the message.
  3. The key is used only once.
  4. The key is kept secret and shared securely in advance.

Claude Shannon proved in 1949 that these conditions give perfect secrecy: the ciphertext tells an attacker nothing about the plaintext, except its length, even with unlimited computing power. The intuition is that for a given ciphertext, every plaintext of the same length is possible, each with a matching key, and all keys are equally likely.

flowchart LR
    M["Plaintext m"] --> X["XOR"]
    K["Random key k<br/>same length, used once"] --> X
    X --> C["Ciphertext c = m XOR k"]
    C --> Y["XOR with k"]
    K --> Y
    Y --> M2["Plaintext m"]

Encryption and decryption are the same operation, XOR with the pad.

Python Perfect secrecy: every message fits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

No attacker could tell the three candidates apart, because each has a key that explains the ciphertext just as well. That is perfect secrecy.

Why is the OTP not used everywhere, then? Because the conditions are brutal. You must securely deliver as much random key material as the total traffic, and never reuse a single byte. If you could securely hand someone a key that long, you could have handed them the message. The OTP survives in niches (diplomatic and espionage traffic, where pads were distributed in advance), and its ideas live on in stream ciphers, which replace the true random pad with a pseudorandom keystream generated from a short key (stream ciphers). That trade gives up perfect secrecy for practicality and security that rests on computational hardness instead.

Another property to remember: the OTP gives no integrity. An attacker who flips a ciphertext bit flips exactly the same plaintext bit. If they know the message format, they can change a payment amount without knowing the key. Secrecy and authenticity are separate goals (see authenticated encryption).

The two-time pad attack

What if the pad is used twice? Let c1 = m1 XOR k and c2 = m2 XOR k. Then:

c1 XOR c2 = m1 XOR m2

The key cancels, and the attacker holds the XOR of the two plaintexts. Natural language is redundant, so this is usually enough to read both. The standard technique is crib dragging: guess a common word, XOR it at every position of c1 XOR c2, and look for positions where the result is readable text. Each readable fragment is a piece of the other message, and each gives more key bytes to extend the guess.

The attack was used by Allied codebreakers against Soviet traffic in the Venona project, after pads were duplicated under wartime pressure. It also explains why nonce reuse in stream ciphers is fatal.

Python Crib dragging a reused pad

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Of 62 positions, only six look like lowercase text, and four of them are real fragments (hipme, ct an, orth, unris); the other two are chance matches that the attacker discards. The attacker iterates: try more cribs ("the", "and", names, "attack"), extend each confirmed fragment in both messages, and the two plaintexts emerge piece by piece. No key was ever recovered by guessing it directly; the repeated pad is the whole weakness.

Warning: "Key reuse" does not just mean using the same pad twice by hand. Any system that produces the same keystream twice, such as a stream cipher with a repeated nonce, a PRNG restarted with the same seed, or a counter that rolls over, creates a two-time pad.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is (m XOR k) XOR k?

    XOR is its own inverse: k XOR k is 0 and anything XOR 0 is itself, so the second XOR with k restores m.
  2. 2. Which condition is NOT required for a one-time pad to give perfect secrecy?

    A short password cannot supply a truly random, message-length key. Deriving a keystream from a short key gives a stream cipher, which is only computationally secure.
  3. 3. An attacker has c1 and c2, encrypted with the same pad. What can they compute directly?

    c1 XOR c2 = (m1 XOR k) XOR (m2 XOR k) = m1 XOR m2, because the key cancels.
  4. 4. Does the one-time pad protect a message against tampering?

    XOR encryption is malleable. Integrity needs a separate MAC or an authenticated encryption mode.

Summary

  • XOR is its own inverse, so (m ^ k) ^ k = m; it appears inside nearly every modern cipher.
  • Repeating-key XOR is weak; any known plaintext reveals the matching key bytes.
  • A one-time pad (random, message-length, secret, used once) has perfect secrecy, but distributing the pad is impractical.
  • Reusing a pad leaks m1 XOR m2, and crib dragging usually recovers both messages.
  • XOR encryption gives no integrity: attackers can flip plaintext bits by flipping ciphertext bits.

Next: Stream Ciphers and Keystreams.