Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 40 ยท Symmetric Encryption

Stream Ciphers and Keystreams

Learn how stream ciphers turn a short key into an endless keystream, build ChaCha20 from scratch in Python, and see why reusing a nonce is fatal.

The one-time pad is perfectly secret, but it needs a random key as long as the message, used once. That is impractical: if you could safely share a gigabyte of key, you could simply share the gigabyte of data. A stream cipher keeps the good part of the pad (XOR the message with a stream of bytes) and fixes the bad part: it generates the long stream from a short key, which can be just 16 or 32 bytes.

The generated stream is called the keystream. It is not truly random, but a good generator makes it computationally indistinguishable from random bytes for anyone who does not know the key. This lesson builds a keystream from a hash function, then implements ChaCha20, the stream cipher used in TLS and in many VPNs, entirely from scratch. You will also see the one rule you must never break: never reuse a key and nonce pair.

The keystream idea

Encryption and decryption are the same operation:

  • Encrypt: ciphertext = plaintext XOR keystream
  • Decrypt: plaintext = ciphertext XOR keystream

XOR undoes itself, so both sides only need the same keystream. The whole security of the cipher rests on the keystream generator: given the key, both parties produce identical bytes, but an attacker who sees any amount of keystream must not be able to predict the next byte or work out the key.

flowchart LR
    K["Key + nonce"] --> G["Keystream<br/>generator"]
    G --> KS["Keystream bytes"]
    P["Plaintext"] --> X(("XOR"))
    KS --> X
    X --> C["Ciphertext"]

A stream cipher is a keystream generator plus one XOR.

Here is the smallest possible example. We build the keystream from SHA-256: hash the key together with a counter, and glue the digests together. This is not a standard cipher, but it shows the structure. (Hash functions are covered in Cryptographic Hash Functions.)

Python A toy keystream from SHA-256

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The key is 16 bytes but the message could be a megabyte: the generator stretches the key to any length. Notice also that the ciphertext is exactly as long as the message. That is a real advantage over block ciphers, which work on fixed-size chunks and sometimes need padding.

The nonce

There is a catch. A key plus a counter always produces the same keystream, so encrypting two messages with the same key reuses it. The fix is a nonce ("number used once"): a value, different for every message, that is mixed into the generator together with the key. The nonce is not secret. It is sent along with the ciphertext. Its only job is to make the keystream unique for each message.

A stream cipher is therefore a function of three inputs: key, nonce and a block counter that advances as the keystream gets longer. The rule that matters is:

Never use the same key and nonce for two different messages. The two keystreams would be identical, and the secrecy of both messages collapses (you will see how in a moment).

ChaCha20 from scratch

ChaCha20, designed by Daniel J. Bernstein, builds its keystream from a 4x4 grid of 32-bit words. Four of them are fixed constants (the ASCII text expand 32-byte k), eight are the 256-bit key, one is a block counter and three are the 96-bit nonce. The core operation is the quarter round, which mixes four words using only three cheap operations: addition modulo 232, XOR and bit rotation. That is why it is fast even on devices without special AES hardware.

Twenty rounds (ten "column" rounds and ten "diagonal" rounds) scramble the grid thoroughly. The result is added to the starting grid, and the 64 bytes that come out are one block of keystream. For the next 64 bytes, the counter goes up by one.

flowchart TD
    S["Initial state: 4 constants,<br/>8 key words, counter, 3 nonce words"] --> R["20 rounds of<br/>quarter rounds"]
    R --> A["Add the initial state back"]
    A --> B["64 bytes of keystream"]
    B --> N["Counter + 1 for<br/>the next block"]

One ChaCha20 block: scramble, add the start state back, output 64 bytes.

The code below follows the specification in RFC 8439. The final check uses the official test vector for the block function, so you can see that your implementation matches the real thing.

Python ChaCha20 in 30 lines of Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the first four bytes print as 10f1e7e4, your quarter round, state layout and byte order are all correct. Real libraries do exactly this, only faster.

Note: ChaCha20 is the successor of Salsa20. Its 20 rounds leave a large safety margin, and it runs in constant time with no table lookups, which makes timing attacks on it much harder than on a naive software AES. In practice you pair it with an authentication tag; see Authenticated Encryption.

What happens when a nonce is reused

Suppose Alice encrypts two different messages with the same key and the same nonce. The keystream is the same K both times:

  • C1 = P1 XOR K
  • C2 = P2 XOR K

An eavesdropper XORs the two ciphertexts, and the keystream cancels out: C1 XOR C2 = P1 XOR P2. She never needed the key. Now she has the XOR of two English texts, which is easy to attack. If she can guess a word that appears in one message (a "crib"), she XORs it at every position and reads off the matching piece of the other message. This is the same attack as the two-time pad in the one-time pad lesson, and it is the reason nonces are not optional.

Python Nonce reuse leaks the plaintexts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only readable results are printed. Sliding the guess "Password" along the leak reveals the word "Transfer" at position 0: because the second message starts with "Password", XORing it into the leak peels it away and exposes the first message. With more guesses, the attacker unravels both texts. With fresh nonces the XOR no longer equals P1 XOR P2.

How to pick nonces

  • Counter: 0, 1, 2, ... works if you can store the counter reliably and never roll it back (for example after restoring a backup).
  • Random: a random nonce is fine only if it is long enough that collisions are negligible. ChaCha20's 96-bit nonce is acceptable for a moderate number of messages per key; for huge volumes use a longer nonce (XChaCha20 has 192 bits) or change keys regularly.

Two further limits apply to every stream cipher. The ciphertext is malleable: flipping a bit of the ciphertext flips the same bit of the plaintext, with no error. And the counter can only count so far: ChaCha20 with a 32-bit counter can encrypt at most 256 GiB under one key and nonce. Authentication (covered soon) deals with the first problem, and sensible key management with the second.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a stream cipher do with its key?

    The generator stretches a short key (plus a nonce) into a long keystream. Encryption and decryption are both an XOR with that keystream.
  2. 2. Which statement about the nonce is correct?

    A nonce only has to be unique per key. Because it is not secret, it normally travels next to the ciphertext.
  3. 3. Two messages are encrypted with the same key and nonce. What can an eavesdropper compute from the ciphertexts alone?

    C1 XOR C2 equals P1 XOR P2 because the identical keystreams cancel. That is enough to start recovering both messages with guessed words.
  4. 4. Why does the ChaCha20 block function add the initial state to the scrambled state at the end?

    The rounds alone are reversible. Adding the original state back makes the block function one-way, so seeing keystream does not reveal the key.

Summary

  • A stream cipher expands a short key and a nonce into a keystream and XORs it with the data; decryption is the identical operation.
  • ChaCha20 builds each 64-byte keystream block from constants, a 256-bit key, a counter and a 96-bit nonce using only add, XOR and rotate.
  • The nonce is public but must never repeat under one key: reuse leaks P1 XOR P2.
  • Stream ciphers are malleable, so they need authentication on top.

Next: Block Ciphers and AES, the other main family of symmetric ciphers.