Stream Ciphers Explained: RC4, LFSRs, Salsa20/ChaCha, and the Nonce Reuse Trap
Before You Read
You should already be comfortable with XOR as a bitwise operation and know roughly what a block cipher (AES, DES) does, since this post repeatedly contrasts stream ciphers against that model. No prior LFSR or RC4 knowledge is assumed; both are built up from scratch. By the end you’ll understand how RC4, LFSR-based, and Salsa20/ChaCha keystream generators actually work internally, why plain LFSRs and RC4 are both broken in practice (for different mathematical reasons), and exactly why reusing a (key, nonce) pair is a total, key-independent break rather than a minor weakening.
What a Stream Cipher Actually Does
A stream cipher takes two inputs: a secret key (128 or 256 bits, typically) and a public, non-secret nonce (“number used once,” usually 64 to 128 bits). It expands them into a long pseudorandom sequence of bits called the keystream. Encryption is nothing more than ciphertext = plaintext XOR keystream. Decryption runs the exact same operation: plaintext = ciphertext XOR keystream, because XOR is its own inverse: XOR a value with the same bits twice and you get the original value back.
That self-inverse property matters more than it looks. Encrypt and decrypt are literally the same code path applied twice. There’s no separate decrypt routine that could drift out of sync with encrypt, no second implementation to audit for a mismatched bug. One function, two roles.
This makes a stream cipher, at its core, a deterministic keystream generator. That’s a sharper claim than “random number generator.” A true random source never has to repeat itself. A stream cipher must be exactly reproducible: hand it the same (key, nonce) pair twice and it has to emit the identical keystream both times, or the receiver could never regenerate it to decrypt. The nonce’s whole job is to make that keystream different every time the same key gets reused, without needing a fresh secret key for every single message.
Picture a three-person group chat where everyone shares one symmetric key, and the server tags each outgoing message with a sequential nonce: message #41, #42, #43. Same key throughout, but each message rides its own nonce, so each keystream comes out completely different even though nothing about the key changed.
import hashlib
def keystream(key: bytes, nonce: bytes, length: int) -> bytes:
# placeholder keystream generator: not a real cipher, just stands in
# for "expand (key, nonce) into pseudorandom bytes" for this demo
h = hashlib.shake_128(key + nonce)
return h.digest(length)
def xor_bytes(a: bytes, b: bytes) -> bytes:
return bytes(x ^ y for x, y in zip(a, b))
key = b"group-chat-secret-key-32bytes!!"
messages = {
41: b"lunch at noon?",
42: b"works for me",
43: b"see you there",
}
for msg_id, plaintext in messages.items():
nonce = msg_id.to_bytes(8, "big")
ks = keystream(key, nonce, len(plaintext))
ciphertext = xor_bytes(plaintext, ks)
print(f"message #{msg_id}: nonce={nonce.hex()} plaintext={plaintext!r}")
print(f" ciphertext: {ciphertext.hex()}")Running that against three one-line messages and then round-tripping a fourth message under two different nonces:
Three messages, one shared key, sequential nonces:
message #41: nonce=0000000000000029 plaintext=b'lunch at noon?'
ciphertext: 0b1d08bd7b7841db09a41e8e519a
message #42: nonce=000000000000002a plaintext=b'works for me'
ciphertext: 7a59da10f7b6dc52e71f00f4
message #43: nonce=000000000000002b plaintext=b'see you there'
ciphertext: 7ebfbece1f24da6e9dc0ad9f4f
Round trip with explicit nonce reuse check (same plaintext, two nonces):
plaintext: b'hello world'
nonce 0000000000000064 -> ciphertext 3000290a09d0cd1442eaf8
nonce 0000000000000065 -> ciphertext 43da9eb74e1967a6b559e0
decrypt ct_a with same keystream: b'hello world'Same key both times, but the ciphertexts share no visible pattern with each other, because the nonce changed. Same plaintext (“hello world”), two different nonces, two completely unrelated ciphertexts. That last case is worth staring at for a second: it’s the whole reason nonces exist, and it previews exactly what goes wrong later in this post when a nonce gets reused instead of changed.
flowchart LR
K[Secret key] --> G[Keystream generator]
N[Nonce<br/>public, unique per message] --> G
G --> KS[Keystream bits]
P[Plaintext] --> X((XOR))
KS --> X
X --> C[Ciphertext]Stateful vs. Counter-Based Stream Ciphers
Every stream cipher falls into one of two architectural families, and the difference shapes what you can do with the ciphertext later.
A stateful stream cipher, RC4 being the classic example, keeps an internal secret state that mutates every single time it emits keystream bits. Byte 500 of the keystream depends on everything the cipher has already produced before it, which means you have to run the cipher sequentially from the very start to get there. There’s no shortcut.
A counter-based stream cipher (Salsa20, ChaCha, AES-CTR) works differently. Each keystream block is derived independently from the key, the nonce, and an explicit counter value, with no evolving secret state carried between blocks. Plug in counter value 1000 and you get keystream block 1000 directly, no replay required.
That difference has a very concrete payoff: random access. Decrypting byte 1,000,000 of an RC4-encrypted stream means replaying the entire keystream from byte zero, there’s no way around it. Decrypting the same offset in a ChaCha20-encrypted file means computing counter value 1,000,000 / 64 directly and generating just that one block. The counter-based design also parallelizes trivially: different blocks can be computed on different CPU cores simultaneously, since none of them depend on each other.
flowchart TB
subgraph Stateful["Stateful (RC4)"]
S0[state 0] --> S1[state 1] --> S2[state 2] --> S3["... state 999"] --> S1000[state 1000<br/>needed for byte 1000]
end
subgraph Counter["Counter-based (ChaCha20)"]
direction LR
C1000["counter = 1000"] --> B1000["block 1000<br/>computed directly"]
endFeedback Shift Registers and Why Plain LFSRs Fail
Before RC4 and ChaCha, hardware-oriented stream ciphers were mostly built from feedback shift registers, and it’s worth understanding why the plain version of that idea doesn’t survive contact with an attacker.
A feedback shift register (FSR) is an array of bits. On each clock tick it shifts every bit one position, outputs whichever bit falls off the end, and fills the newly empty slot using a feedback function computed from the current state. When that feedback function is nothing more than an XOR of a fixed subset of the register’s bits, it’s a linear feedback shift register (LFSR), and the specific bit positions that get XORed together are called the taps.
A few facts about LFSRs matter for what comes next. The sequence of states before the register repeats itself is its period. For an n-bit register the theoretical ceiling on that period is 2^n minus 1, not 2^n, because the all-zero state is a fixed point: it feeds back into itself forever and produces nothing but zeros, so it’s excluded from any real cycle. Hitting that 2^n - 1 ceiling requires the taps to correspond to what’s called a primitive polynomial, and most random choices of taps don’t land on one.
Stage 1: Sweeping tap choices to see who gets the maximal period
To make that concrete instead of asserting it, here’s a 6-bit LFSR swept across every possible nonzero tap combination, all 63 of them, starting from the same fixed seed each time:
from collections import Counter
N = 6 # register width in bits
SEED = [1, 0, 1, 1, 0, 1] # fixed nonzero 6-bit seed
def run_lfsr(taps, seed, max_steps=200):
"""Run a Fibonacci LFSR with given tap positions (0-indexed into state).
Returns period: number of clocks until the state repeats the seed."""
state = list(seed)
start = tuple(state)
for step in range(1, max_steps + 1):
fb = 0
for t in taps:
fb ^= state[t]
state.pop() # bit that falls off the end
state.insert(0, fb) # feedback fills the new slot
if tuple(state) == start:
return step
return None
period_tally = Counter()
for mask in range(1, 2**N):
taps = [i for i in range(N) if (mask >> i) & 1]
period = run_lfsr(taps, SEED, max_steps=200)
if period is not None:
period_tally[period] += 1Tallying how many of the 63 tap-sets land on each period value:
6-bit LFSR, seed=[1, 0, 1, 1, 0, 1], swept 63 nonzero tap subsets
theoretical max period (2^6 - 1) = 63
period 3: 16 tap-sets ################
period 5: 2 tap-sets ##
period 7: 1 tap-sets #
period 8: 2 tap-sets ##
period 9: 1 tap-sets #
period 14: 2 tap-sets ##
period 21: 2 tap-sets ##
period 28: 2 tap-sets ##
period 30: 2 tap-sets ##
period 31: 8 tap-sets ########
period 63: 6 tap-sets ######
tap-sets reaching maximal period 63: 6 of 63
example maximal tap-set: [0, 5]
16 of the 63 tap choices collapse to a period of just 3. Only 6 reach the full 63. Register size alone tells you nothing about how random the output looks; tap choice is what determines it, and getting that choice right requires actual number theory, not guessing.
Stage 2: Recovering an LFSR from its own output
Short period is bad, but it’s not even the real problem. The real problem is linearity. LFSR output bits are a linear function of the initial state, which means an attacker who observes just n consecutive output bits from an n-bit LFSR can reconstruct the taps and the full initial state by solving a small linear system. The Berlekamp-Massey algorithm does exactly this, efficiently, and once it succeeds the attacker can predict every future bit the register will ever produce, regardless of how long its period is.
Here’s Berlekamp-Massey run over GF(2), fed only the first 12 bits (2n, for n = 6) from the maximal-period tap-set [0, 5] found in Stage 1:
def berlekamp_massey(bits):
"""Berlekamp-Massey over GF(2). Returns (connection_poly, linear_complexity)."""
n = len(bits)
C = [1] + [0] * n
B = [1] + [0] * n
L = 0
m = 1
for N_ in range(n):
discr = bits[N_]
for i in range(1, L + 1):
discr ^= C[i] & bits[N_ - i]
if discr == 0:
m += 1
elif 2 * L <= N_:
T = C[:]
for i in range(len(B)):
if i + m < len(C):
C[i + m] ^= B[i]
L = N_ + 1 - L
B = T
m = 1
else:
for i in range(len(B)):
if i + m < len(C):
C[i + m] ^= B[i]
m += 1
return C, L
# observed = the LFSR's own first 12 output bits, nothing else
C, L = berlekamp_massey(observed)
# the recurrence BM finds is: s[k] = XOR_{i=1..L} C[i] * s[k-i]
history = list(observed[:L])
for k in range(L, 40):
val = 0
for i in range(1, L + 1):
val ^= C[i] & history[k - i]
history.append(val)attacker observes first 12 output bits: [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1]
Berlekamp-Massey recovered linear complexity L = 6 (register size was 6)
recovered connection polynomial C(x) coefficients, C[1..L] = [1, 0, 0, 0, 0, 1]
predicting 40 bits forward using only the recurrence learned from the first 6 bits:
predicted: [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0]
actual: [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0]
match: TrueTwelve bits, and the algorithm hands back the exact taps and enough state to predict the next 28 correctly. This is the same tap-set that reached the maximal period of 63 in Stage 1. Maximal period bought it nothing: it’s still completely transparent to anyone holding a handful of output bits.
Hardening LFSRs: Filters, Nonlinearity, and Real Hardware Ciphers
Raw LFSRs are linear, hence solvable, so real hardware-oriented designs fix that in one of two ways. A filtered LFSR passes the LFSR’s output through a separate nonlinear function (AND/OR combinations, not just XOR) before it’s used as keystream. An NFSR makes the feedback function itself nonlinear instead of a plain XOR of taps. Either way, nonlinearity is what defeats the linear-algebra recovery attack that Berlekamp-Massey runs.
There’s a real tradeoff buried in that choice. For a plain LFSR, the primitive-polynomial test tells you instantly, on paper, whether a given tap set reaches the maximal period. No equivalent shortcut exists for an NFSR. Confirming that a chosen nonlinear feedback function actually reaches its maximal period means brute-force simulating the register through nearly its entire state space, which is infeasible to check at design time for any register wide enough to be useful for anything.
The standard fix in practice sidesteps having to choose one or the other: run an LFSR and an NFSR side by side, and combine their outputs with a nonlinear mixing function. The LFSR half supplies a provable long period. The NFSR-plus-mixer half supplies resistance to the algebraic attacks that would otherwise break it. This hybrid pattern is what hardware-oriented ciphers for constrained devices, smart cards, RFID tags, embedded sensors, actually use. It’s background for what follows: software-oriented ciphers like RC4 and Salsa20 abandoned shift registers entirely and took a completely different approach.
RC4: Generating a Keystream from Byte Swaps
RC4 keeps its entire secret state in one place: a 256-byte array S, initialized to the identity permutation 0 through 255. Setting it up is a two-stage process.
Stage 1: Key scheduling
The key-scheduling algorithm (KSA) walks through all 256 positions once, mixing in the secret key bytes (cycling through them if the key is shorter than 256 bytes) and swapping array entries as it goes. By the end, S is a key-dependent, seemingly random shuffle of the byte values 0 through 255.
def rc4_ksa(key: bytes):
"""Key-scheduling algorithm: build the 256-byte permutation S from the key."""
S = list(range(256))
j = 0
for i in range(256):
j = (j + S[i] + key[i % len(key)]) % 256
S[i], S[j] = S[j], S[i]
return SStage 2: Keystream generation and round-trip encryption
Keystream generation, sometimes called PRGA, runs a separate loop against that scheduled S. Each step advances two index pointers, swaps the two array entries they point to, and outputs the byte sitting at the position given by the sum of those two swapped entries.
def rc4_prga(S, n_bytes: int):
"""Pseudo-random generation algorithm: emit n_bytes of keystream from S."""
S = S[:] # PRGA mutates S further, work on a copy so KSA's S stays untouched
i = 0
j = 0
out = bytearray()
for _ in range(n_bytes):
i = (i + 1) % 256
j = (j + S[i]) % 256
S[i], S[j] = S[j], S[i]
out.append(S[(S[i] + S[j]) % 256])
return bytes(out)
def rc4_crypt(key: bytes, data: bytes) -> bytes:
S = rc4_ksa(key)
ks = rc4_prga(S, len(data))
return bytes(d ^ k for d, k in zip(data, ks))
key = b"summer-key-2026"
plaintext = b"MEET AT NOON"
ciphertext = rc4_crypt(key, plaintext)
recovered = rc4_crypt(key, ciphertext)key: b'summer-key-2026'
plaintext: b'MEET AT NOON'
ciphertext (hex): 78d281f7e02ab5485758d07c
decrypted: b'MEET AT NOON'
round trip ok: TrueNotice that rc4_crypt gets called with the exact same arguments to encrypt and to decrypt. That’s the “one function does both directions” property from the very first section, made concrete: there’s no separate decrypt function anywhere in this code.
Every operation RC4 performs reduces to two primitives: swap two array entries, and add two indices mod 256 to pick the next position. There’s no separate mixing or diffusion step layered on top the way a block cipher layers substitution and permutation rounds, the swapping itself is the entire mixing function. That’s also why a working RC4 implementation is famously this short, and why it ended up embedded into so many protocols and products before anyone took its output bias seriously.
flowchart TB
subgraph KSA["Key-Scheduling Algorithm (once)"]
Key[Secret key] --> KSAloop["256 iterations:<br/>swap S[i], S[j]"]
KSAloop --> S["S: key-dependent<br/>permutation of 0-255"]
end
subgraph PRGA["Pseudo-Random Generation (per byte)"]
S --> Advance["advance i, j<br/>swap S[i], S[j]"]
Advance --> Out["output S[(S[i]+S[j]) mod 256]"]
endWhy RC4 Is Actually Broken: Statistical Bias
A secure keystream byte should land on each of the 256 possible values with equal probability, 1/256 each. RC4’s doesn’t. Certain early bytes, most famously the second byte of the keystream, come out as specific values, notably zero, measurably more often than chance predicts.
Think of it like a biased coin that lands heads 51% of the time instead of 50%. Flip it 10 times and that bias is invisible, buried in noise. Flip it 10 million times and it’s unmissable. RC4’s bias works the same way: tiny per byte, but across millions of ciphertexts encrypting the same or related plaintext under different keys (the “broadcast” scenario, think a session cookie sent repeatedly, re-encrypted fresh each connection), an attacker can average out the noise and use the skew to recover plaintext bytes statistically, without ever touching the key. Both WEP, Wi-Fi’s original encryption scheme, and TLS trusted RC4 for over a decade before these biases were treated as disqualifying rather than academic curiosities.
To see the bias directly, here’s RC4’s second keystream byte tallied across 200,000 independently random keys:
import os
from collections import Counter
counts = [0] * 256
for _ in range(200_000):
key = os.urandom(16)
S = rc4_ksa(key)
ks = rc4_prga(S, 2)
counts[ks[1]] += 1
expected = 200_000 / 256RC4 second keystream byte, tallied over 200000 random keys
expected count per value if uniform: 781.2
byte value 0x00 observed count: 1556 (expected 781.2)
top 5 most frequent byte values: [(0, 1556), (164, 842), (183, 840), (9, 837), (205, 835)]
min count: 679 max count: 1556
Byte value 0 shows up almost exactly twice as often as a uniform distribution would predict. Every other value hovers close to the flat expected line. That’s not a subtle statistical artifact, it’s a structural property of the KSA/PRGA construction itself, and it’s why “looks random” and “is uniformly random” are treated as completely different bars in cryptography. RC4’s shuffled-array output looks fine on casual inspection. It fails formal randomness testing outright, and formal testing is the bar that actually matters.
Salsa20/ChaCha: Counter-Based Keystream from Add-Rotate-XOR
Salsa20, and its close relative ChaCha, take a completely different approach from either LFSRs or RC4’s byte swapping. They load a 512-bit state as a 4x4 grid of 32-bit words: fixed constant words, the 256-bit key, a 64-bit nonce, and a 64-bit block counter.
The core building block is the quarter-round function. It takes four of those sixteen words and mixes them through a sequence of steps, each one adds two words together, XORs the result into a third word, and rotates that third word’s bits by a fixed amount. Add, XOR, rotate: this pattern is called ARX, and repeating it is what gives the cipher both speed (these are all cheap CPU operations, no lookup tables or S-boxes) and nonlinearity (rotation combined with addition resists exactly the linear-algebra attacks that broke the LFSR above).
MASK32 = 0xFFFFFFFF
def rotl(x, n):
x &= MASK32
return ((x << n) | (x >> (32 - n))) & MASK32
def quarter_round(a, b, c, d):
"""Salsa20 quarter round on four 32-bit words."""
b ^= rotl((a + d) & MASK32, 7)
c ^= rotl((a + b) & MASK32, 9)
d ^= rotl((b + c) & MASK32, 13)
a ^= rotl((c + d) & MASK32, 18)
return a & MASK32, b & MASK32, c & MASK32, d & MASK32Salsa20 applies the quarter-round to all four columns of the grid, then to all four rows, and calls that pair a “double-round.” It repeats that 10 times, 20 rounds total, to scramble the grid. On its own, that 20-round scramble is just a reversible shuffle of the input words, anyone holding one output block could run it backward and recover the exact key/nonce/counter grid that produced it, which would hand over the key outright. What makes it safe is the last step: adding the pre-round grid back into the scrambled grid, word by word. That addition breaks reversibility. The public keystream block becomes a many-to-one function of the internal state, so no amount of algebra on the output alone gets you back to the key. Because the counter word is the only thing that changes between blocks, generating block N is a direct computation rather than a sequential replay, which is exactly what makes this design counter-based instead of stateful.
Measuring diffusion: the avalanche effect
The claim that ARX spreads a single input bit across the whole output fast is testable. Take two initial states that share the same nonce and counter but differ in a single flipped bit deep in the 256-bit key, run both through every individual round from round 1 to round 8, and after each round count how many of the 512 bits differ between the two states (their Hamming distance).
It’s the same idea as tracking a rumor spreading through a fully connected office floor, one conversation-round at a time. After round 1 almost nobody’s heard it. The count of “informed” bits should climb steeply and then flatten out near 256, half of 512, by round 8. The shape of that curve, not just the start and end points, is the evidence that mixing is fast rather than merely eventually complete.
COLUMNS = [(0, 4, 8, 12), (5, 9, 13, 1), (10, 14, 2, 6), (15, 3, 7, 11)]
ROWS = [(0, 1, 2, 3), (5, 6, 7, 4), (10, 11, 8, 9), (15, 12, 13, 14)]
def single_round(state, column_round: bool):
"""One Salsa20 round: quarter-round applied to all four columns
(column_round=True) or all four rows (column_round=False)."""
s = state[:]
groups = COLUMNS if column_round else ROWS
for a, b, c, d in groups:
s[a], s[b], s[c], s[d] = quarter_round(s[a], s[b], s[c], s[d])
return s
def hamming_distance(s1, s2):
return sum(bin(w1 ^ w2).count("1") for w1, w2 in zip(s1, s2))
key_a = [0x01020304, 0x05060708, 0x090a0b0c, 0x0d0e0f10,
0x11121314, 0x15161718, 0x191a1b1c, 0x1d1e1f20]
key_b = key_a[:]
key_b[6] ^= 0x00000001 # flip a single bit deep in the key
# build_state assembles constants + key + nonce + counter into the 16-word grid
state_a = build_state(key_a, nonce, counter)
state_b = build_state(key_b, nonce, counter)
sa, sb = state_a[:], state_b[:]
for r in range(1, 9):
column_round = (r % 2 == 1)
sa = single_round(sa, column_round)
sb = single_round(sb, column_round)
print(r, hamming_distance(sa, sb))initial state Hamming distance (single flipped key bit): 1 of 512 bits
round bits changed fraction of 512
1 7 1.4%
2 76 14.8%
3 198 38.7%
4 255 49.8%
5 253 49.4%
6 247 48.2%
7 252 49.2%
8 263 51.4%
One flipped bit turns into 7 changed bits after round 1, climbs past 250 by round 4, and then hovers right around the 256-bit “half of everything looks different” line for the rest of the rounds shown. That’s the avalanche effect working as designed: it doesn’t take anywhere near the full 20 rounds for a single bit to saturate the whole state, the real 20-round count is a large security margin on top of a mixing process that’s already thorough within a handful of rounds.
Nonce Reuse: Why It Breaks Everything
Everything above, whether it’s RC4’s byte swapping or ChaCha’s ARX rounds, shares one absolute requirement: never use the same (key, nonce) pair twice. Here’s exactly why, algebraically, not as a vague warning.
If the same key and nonce are ever reused, the cipher produces the identical keystream both times, since the keystream is entirely determined by (key, nonce), nothing else feeds into it. Say an attacker collects two ciphertexts made that way: C1 = P1 XOR KS and C2 = P2 XOR KS. XOR those two ciphertexts together and the keystream cancels out completely:
C1 XOR C2 = (P1 XOR KS) XOR (P2 XOR KS) = P1 XOR P2
The attacker now holds the XOR of two plaintexts, with zero key material needed to get there. And P1 XOR P2 is far from random-looking to anyone who can guess even a fragment of one plaintext. A predictable header, a common word, file-format magic bytes, any such “crib” XORed against the matching stretch of P1 XOR P2 immediately reveals the corresponding stretch of the other plaintext. That recovered fragment can then be extended outward, peeling back the rest of both messages piece by piece.
flowchart TB
K["same key + same nonce<br/>(the mistake)"] --> KS["identical keystream KS<br/>generated twice"]
P1["Plaintext 1"] --> X1((XOR)) --> C1["Ciphertext 1"]
P2["Plaintext 2"] --> X2((XOR)) --> C2["Ciphertext 2"]
KS --> X1
KS --> X2
C1 --> X3((XOR))
C2 --> X3
X3 --> Result["C1 XOR C2 = P1 XOR P2<br/>no key needed"]This is a total break. No computational attack on the cipher’s internals is required, and it applies equally whether the underlying cipher is 1990s RC4 or the strongest counter-based cipher available today. That’s precisely why a nonce is treated as a hard uniqueness requirement in every serious spec, not a best-effort suggestion.
Stage 1: Constructing the mistake
Imagine a note-syncing app that derives its nonce from a per-session message counter, a reasonable-sounding design, except the counter resets to 0 every time the app restarts. Two different app restarts, two different plaintexts, same key, and the counter starts back at 0 both times:
def keystream(key: bytes, nonce: bytes, length: int) -> bytes:
S = rc4_ksa(key + nonce) # bind nonce into the keying material
return rc4_prga(S, length)
key = b"device-shared-sync-key-2026!!"
session_1_note = b"STATUS: idle, battery 91%, last sync ok"
session_2_note = b"STATUS: user typed the passphrase hunter2 into notes"
nonce = (0).to_bytes(8, "big") # counter reset to 0 on both app restarts
ks = keystream(key, nonce, max(len(session_1_note), len(session_2_note)))
ct1 = xor_bytes(session_1_note, ks[:len(session_1_note)])
ct2 = xor_bytes(session_2_note, ks[:len(session_2_note)])app restart #1, counter/nonce reset to 0:
plaintext: b'STATUS: idle, battery 91%, last sync ok'
ciphertext: 45e5b37c7f76d74276e4f5e843eca144f9fcb7ac57331157a85248f692803d06715fe939cf5cf3
app restart #2, counter/nonce reset to 0 again:
plaintext: b'STATUS: user typed the passphrase hunter2 into notes'
ciphertext: 45e5b37c7f76d7426af3fcff4fb8ba55e8ecf2aa46760816ec0d1bea9b8128556706ef2f8147fdbee4eea63452982852eecedc2fLook at the first several bytes of both ciphertexts: 45e5b37c7f76d742 opens both of them, identically. That’s the reuse leaking through before any XOR-cancellation math even happens, both ciphertexts were built from the same keystream prefix, so their common structure shows straight through.
Stage 2: XORing the ciphertexts and pulling plaintext out with a crib
An app developer trusted a restart-safe counter that wasn’t. Now the attacker XORs the two captured ciphertexts and applies a guessed crib, the plausible assumption that a status message starts with “STATUS: ”:
n = min(len(ct1), len(ct2))
xor_ct = xor_bytes(ct1[:n], ct2[:n])
crib = b"STATUS: "
recovered_prefix = xor_bytes(xor_ct[:len(crib)], crib)
# extend using the full known message 1 as an ever-growing crib
full_p2 = xor_bytes(xor_ct[:len(session_1_note)], session_1_note[:len(xor_ct)])attacker has both ciphertexts, no key: C1 XOR C2 (hex) = 00000000000000001c1709170c541b111110450611451941445f531c09011553165906164e1b0e
attacker guesses message 1 starts with crib b'STATUS: '
XORing crib against C1 XOR C2 recovers start of message 2: b'STATUS: '
full recovery using entire known message 1 as the crib:
recovered message 2: b'STATUS: user typed the passphrase hunte'
actual message 2: b'STATUS: user typed the passphrase hunter2 into notes'
match: TrueNotice the first eight bytes of C1 XOR C2 are literally 00000000000000001c...: wherever both plaintexts share the same bytes (“STATUS: ”), XORing them together cancels to zero, another visible fingerprint of reuse before any cleverness is applied. Once the attacker has all of message 1 as a known plaintext (which, in a real attack, might just be a previous status update they already saw in cleartext elsewhere), XORing it against P1 XOR P2 hands back message 2 byte for byte, including the passphrase sitting in it. Zero cryptanalysis of RC4 itself was needed. The break came entirely from a counter that silently reset.
Choosing and Deploying Stream Ciphers Safely Today
RC4 should never appear in a new design. Its statistical biases, the kind measured directly above, are proven and practically exploitable, which is exactly why TLS, every major browser, and every major crypto library deprecated and eventually removed it entirely.
ChaCha20, Salsa20’s more widely standardized successor, paired with the Poly1305 authenticator as ChaCha20-Poly1305, is the modern default for software-oriented stream encryption. It’s fast without needing special hardware support, it’s held up under decades of sustained cryptanalysis attention, and its counter-based design allows safe parallel and random-access decryption, the property demonstrated back in the stateful-vs-counter-based section.
The nonce is the piece that most often gets mishandled in practice, not the cipher itself. Generate it uniquely per (key, message) either through a monotonically incremented counter that’s never allowed to reset or repeat, or through a nonce wide enough (96 bits or more) that random generation makes a collision negligible. Never derive it from something that can silently reset, a counter tied to process restarts or connection re-establishment, exactly the mistake the note-syncing app made above.
There’s a separate design category worth knowing about for the cases where nonce uniqueness genuinely can’t be guaranteed operationally: misuse-resistant encryption. Think stateless, horizontally-scaled servers that can’t share a live counter across instances. These constructions derive part of the keystream from the plaintext itself, rather than purely from key and nonce, so an accidentally repeated nonce no longer causes the full XOR-cancellation break demonstrated above. The cost is that data has to be processed in two passes instead of one, roughly doubling the work. SIV is the standard example of this family, and it exists specifically because “just don’t reuse the nonce” is, in practice, a rule that real systems sometimes can’t fully guarantee on their own.
Key Takeaways
- A stream cipher turns (key, nonce) into a keystream and encrypts with
ciphertext = plaintext XOR keystream; the same operation decrypts, since XOR is its own inverse. - Stateful designs (RC4) must be replayed sequentially from the start to reach any given byte; counter-based designs (Salsa20, ChaCha, AES-CTR) compute any block directly and parallelize trivially.
- Plain LFSRs fail two separate ways: most tap choices don’t even reach the theoretical maximal period, and even a maximal-period LFSR is fully predictable from a handful of observed output bits via Berlekamp-Massey, because its output is linear in the seed.
- RC4 is broken by measurable statistical bias in its early keystream bytes (the second byte lands on 0x00 roughly twice as often as chance predicts), exploitable at scale even without touching the key.
- Salsa20/ChaCha get both speed and nonlinearity from ARX (add-rotate-XOR) rounds, and stay irreversible because the pre-round state is added back into the scrambled state at the end.
- Reusing a (key, nonce) pair is a total break regardless of which cipher is used: XORing two ciphertexts made under the same keystream cancels it out entirely, leaving
P1 XOR P2recoverable with zero key material and, given any crib, the plaintexts themselves.