Stream Ciphers

The One-Time Pad encrypts a plaintext $m \in \{0,1\}^n$ under a uniformly random key $k \in \{0,1\}^n$ by computing $c = m \oplus k$, achieving perfect (information-theoretic) secrecy: the ciphertext reveals literally zero information about $m$. Its fatal flaw is practical, not mathematical — the key must be as long as the message and must never be reused, making it unusable for high-volume communication. A stream cipher keeps the encryption rule $c = m \oplus \text{keystream}$ but replaces the truly random pad with a pseudorandom one. Formally, let $G: \{0,1\}^s \to \{0,1\}^n$ be a PRG that stretches a short seed of length $s$ into a long pseudorandom output of length $n \gg s$. The shared secret key $k \in \{0,1\}^s$ is fed to $G$ to produce a keystream $G(k)$, and encryption is

Decryption is identical: $m = c \oplus G(k)$, since XOR is its own inverse. The entire security of the scheme now rests on one question: can an adversary distinguish $G(k)$ from a truly random string of the same length, without knowing $k$? If not — if $G$ is a secure PRG — then the ciphertext is computationally indistinguishable from a one-time-pad encryption, and the scheme achieves the strongest notion of secrecy achievable without a full-length key: indistinguishability under a single-message eavesdropping attack (IND-EAV / semantic security). Two important refinements make this construction deployable. First, real stream ciphers are usually keyed generators with a nonce: $G(k, \text{IV})$, so that the same key $k$ can safely produce many different keystreams by varying a public initialization vector or nonce per message — this is how a fixed key can be reused across many messages without ever reusing keystream. Second, stream ciphers come in two structural flavors: synchronous stream ciphers, where the keystream depends only on $(k, \text{IV})$ and not on the ciphertext (RC4, ChaCha20, A5/1 are synchronous), and self-synchronizing stream ciphers, where the keystream depends on previously produced ciphertext bits (rare in modern designs, historically used in some CFB-mode constructions). This article focuses on the synchronous case, which is the dominant paradigm and the one that cleanly generalizes the one-time pad.

The mechanics are almost embarrassingly simple compared to the depth of the security argument behind them. Key generation picks a random seed; encryption expands it with the PRG and XORs; decryption re-expands the same seed and XORs again. ``` ALGORITHM StreamCipher // --- Key Generation --- function KeyGen(securityParam s) -> key: k <- Uniform({0,1}^s) // sample a truly random short seed return k // --- Encryption --- // G is a public, fixed PRG stretching s bits to n bits (n = |m|) function Encrypt(k, m): n <- length(m) ks <- G(k, n) // expand seed into n-bit keystream c <- m XOR ks // bitwise XOR, same length return c // --- Decryption --- function Decrypt(k, c): n <- length(c) ks <- G(k, n) // regenerate identical keystream m <- c XOR ks return m // --- Nonce-based variant used in real systems (RC4-style, ChaCha20-style) --- function EncryptWithNonce(k, IV, m): n <- length(m) ks <- G(k, IV, n) // keystream now depends on (k, IV) c <- m XOR ks return (IV, c) // IV sent alongside ciphertext, in the clear function DecryptWithNonce(k, IV, c): n <- length(c) ks <- G(k, IV, n) m <- c XOR ks return m ``` Correctness is immediate: decryption recovers $m$ because

using associativity/commutativity of XOR and $x \oplus x = 0$. The scheme requires the sender and receiver to hold the same key $k$ (and, in the nonce variant, to agree on or transmit the same IV) — this is a private-key (symmetric) primitive. The architecture below shows the data flow for the nonce-based synchronous stream cipher, the form used by ChaCha20 and modern designs.

Time complexity. Encryption and decryption each cost exactly one PRG evaluation plus one XOR over $n$ bits: $O(T_G(n) + n)$, where $T_G(n)$ is the time to produce $n$ bits of PRG output. For stream-oriented PRGs like RC4 or ChaCha20, keystream generation is $O(n)$ with small constants (a handful of ALU operations per output byte), so total encryption/decryption time is linear in the message length, $O(n)$, with no dependence on key length beyond a fixed initialization cost. This is asymptotically optimal — any cipher must read and touch every bit of the message at least once, so $\Omega(n)$ is a lower bound, and stream ciphers meet it.

Space complexity. The scheme needs $O(s)$ space to store the key (and IV), plus whatever internal state the PRG maintains (RC4: a 256-byte permutation table plus two indices; ChaCha20: a 512-bit state block), which is $O(1)$ independent of message length — the keystream is generated incrementally, not stored in full. This is what makes stream ciphers attractive for streaming data of unknown or unbounded length: unlike block ciphers that pad to fixed block sizes, a stream cipher can encrypt one byte at a time as it arrives.

Correctness was shown above via the XOR self-inverse identity; it holds unconditionally, for any function $G$, deterministic or not, keyed correctly on both ends.

Security — the real content. Correctness is trivial; the interesting claim is security, and it must be argued carefully, because the construction only inherits security from $G$ — it does not manufacture it. Define the experiment $\text{PrivK}^{\text{eav}}_{A,\Pi}$: an adversary $A$ picks two equal-length messages $m_0, m_1$; a challenger picks a random key $k$, flips a bit $b$, and returns $c = m_b \oplus G(k)$; $A$ must guess $b$. The scheme is IND-EAV secure if every efficient $A$ guesses correctly with probability at most $\tfrac12 + \text{negl}(s)$. Proof sketch (reduction). Suppose an efficient adversary $A$ wins this game with advantage $\varepsilon$ (i.e., guesses $b$ correctly with probability $\tfrac12 + \varepsilon$). Build a PRG distinguisher $D$ that, given a string $w$ (either $G(k)$ for random $k$, or a truly uniform random string of the same length), runs $A$, computes $c = m_b \oplus w$ for a randomly chosen bit $b$, and outputs $1$ if $A$'s guess equals $b$.

• If $w$ is truly random, then $c = m_b \oplus w$ is a uniformly random string independent of $b$ — this is exactly the one-time pad case, which has perfect secrecy, so $A$ guesses $b$ correctly with probability exactly $\tfrac12$.
• If $w = G(k)$, then $D$ perfectly simulates the real eavesdropping experiment, so $A$ guesses correctly with probability $\tfrac12 + \varepsilon$.

Hence $D$ distinguishes $G(k)$ from random with advantage exactly $\varepsilon$. Since $G$ is a secure PRG, $D$'s advantage must be negligible, forcing $\varepsilon$ to be negligible. This is a tight reduction: the cipher's insecurity is upper-bounded by the PRG's insecurity, and no attack can do better against the cipher than the best attack does against the PRG itself. This is the entire content of "stream ciphers emulate the one-time pad computationally": wherever the one-time pad's argument used true randomness, the reduction substitutes indistinguishability from true randomness, and the eavesdropper's view is unaffected up to negligible probability.

Honest tradeoffs.

• This proof only covers a single ciphertext per key (the "eav" game encrypts once). It says nothing about reusing the same keystream for two messages — and indeed reuse is catastrophically insecure, independent of how good $G$ is (see Worked Example).
• The construction as given is not CCA-secure or even secure against active tampering: XOR encryption is malleable — flipping a ciphertext bit flips the corresponding plaintext bit predictably, so an attacker who can inject ciphertext can make targeted plaintext edits without ever learning the key. Real deployments (e.g., ChaCha20-Poly1305) pair the stream cipher with a MAC for authenticated encryption.
• A PRG is required to be a secure PRG (indistinguishable from random to all efficient adversaries), not merely "look complicated"; historically several deployed generators (RC4's early keystream bytes, A5/1) had statistical biases that violated this and were exploited in real attacks.

We trace a small, explicit instance so the mechanics and the classic vulnerability are both visible in bits, not just symbols. Suppose (toy-sized for clarity) the PRG $G$ maps a 4-bit seed to an 16-bit keystream via some fixed public expansion rule (in a real system this would be RC4/ChaCha20-style; here we hardcode illustrative output).

Decryption: the receiver, holding the same $k$, recomputes $G(k) =$ `1100101100111010` and computes

Now the classic pitfall — keystream reuse ("two-time pad"). Suppose the sender mistakenly reuses the same key (and, in a nonce-based scheme, the same nonce) to send a second message $m_2 =$ "NO" = `0100111001001111`:

An eavesdropper who intercepts both $c_1$ and $c_2$, without knowing $k$ at all, computes:

because $G(k) \oplus G(k) = 0$ cancels exactly. Concretely:

This equals `0100100001001001 XOR 0100111001001111`, the XOR of the two plaintexts — recoverable entirely from public ciphertext, no key needed. Given known structure (English text, known headers, ASCII patterns), $m_1 \oplus m_2$ is frequently enough to recover both $m_1$ and $m_2$ via crib-dragging (guessing likely words in one message and checking if XORing them into $m_1 \oplus m_2$ yields plausible text in the other). This is exactly the attack that broke the original WEP protocol and the Venona project's Soviet one-time-pad reuse in the 1940s — the mathematics is identical whether the "pad" is a true random pad reused, or a PRG-based keystream reused.

The stream cipher idea is the direct engineering descendant of the one-time pad, refracted through the mid-20th-century theory of pseudorandomness and computational hardness.

Stream ciphers are load-bearing infrastructure across the internet and telecommunications stack. TLS 1.2/1.3 offers ChaCha20-Poly1305 as a cipher suite, favored especially on mobile devices lacking AES hardware acceleration, because ChaCha20's PRG-style keystream generation is fast in pure software. WireGuard, a modern VPN protocol, uses ChaCha20 as its sole symmetric cipher. GSM cellular networks historically encrypted voice traffic with the A5/1 stream cipher, whose LFSR-based PRG was eventually shown to be distinguishable from random, enabling real-time call interception. WEP (802.11 Wi-Fi security) built directly on RC4 and was broken largely due to nonce/IV reuse — the exact two-time-pad flaw described above — motivating its replacement by WPA/WPA2. Beyond networking, disk and database encryption products sometimes use stream-cipher-style keystream generation for its low per-byte overhead and suitability for random-access or streaming workloads. The general lesson — build practical encryption from a PRG stretching a short key into a long pseudorandom stream — also underlies the design philosophy of counter-mode (CTR) block cipher operation, which turns a block cipher into a stream cipher by using it as the PRG itself, directly bridging this article to the Pseudorandom Permutation abstraction used to model AES and its relatives.

Ask the tutor: How does CTR mode turn a block cipher into a stream cipher, and does it inherit the same keystream-reuse vulnerability?