Stream Cipher

Stream Cipher denotes a class of symmetric-key cryptographic primitives in which individual plaintext digits—typically single bits over the Galois field GF(2) or 8-bit bytes—are combined sequentially with a time-varying keystream generated from a short secret key K and a public initialization vector or nonce (IV). Whereas block ciphers partition messages into fixed-width blocks (such as 128 bits in the Advanced Encryption Standard) and apply an invertible keyed permutation to each block, stream ciphers maintain an evolving internal state σ_i that emits keystream symbols k_i independently of block boundaries, yielding zero ciphertext expansion and low per-byte latency.

Vernam's Cipher, One-Time Pads, and Shannon Secrecy

Originating in Gilbert S. Vernam's 1917 Baudot teleprinter tape cipher and contrasting with mechanical polyalphabetic devices such as the Enigma Machine, a synchronous binary stream cipher uses a deterministic generator G : {0, 1}^λ × {0, 1}^ν → {0, 1}^L to expand a λ-bit secret key K and a ν-bit nonce IV into keystream k₁, k₂, …, k_L. Encryption and decryption apply involutory bitwise exclusive-OR (⊕, addition modulo 2):

• Encryption: c_i = m_i ⊕ k_i
• Decryption: c_i ⊕ k_i = (m_i ⊕ k_i) ⊕ k_i = m_i ⊕ (k_i ⊕ k_i) = m_i

In 1917, AT&T engineer Gilbert S. Vernam patented this binary modulo-2 combination for Baudot-coded punched paper teleprinter tapes, and U.S. Army Signal Corps officer Joseph Mauborgne recognized that replacing periodic tape loops with truly non-repeating random keys thwarted polyalphabetic cryptanalysis. In his landmark 1949 monograph Communication Theory of Secrecy Systems, Claude E. Shannon proved that the one-time pad (OTP) achieves unconditional perfect secrecy: when k₁, …, k_L are independent, identically distributed uniform Bernoulli(1/2) bits never reused across messages, the posterior distribution of plaintext M given ciphertext C equals the prior distribution, P(M = m | C = c) = P(M = m), so mutual information vanishes (I(M; C) = 0) and ciphertext reveals zero Shannon Entropy about the message regardless of adversary compute resources.

Computational Indistinguishability, Two-Time Pads, and Malleability

Shannon simultaneously proved an optimality barrier: unconditional secrecy requires key length |K| ≥ |M|. Practical stream ciphers circumvent this key-distribution bottleneck under Computational Complexity Theory by replacing true randomness with a cryptographically secure pseudorandom generator (CSPRNG) whose output is computationally indistinguishable from uniform coin flips to any polynomial-time distinguisher.

Two operational hazards govern all additive stream ciphers:

1. Keystream Reuse (Two-Time Pad Failure): If an identical (K, IV) pair encrypts two plaintexts m⁽¹⁾ and m⁽²⁾, bitwise XOR of the ciphertexts cancels the keystream: c⁽¹⁾ ⊕ c⁽²⁾ = m⁽¹⁾ ⊕ m⁽²⁾. Because natural language and protocol headers contain 3–5 bits of redundancy per byte, cryptanalysts recover both messages via crib dragging (exploited by the VENONA project against reused diplomatic pads and against IEEE 802.11 WEP's 24-bit IVs).
2. Bit-Flipping Malleability: Flipping ciphertext bit c_i′ = c_i ⊕ Δi flips decrypted bit m_i′ = m_i ⊕ Δi at that bit offset without disturbing surrounding bytes. Modern protocols therefore pair stream ciphers with a message authentication code in Authenticated Encryption with Associated Data (AEAD) constructions such as ChaCha20-Poly1305 or AES-GCM.

Linear Feedback Shift Registers and the Berlekamp–Massey Attack

Hardware telecommunications historically favored Linear Feedback Shift Registers (LFSRs) for their compact gate footprints. An L-stage LFSR updates state (s_t+L−1, …, s_t) over GF(2):

s_t+L = c₁ s_t+L−1 ⊕ c₂ s_t+L−2 ⊕ … ⊕ c_L s_t

When the feedback polynomial P(x) = 1 + c₁x + … + c_Lx^L is primitive over GF(2)[x], every non-zero initial state traverses all 2^L − 1 non-zero states before repeating. Despite maximal period, a bare LFSR is insecure: observing 2L consecutive keystream bits via known plaintext allows the Berlekamp–Massey algorithm (1969) to reconstruct both P(x) and the initial state in O(L²) bit operations. Hardware stream ciphers therefore add Boolean nonlinearity—combining LFSRs via nonlinear filters or irregular clocking (as in GSM A5/1, later broken by rainbow-table and SAT attacks) or coupling Nonlinear Feedback Shift Registers (NFSRs) in Trivium (288-bit state) and Grain-128AEAD.

Decline of RC4 and Rise of ChaCha20 and AES-CTR

Designed by Ronald Rivest in 1987 for fast software execution on 8-bit and 32-bit microprocessors, RC4 maintained a 256-byte dynamic permutation array S[0…255] scrambled by a Key-Scheduling Algorithm (KSA) and updated via two index pointers (i, j) per output byte. Over two decades of cryptanalysis exposed structural statistical defects: Fluhrer, Mantin, and Shamir (2001) proved that prepending unhashed initialization vectors to secret keys in WEP leaked key bytes directly through early KSA steps, while Mantin, Biham, and AlFardan et al. (2013) demonstrated persistent non-uniform biases in the second byte (P(k₂ = 0) ≈ 2/256 instead of 1/256) and multi-million-connection TLS session recovery, prompting the IETF to prohibit RC4 in TLS under RFC 7465 (2015).

Modern software protocols—where session keys are negotiated via Diffie–Hellman Key Exchange and Elliptic-Curve Cryptography—converged on two designs resistant to both algebraic cryptanalysis and cache-timing Side-Channel Attack leakage:

• ChaCha20 (ARX Counter-Based Stream Cipher): Introduced by Daniel J. Bernstein in 2008 as a refinement of eSTREAM winner Salsa20, ChaCha20 initializes a 512-bit (4 × 4 thirty-two-bit word) matrix from four 32-bit ASCII constants ("expand 32-byte k"), eight words of a 256-bit key, a 32-bit block counter b, and three words of a 96-bit nonce. Twenty alternating column and diagonal quarter-round passes execute constant-time Add–Rotate–XOR (ARX) word updates (a ← a ⊞ b; d ← (d ⊕ a) ⋘ 16; …), after which the scrambled matrix is added wordwise to the initial matrix to emit a seekable 64-byte keystream block.
• Counter Mode (AES-CTR): Evaluates a block cipher E_K(IV ∥ b) over sequential counter blocks b = 0, 1, 2, …, converting AES into a parallelizable synchronous stream cipher accelerated by dedicated AES-NI processor silicon.

What distinguishes a synchronous stream cipher from a self-synchronizing stream cipher?

In a synchronous stream cipher (ChaCha20 or AES-CTR), internal state advances independently of ciphertext; a flipped wire bit alters only that decrypted bit, whereas a dropped bit desynchronizes subsequent output until packet framing resets the counter. In a self-synchronizing stream cipher (such as Cipher Feedback mode, CFB), keystream generation depends on the preceding n ciphertext bits, restoring synchronization automatically after n intact bits following a burst loss while spreading a single-bit error across n decrypted bits.

Why does ChaCha20 add the initial 512-bit matrix to the permuted matrix after 20 rounds?

The 20-round ARX core π is an unkeyed public bijection on 512-bit blocks. Without the feed-forward sum X_out = X_init ⊞ π(X_init), an attacker obtaining one 64-byte keystream block from known plaintext could invert π⁻¹(X_out) backward in microseconds and read the 256-bit key directly from words 4 through 11 of X_init.

1. Shannon, C. E. (1949). Communication theory of secrecy systems. Bell System Technical Journal, 28(4), 656–715. https://doi.org/10.1002/j.1538-7305.1949.tb00928.x
2. Massey, J. L. (1969). Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, 15(1), 122–127. https://doi.org/10.1109/TIT.1969.1054260
3. Fluhrer, S., Mantin, I., & Shamir, A. (2001). Weaknesses in the key scheduling algorithm of RC4. Selected Areas in Cryptography (SAC 2001), Lecture Notes in Computer Science, 2259, 1–24. https://doi.org/10.1007/3-540-45537-X_1
4. De Cannière, C., & Preneel, B. (2008). Trivium. In New Stream Cipher Designs: The eSTREAM Finalists, Lecture Notes in Computer Science, 4986, 244–266. https://doi.org/10.1007/978-3-540-68351-3_18
5. Nir, Y., & Langley, A. (2018). ChaCha20 and Poly1305 for IETF Protocols (RFC 8439). Internet Engineering Task Force. https://doi.org/10.17487/RFC8439