Stream ciphers: RC4, ChaCha20, and the rule you must never break

Structure: a pseudorandom generator and an XOR

A stream cipher does not transform the plaintext at all. It feeds the key into a pseudorandom bit generator, which emits a keystream — a sequence of bits that looks random but is completely determined by the key — and XORs that keystream with the plaintext, typically one byte at a time. Decryption is the identical operation: regenerate the same keystream from the same key and XOR again, because $x\oplus k\oplus k=x$.

With a well-designed generator, a stream cipher is as secure as a block cipher of comparable key length. What it buys you is speed and code size: RC4 needs only eight to sixteen machine operations per output byte, and the whole algorithm is a few dozen lines. What a block cipher buys you in exchange is the property that matters most in practice — its key can be safely reused across messages.

The rule, and the worked example that proves it

A keystream must never be used twice. Here is why, in four lines of algebra you can reproduce under exam conditions. Suppose two plaintexts are encrypted under the same keystream $S$:

$$C_1=P_1\oplus S,C_2=P_2\oplus S$$

An eavesdropper who has both ciphertexts computes

$$C_1\oplus C_2=(P_1\oplus S)\oplus (P_2\oplus S)=P_1\oplus P_2$$

The keystream has cancelled out. The key has vanished from the equation entirely, and no amount of key length helps. This is the two-time pad.

Worked example. Take the keystream bytes 9a 3f 61 c8 0d 52 b7 e4 and two eight-byte messages, ATTACK!! and RETREAT?:

C1 = db6b35894e1996c5
C2 = c87a359a4813e3db
C1 XOR C2 = 13110013060a751e
P1 XOR P2 = 13110013060a751e     <- identical

An attacker who guesses, or already knows, that the first message is ATTACK!! recovers the second for free: $(C_1\oplus C_2)\oplus P_1=P_2$ = RETREAT?. Nothing was broken. The cipher did exactly what it was told.

This is not a theoretical worry. It is the mechanism behind the WEP break you will meet in Module 15: WEP's initialisation vector is only 24 bits wide, so on a busy link the IV wraps and keystreams repeat within hours — and every repeat hands an attacker another pair of ciphertexts encrypted under the same keystream.

RC4

RC4 was designed by Ron Rivest in 1987 for RSA Security. It has a variable key size, is byte-oriented, and is built on a random permutation of the 256 possible byte values. It comes in two halves:

• The key-scheduling algorithm (KSA) initialises a 256-byte array $S$ to the identity permutation $0,1,\dots ,255$, then walks it once, swapping entries under the control of the key. The key is repeated cyclically to cover all 256 steps.
• The pseudorandom generation algorithm (PRGA) then walks $S$ indefinitely, swapping two entries at each step and emitting a third as the next keystream byte.

It was kept as a trade secret until the algorithm was posted anonymously in September 1994, and it went on to be used in SSL/TLS, in WEP and in WPA. RFC 7465 (2015) prohibits RC4 in TLS outright.

One precision is worth more than all the rest, because it is the lesson and not just a fact. The 2001 Fluhrer–Mantin–Shamir result is routinely described as "RC4 was broken". It broke WEP: the flaw was in the way WEP constructed the key input it handed to RC4, not in RC4's own output function. A cryptographic primitive and the protocol that uses it fail separately, and telling the two apart is most of what security engineering is.

ChaCha20

ChaCha20 is Daniel Bernstein's 2008 stream cipher, and it is what replaced RC4 in practice. Its state is sixteen 32-bit words — 512 bits — laid out as a 128-bit constant, a 256-bit key, a 32-bit block counter and a 96-bit nonce. It runs 20 rounds, arranged as 10 double rounds: odd rounds operate on the columns of the 4×4 state, even rounds on the diagonals. Each quarter-round is add, XOR and rotate, with rotation constants 16, 12, 8 and 7.

Two design points earn marks. First, the final state is added to the initial state before being output, and that addition is what makes the transformation non-invertible — without it the whole state, key included, could be run backwards from the keystream. Second, ChaCha20 uses only addition, rotation and XOR (an "ARX" design), with no table lookups at all, so it runs in constant time in software and avoids the cache-timing attacks that table-driven ciphers are exposed to. Speed is the advertised benefit; constant time is the security one. It is standardised in RFC 8439 and paired with the Poly1305 authenticator for authenticated encryption.