Stream ciphers

The one-time pad is perfectly secret, and almost useless: its key has to be as long as everything it will ever encrypt. A stream cipher keeps the pad’s simple idea (XOR the message with a stream of key bits) but makes the stream from a short key, of 16 or 32 bytes, that can be shared once and used for years. The stream can’t be truly random any more. It only has to look random to anyone without the key, and the Randomness page showed how badly that can go: a linear register’s stream gave its whole future away from 8 known characters. This page builds two real stream ciphers, one that fell and one in use today.

1 · A key, stretched

A stream cipher is a generator: given a key, it produces as many bytes of keystream as are needed. Encrypting is XORing the message with the keystream; decrypting is XORing again with the same keystream, exactly as with the pad.

One rule carries over from the pad, in a new form. Using the same keystream twice gives away both messages, so a key can’t simply be used again. Instead, each message also gets a nonce (“number used once”): a value that needn’t be secret but must never repeat under the same key. The generator mixes it in with the key, so every nonce gives a completely different keystream.

A 32-byte secret key and a nonce, stretched into a keystream as long as the message (by ChaCha20, which section 4 opens up). The ciphertext is the message XORed with it. Change the nonce by one: the keystream changes entirely. Make the message longer: the key stays 32 bytes.

The nonce can be sent openly alongside the ciphertext, or simply be a counter both sides keep: message 1, 2, 3. All the security rests on the key, and on the generator.

2 · RC4: a shuffled deck

RC4 was designed by Ron Rivest in 1987. It was a trade secret until its code was posted anonymously to the internet in 1994, and for twenty years after that it was the most widely used stream cipher there was: in Wi-Fi’s first encryption, and in a large share of secure web connections. It’s also tiny, which makes it a good first cipher to take apart.

RC4 keeps a table of the numbers 0 to 255, in some order, like a shuffled deck of cards. It works in two stages:

Shuffling with the key. The table starts in order. A pointer i walks through it from start to end; at each step another pointer j moves on by the card at i plus the next byte of the key, and the cards at i and j swap. After 256 steps the deck is shuffled in a way that depends on every byte of the key.
Giving output. Now i steps along one place at a time, round and round, and j moves on by the card at i. The cards at i and j swap, their values are added, and the card at that position is the next byte of keystream. The deck keeps shuffling as it goes.

All arithmetic wraps round at the table’s size. With 256 cards that’s too much to follow by eye, but the algorithm works for a deck of any size, so here it is with 16:

RC4 on a table of 16 instead of 256, with a key of a few numbers. Step through the shuffle (16 steps, one swap each), then the output: each step names i and j, the two cards that swap (orange), and the card read out (blue ring). Every step is a swap, so the table is always some order of 0 to 15.

The real cipher is the same, with 256 cards and bytes for the key:

Test vectors:

RC4 with its full table of 256. The buttons load the three test vectors that implementations are checked against: the key “Key” turns “Plaintext” into BB F3 16 E8 D9 40 AF 0A D3. This code gives all three exactly (checked in the tests).

3 · Where RC4 leaks

The output looks random at a glance, but it isn’t quite. In 2001 Itsik Mantin and Adi Shamir proved that RC4’s second byte of output is 0 twice as often as it should be: about 1 time in 128 rather than 1 in 256. The shuffle hasn’t mixed the deck enough by then.

RC4’s first 8 output bytes, for many random 16-byte keys: how often each was 0, against 1 in 256 (dashed). The second byte (orange) stands out at about twice that; the others sit at about 1 (200,000 keys give 1.94× for byte 2 in the tests).

A one-in-128 chance sounds harmless, but it’s enough to read a message. Suppose the same message is sent many times, each under a different key, as happens when a secret, such as a password or a cookie, is resent with every connection. Eve collects the second byte of each ciphertext. Most of the time it’s the message’s byte XOR some random keystream byte, which could be anything; but twice as often as any other value, the keystream byte is 0 and the ciphertext byte is the message’s byte. So Eve counts, and the commonest value wins.

The secret message is sent the chosen number of times, each under a fresh random key. The bars count each value of the second ciphertext byte; the tallest (orange) is Eve’s guess at the message’s second character. In the tests, 20,000 copies gave the right answer for 40 trial runs out of 40, and 1,000 copies only 4 times: with too few, the random spread hides the extra.

That bias only touches the second byte, and others turned up for later bytes. The worse damage came from the key shuffle. Wi-Fi’s first encryption, WEP, built each packet’s RC4 key by putting a 24-bit value, sent openly with the packet, in front of the network’s secret key. Scott Fluhrer, Itsik Mantin and Adi Shamir showed in 2001 that keys built like that leak their secret part through the first output bytes, and tools that recovered a network’s key from captured traffic followed within months. That 24-bit value was also simply too short: with 2²⁴ of them, chosen at random, a repeat (and so a reused keystream) is more likely than not within 4,823 packets. More biases kept being found, until in 2015 RC4 was banned from secure web connections altogether (RFC 7465).

The lesson is the one every broken cipher teaches: an output that looks random to the eye can still be lopsided in ways that a patient attacker, with enough samples, can measure.

4 · ChaCha20: add, rotate, XOR

ChaCha20, by Daniel Bernstein (2008), is what replaced RC4 in many places, including today’s secure web connections. It has no table and no secret-dependent memory lookups. It works on 32-bit words, with only three operations:

add (wrapping round at 2³²),
rotate (shift the bits along, the ones falling off one end coming back in at the other),
XOR.

Each is fast and simple on any processor. What makes them strong together is that they don’t get along: adding mixes bits upwards with carries, which XOR knows nothing about, and rotating moves bits sideways into positions that the next add and XOR mix again. The quarter-round combines them on four words, a, b, c and d, four times over:

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

(+= adds, ^= XORs, <<<= rotates left by that many bits.)

The quarter-round, one operation at a time, on four words in hex. The starting words are the example in the standard, RFC 8439; all twelve steps end at its answer, ea2a92f4 cb1cf8ce 4581472e 5881c4bb (checked in the tests). Each row highlights the word it changed. Type other words and step again.

The whole cipher works on a 4 × 4 grid of 16 words: four fixed constants, eight words of key, a block counter, and three words of nonce. It applies quarter-rounds down the four columns, then along the four diagonals, and repeats: 20 rounds in all. Finally it adds the starting grid back in (so the mixing can’t simply be run backwards to find the key), and the 64 bytes that result are the next block of keystream. The next block has the next counter value.

ChaCha20’s 16 words with the standard’s example key, counter and nonce, round by round. Tick the box to run a second copy with one bit of the key flipped: each word is shaded by how many of its 32 bits differ between the two, and the plot follows the total. After one round 35 of the 512 bits differ, after two 219, and from round 3 on, about half: as different as two unrelated blocks (pinned in the tests). Then it goes on for 17 more rounds.

Twenty rounds is a wide margin: the best published attacks reach about seven. ChaCha20 is also checked here against all of RFC 8439’s examples, including the standard’s own sample message (“Ladies and Gentlemen of the class of ‘99…”), encrypted to the byte.

5 · The nonce rule

A stream cipher is only as good as its nonces. Two messages under the same key and nonce get the same keystream, and then XORing their ciphertexts cancels it, leaving the two messages XORed together: the two-time pad, with everything that page’s crib dragging could do.

Two messages encrypted with ChaCha20 under one key. With the same nonce for both, ciphertext 1 ⊕ ciphertext 2 equals message 1 ⊕ message 2 at every byte (highlighted): the key has dropped out, however strong the cipher. Untick the box to give the second message its own nonce, and the match disappears.

And even used correctly, a stream cipher only hides. Mallory can still flip bits in the ciphertext to flip the same bits in the message, exactly as on What we want from cryptography. Real systems always pair a stream cipher with a check that catches changes: ChaCha20 is almost always used with a companion, Poly1305, that does exactly that.

Summary

A stream cipher stretches a short key into a long keystream, and XORs it with the message: the one-time pad, made practical.
Each message needs a nonce that’s never repeated under the same key; reusing one is the two-time pad.
RC4 is a key-driven shuffle of 256 numbers. It’s small and elegant, and its output is lopsided: the second byte is 0 twice as often as it should be, enough to read a byte sent under many keys. WEP’s construction made it far worse, and RC4 is now banned from secure web connections.
ChaCha20 mixes a 4 × 4 grid of words with add, rotate and XOR, 20 rounds of quarter-rounds; one flipped key bit changes about half the state within three rounds.
A stream cipher hides, but doesn’t stop changes.