Stream Ciphers & ChaCha20

A stream cipher expands a key and nonce into a long pseudorandom keystream, which is XORed with the plaintext. That makes it a one-time pad whose pad is generated rather than shared — inheriting the OTP's elegance (no padding, no block alignment, byte-granular, seekable) and its single unforgiving rule: never reuse a (key, nonce) pair.

$$C_i = P_i \oplus \text{KS}(K, N)_i$$

The line between stream and block ciphers is thinner than the taxonomy suggests: AES in CTR mode is a stream cipher. What distinguishes a dedicated design like ChaCha20 is that it was built for this job from the start, with no invertibility requirement on the core function.

What killed RC4 #

RC4 (Rivest, 1987) was the workhorse for two decades — SSL/TLS, WEP, WPA-TKIP — because it was tiny and fast. It is now prohibited in TLS (RFC 7465), and the reason is instructive: it wasn't one break but an accumulation of biases.

RC4's keystream is not uniform. The second byte is 0 with probability $2/256$ instead of $1/256$; the Fluhrer–Mantin–Shamir related-key weaknesses broke WEP outright; and AlFardan et al. (2013) showed the biases persist far enough into the stream to recover HTTP cookies from roughly $2^{26}$ TLS sessions of the same plaintext.

WEP compounded it with a 24-bit IV — guaranteed keystream reuse within hours on a busy access point — a design error independent of RC4's own flaws.

ChaCha20 #

Bernstein's Salsa20 (2005) and its refinement ChaCha20 (2008) are ARX designs: the only operations are Add (32-bit), Rotate, and Xor. No S-boxes, no lookup tables, no data-dependent branches.

The state is 16 words (512 bits) in a 4×4 matrix:

The constants are the ASCII of "expand 32-byte k" — a nothing-up-my-sleeve value. The core is a quarter-round applied to four words:

a += b;  d ^= a;  d <<<= 16
c += d;  b ^= c;  b <<<=  12
a += b;  d ^= a;  d <<<=  8
c += d;  b ^= c;  b <<<=  7

Twenty rounds alternate column rounds and diagonal rounds (four quarter-rounds each, all four independent — hence natural SIMD parallelism). Finally the original state is added to the permuted state, which makes the whole thing non-invertible and yields 64 bytes of keystream per block. The 32-bit block counter permits $2^{32}$ blocks = 256 GB per (key, nonce), and seeking to any offset is free — just set the counter.

RFC 8439 fixes the IETF variant: 96-bit nonce, 32-bit counter. That nonce is large enough for random generation to be safe in most protocols, unlike the original 64-bit Salsa20 nonce.

ChaCha20-Poly1305 #

The cipher alone provides no integrity, and XOR keystreams are perfectly malleable, so it is always deployed as an AEAD paired with Poly1305 — a one-time MAC evaluating a polynomial modulo the prime $2^{130} - 5$.

The construction detail that matters: the Poly1305 key is derived per message from the first 32 bytes of the ChaCha20 keystream at counter 0, and the actual encryption starts at counter 1. Poly1305 is a one-time MAC — reusing its key across messages leaks the key through linear algebra, exactly as with GHASH — so deriving it fresh from the nonce-dependent keystream is what makes the composition safe.

Where each wins #

TLS 1.3 standardizes both and clients pick by hardware: desktop and server browsers on modern x86 negotiate AES-GCM, while mobile and embedded clients — and anything on older ARM without crypto extensions — prefer ChaCha20-Poly1305. Google deployed it in Chrome on Android precisely for this reason. It is also the default in WireGuard, and available in OpenSSH and libsodium.