Stream Ciphers

Why stream ciphers matter

The one-time pad is the only cipher with a proof of perfect secrecy: XOR your message with a truly random key as long as the message, use that key exactly once, and the ciphertext leaks nothing. The catch is fatal in practice — you need to pre-share as many secret key bits as you will ever encrypt, and you must never reuse a single bit. Stream ciphers are the engineering compromise: keep the beautiful XOR structure of the pad, but generate the pad on the fly from a short (128- or 256-bit) key using a cryptographically secure pseudorandom generator. The pad is no longer information-theoretically random, only computationally unpredictable, which is enough against any real-world adversary.

That structure buys three things that make stream ciphers ubiquitous. They add zero length overhead — a 1000-byte message becomes a 1000-byte ciphertext, no block-padding, which matters for small packets and low-latency streaming. They are fast — ChaCha20 encrypts at multiple gigabytes per second in pure software and beats AES on any CPU without dedicated AES-NI instructions (most phones a decade ago, many embedded chips today). And they naturally fit streaming workloads where data arrives byte by byte and you cannot buffer a whole block. That is why ChaCha20-Poly1305 sits inside TLS 1.3, SSH, WireGuard, and the QUIC transport under HTTP/3.

How a stream cipher works, step by step

Every synchronous stream cipher has the same skeleton:

• Seed the state. A key-setup function absorbs the secret key K and a public nonce (number-used-once) N into an internal state. The nonce is what lets you safely reuse one key across many messages.
• Generate keystream. A next-state function repeatedly updates the state and emits a stream of pseudorandom bytes Z = z₀, z₁, z₂, …. This step never looks at the plaintext.
• Combine. Each ciphertext unit is cᵢ = pᵢ ⊕ zᵢ. Because (p ⊕ z) ⊕ z = p, the receiver runs the identical generator with the same K and N, produces the same Z, and XORs it back out.

The security bet is entirely on the keystream generator: if Z is indistinguishable from random to a computationally bounded attacker, the ciphertext is too. There are two classic ways to build the generator.

LFSR-based. A Linear-Feedback Shift Register produces a long pseudorandom bit sequence by shifting a register and feeding back the XOR of tapped bits, chosen by a primitive polynomial so the period is maximal (2ⁿ − 1 for an n-bit register). LFSRs are trivial in hardware — one clock cycle per bit — but a bare LFSR is linear and therefore fatally weak: the Berlekamp–Massey algorithm recovers the entire register from just 2n output bits in O(n²) time. Real designs (A5/1 in GSM, E0 in Bluetooth) combine several LFSRs with nonlinear clocking or filtering to hide the linearity — and several of those designs were still broken.

PRF-in-counter-mode. Modern designs don't chain state at all. ChaCha20 defines a keyed pseudorandom function F(K, N, counter) that maps a 32-bit block counter to a fresh 64-byte keystream block. To encrypt, you evaluate F at counter 0, 1, 2, … and concatenate the outputs. This is seekable (you can jump to any offset by computing the right counter) and parallelizable (every block is independent), unlike an LFSR whose state you must roll forward one step at a time.

Synchronous vs self-synchronizing

Stream ciphers split into two families by how the keystream is fed:

• Synchronous. The keystream is a function of key and nonce only — it ignores the plaintext and ciphertext entirely. Sender and receiver must generate exactly the same sequence in lockstep, so a single inserted or dropped bit desynchronizes everything after it. The upside: a flipped ciphertext bit flips exactly one plaintext bit — no error propagation. RC4, ChaCha20, Salsa20, and AES-CTR are all synchronous.
• Self-synchronizing (asynchronous). Each keystream bit is a function of the previous N ciphertext bits. After any insertion, deletion, or corruption, the register refills with correct ciphertext within N bits and the receiver re-syncs automatically. The cost: one bad ciphertext bit corrupts N plaintext bits (limited error propagation). CFB mode of a block cipher is the canonical example.

The nonce-reuse catastrophe

Here is the single most important operational rule, and the one most often broken in the field. Suppose you encrypt two messages under the same key and the same nonce. The generator is deterministic, so it produces the identical keystream K both times:

C1 = P1 ⊕ K
C2 = P2 ⊕ K

C1 ⊕ C2 = (P1 ⊕ K) ⊕ (P2 ⊕ K) = P1 ⊕ P2

The keystream cancels completely. The attacker, who sees only C1 and C2, now holds P1 ⊕ P2 — the XOR of two real plaintexts — with no key involved at all. From there, English text redundancy, known headers ("crib-dragging"), or a single guessed word peels both messages apart. This is exactly how the US Venona project read reused Soviet one-time pads, and how the WEP Wi-Fi protocol collapsed: its 24-bit IV wrapped around after only ~16.7 million frames, guaranteeing nonce reuse on any busy network. The lesson: a nonce must be unique for every message under a given key. With a 96-bit random nonce (as in ChaCha20-Poly1305) the birthday bound keeps collision probability negligible up to roughly 2⁴⁸ messages; if you cannot guarantee uniqueness, use a counter, or reach for a nonce-misuse-resistant AEAD like AES-GCM-SIV.

Stream cipher vs block cipher

	Stream cipher	Block cipher
Unit of operation	Bit or byte at a time	Fixed block (e.g. 128 bits)
Core primitive	Keystream generator + XOR	Keyed permutation (needs a mode)
Length overhead	None	Padding to block multiple
Random access	Seekable if PRF/CTR-based; not if LFSR-chained	Natural per-block (e.g. XTS for disks)
Parallelizable encryption	Yes (CTR/PRF); no (RC4)	Depends on mode (CTR yes, CBC no)
Error propagation	None (synchronous)	Mode-dependent (CBC propagates one block)
Software speed w/o AES-NI	Very fast (ChaCha20)	Slower (bitsliced AES)
Examples	RC4, ChaCha20, Salsa20, A5/1	AES, DES, Blowfish
Relationship	A block cipher in CTR mode is a stream cipher — the boundary is a spectrum, not a wall.

Implementation: ChaCha20 keystream in Python

The heart of ChaCha20 is the quarter-round: four add–rotate–XOR (ARX) operations, applied twenty times (ten "double rounds") over a 4×4 grid of 32-bit words. The state is constants ‖ key ‖ counter ‖ nonce; each counter value yields one independent 64-byte keystream block, which you XOR with the plaintext.

import struct

MASK = 0xffffffff
def rotl(v, c): return ((v << c) | (v >> (32 - c))) & MASK

def quarter_round(s, a, b, c, d):
    s[a] = (s[a] + s[b]) & MASK; s[d] = rotl(s[d] ^ s[a], 16)
    s[c] = (s[c] + s[d]) & MASK; s[b] = rotl(s[b] ^ s[c], 12)
    s[a] = (s[a] + s[b]) & MASK; s[d] = rotl(s[d] ^ s[a], 8)
    s[c] = (s[c] + s[d]) & MASK; s[b] = rotl(s[b] ^ s[c], 7)

def chacha20_block(key, counter, nonce):
    # 4-word constant "expand 32-byte k", 8-word key, 1-word counter, 3-word nonce
    const = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
    state = const + list(struct.unpack('<8I', key)) \
                  + [counter] + list(struct.unpack('<3I', nonce))
    working = state[:]
    for _ in range(10):                       # 10 double-rounds = 20 rounds
        quarter_round(working, 0, 4,  8, 12)  # columns
        quarter_round(working, 1, 5,  9, 13)
        quarter_round(working, 2, 6, 10, 14)
        quarter_round(working, 3, 7, 11, 15)
        quarter_round(working, 0, 5, 10, 15)  # diagonals
        quarter_round(working, 1, 6, 11, 12)
        quarter_round(working, 2, 7,  8, 13)
        quarter_round(working, 3, 4,  9, 14)
    out = [(working[i] + state[i]) & MASK for i in range(16)]  # feed-forward
    return struct.pack('<16I', *out)          # 64-byte keystream block

def chacha20_xor(key, nonce, data, counter=1):
    out = bytearray()
    for i in range(0, len(data), 64):
        ks = chacha20_block(key, counter, nonce)   # keystream block
        counter += 1                               # next 64-byte slice
        for j, b in enumerate(data[i:i + 64]):
            out.append(b ^ ks[j])                  # ciphertext = plaintext XOR keystream
    return bytes(out)

# Encrypt and decrypt are the SAME call — XOR is its own inverse.
key   = bytes(range(32))          # 256-bit key
nonce = bytes(range(12))          # 96-bit nonce — MUST be unique per message
ct = chacha20_xor(key, nonce, b"attack at dawn")
pt = chacha20_xor(key, nonce, ct)
assert pt == b"attack at dawn"

Notice there is no separate decrypt function: encryption and decryption are one code path because the whole cipher is "generate keystream, XOR it in." Notice too the feed-forward at the end (working[i] + state[i]) — adding the original state back is what makes the permutation non-invertible from output alone, so an attacker cannot run it backwards. This example is for teaching only: a real deployment must pair it with Poly1305 as ChaCha20-Poly1305 and use constant-time arithmetic.

Common misconceptions and pitfalls

• "Encryption means it's tamper-proof." No. A raw stream cipher is malleable: flip bit i of the ciphertext and bit i of the recovered plaintext flips, no key needed. An attacker can change "transfer $100" to "transfer $900" without decrypting anything. Always add a MAC — use an AEAD.
• Reusing a nonce "just this once." There is no "just once." One reuse leaks P1 ⊕ P2 forever; retransmits, VM snapshots that rewind an RNG, and 24-bit IVs are the usual culprits.
• Trusting a raw LFSR. Linearity is death — Berlekamp–Massey clones the register from 2n bits. Never use a bare LFSR for security; it is a randomness primitive, not a cipher.
• Still using RC4. Its keystream bytes are biased (the second byte is doubly likely to be zero), enabling plaintext recovery. Prohibited in TLS since RFC 7465 (2015).
• Confusing a nonce with a key. The nonce is public and needs only to be unique, not secret; the key is secret and reusable. Swapping their roles breaks the whole model.