Stream ciphers and the one-time pad

Stream ciphers and keystream unpredictability, the one-time pad's three conditions for perfect secrecy and why they make it impractical, and the repeating-key failure worked through crib dragging's XOR algebra.

Explain how a stream cipher combines a keystream with plaintext, and why the keystream must be unpredictable.
State the three conditions for a one-time pad to achieve perfect secrecy.
Explain why the one-time pad is impractical despite being provably secure.
Derive the crib-dragging relationship P1 XOR P2 from two ciphertexts encrypted under a reused key.

18 min read

Intuition

A block cipher waits until it has a full fixed-size chunk of plaintext before it does anything. A stream cipher does not wait: it generates an unending sequence of bits from the key and combines it with the plaintext as data arrives, one bit or byte at a time. Everything about whether a stream cipher is secure comes down to one question: could an attacker, without the key, tell that sequence apart from true randomness?

Mechanism

A stream cipher generates a keystream $b = b_0, b_1, b_2, \ldots$ from the secret key $k$ by applying some cryptographic function $f(k)$ , then combines it with the plaintext $p = p_0, p_1, p_2, \ldots$ using a bitwise operation, almost always XOR: $c = p \oplus b$ . Examples: RC4, now considered insecure, and Salsa20.

The entire security burden falls on the keystream generator. It must be computationally infeasible for an attacker, without knowing $k$ , to distinguish the keystream from a truly random sequence of bits. If an attacker could find any pattern in it at all, the cipher is broken, whether or not they can yet turn that pattern into recovered plaintext.

Exam detail

The one-time pad (OTP) is a stream cipher too, with one difference that makes all the difference: its keystream is truly random, not merely pseudo-random and generated from a short seed. Not to be confused with the one-time password used in multi-factor authentication: same initials, unrelated concept.

Formula

One-time pad encryption and decryption

c = p \oplus k, \qquad p = c \oplus k

$p$: plaintext bits
$c$: ciphertext bits
$k$: the one-time key (the pad), the same length as p

XOR is its own inverse, so encryption and decryption are the same operation.

Worked example

AnswerSame 8-bit plaintext, two different keys -> two unrelated ciphertexts

The lecture encrypts the same plaintext twice, with two different truly random 8-bit keys, specifically to show that identical plaintext under different one-time keys gives ciphertexts with no visible relationship to each other. Plaintext: 1 0 1 1 1 1 0 1 both times.

Key 1 = 0 1 1 0 0 0 1 1. XOR bit by bit: 1^0=1, 0^1=1, 1^1=0, 1^0=1, 1^0=1, 1^0=1, 0^1=1, 1^1=0.
Ciphertext 1 = 1 1 0 1 1 1 1 0.
Key 2 = 1 1 0 1 0 1 1 0. XOR bit by bit: 1^1=0, 0^1=1, 1^0=1, 1^1=0, 1^0=1, 1^1=0, 0^1=1, 1^0=1.
Ciphertext 2 = 0 1 1 0 1 0 1 1.

Same plaintext, two different keys, two ciphertexts that share no visible relationship: the fundamental property the lecture is illustrating.

Worked example

AnswerBoth ciphertexts decrypt back to the original plaintext

Decryption is the identical XOR operation, run against each ciphertext with its own key.

Ciphertext 1 = 1 1 0 1 1 1 1 0, Key 1 = 0 1 1 0 0 0 1 1. XOR: 1^0=1, 1^1=0, 0^1=1, 1^0=1, 1^0=1, 1^0=1, 1^1=0, 0^1=1.
Recovered plaintext 1 = 1 0 1 1 1 1 0 1.
Ciphertext 2 = 0 1 1 0 1 0 1 1, Key 2 = 1 1 0 1 0 1 1 0. XOR: 0^1=1, 1^1=0, 1^0=1, 0^1=1, 1^0=1, 0^1=1, 1^1=0, 1^0=1.
Recovered plaintext 2 = 1 0 1 1 1 1 0 1.

Both recover the same original plaintext, exactly as encrypted.

Mechanism

OTP achieves perfect secrecy: the ciphertext conveys no information at all about the plaintext, however much of it an attacker collects. In terms of probability, the distribution of possible plaintexts is entirely independent of the ciphertext observed. This holds if, and only if, three conditions on the key all hold.

Exam detail

The key is truly random: not merely unpredictable-looking, but generated by a genuinely random process.
The key is at least as long as the plaintext: $|k| \geq |p|$ .
The key is never reused, not even in part, across more than one message.

It can be proved that any scheme achieving perfect secrecy needs at least as much key material as there is plaintext to encrypt. The one-time pad meets this bound exactly, using exactly one bit of key per bit of plaintext, no more and no less.

Pitfall

“Provably secure” and “practical” are different questions. Despite meeting the strongest security definition cryptography has, the OTP sees almost no real-world use, for two separate reasons. Key distribution: Alice and Bob need a way to securely share a key at least as long as every message they will ever send, and if they already had that channel, they would not need the pad in the first place. Key generation: producing truly random bits at the volume ordinary, frequent communication requires is itself a hard problem. OTPs have seen occasional use only in extremely high-value situations, such as government-to-government “red telephone” links.

Mechanism

Reuse the key, even once, and every guarantee above collapses. A many-time pad, the same key applied to more than one message, can be broken the same way a repeating-key Vigenère cipher can, by the same frequency-based reasoning. A second, more direct method is crib dragging.

Formula

Many-time pad key-reuse relationship

P = C_1 \oplus C_2 = P_1 \oplus P_2

$C_1, C_2$: two ciphertexts produced under the same reused key K
$P_1, P_2$: the plaintexts behind them
$P$: C_1 XOR C_2, independent of the key entirely

Worked example

AnswerC1 XOR C2 = P1 XOR P2, with the key cancelled out entirely

Two plaintexts $P_1$ and $P_2$ are encrypted under the same key $K$ : $C_1 = P_1 \oplus K$ and $C_2 = P_2 \oplus K$ .
An attacker holding both ciphertexts computes $P = C_1 \oplus C_2$ .
Substituting: $P = (P_1 \oplus K) \oplus (P_2 \oplus K)$ .
XOR is commutative and associative, and $K \oplus K$ is all zeros, so the key term cancels: $P = P_1 \oplus P_2$ .
Rearranging gives $P_1 = P \oplus P_2$ and $P_2 = P \oplus P_1$ : either plaintext can be recovered from $P$ and the other one.

Exam detail

This is as far as the lecture’s own algebra goes. Recovering an actual plaintext from $P$ needs a guess to anchor the process: crib dragging. If the language is known, a common word (the lecture suggests “the”) is tried at every position against $P$ . XOR the guess with $P$ at that offset and check whether the result at that same offset in the other plaintext reads as language. A hit at one position often exposes enough surrounding context to extend the guess further, word by word.

The lecture does not work a full crib-dragging session through to completion on this page. It links to an external worked walkthrough instead. What is worked above is the algebra the whole technique rests on, in full; the external example applies exactly this algebra interactively, one guessed word at a time.

Threat

Reusing a keystream, whether in a one-time pad or an ordinary stream cipher, hands an attacker who collects two or more ciphertexts under that key a route to the plaintext that needs no brute force at all: XOR the ciphertexts together, and the key cancels out completely, leaving a relationship between the two plaintexts alone.

Control

The fix is exactly the one-time pad’s own third condition, generalised to any stream cipher: never reuse a keystream. In practice this means a fresh, unpredictable keystream, or a fresh nonce feeding the keystream generator, for every message, without exception. Reuse it once and the cancellation above is available to anyone holding both ciphertexts.

Recall

Two messages are encrypted with the same one-time-pad key. An attacker XORs the two ciphertexts together. What do they get, and why?

They get $P_1 \oplus P_2$ , the XOR of the two plaintexts, entirely independent of the key. Because $C_1 \oplus C_2 = (P_1 \oplus K) \oplus (P_2 \oplus K)$ and $K \oplus K$ cancels to all zeros, the key drops out completely, leaving a relationship an attacker can attack with crib dragging.

Aside

A one-time pad used correctly and a stream cipher are, structurally, the same construction: plaintext XORed with a keystream. The entire difference between “provably unbreakable” and “only as strong as its keystream generator” is whether that keystream is genuinely random or merely computed to look that way.

Source

Week 4 notes PDF