The ChaCha20 stream cipher

ChaCha20 is a stream cipher Daniel J. Bernstein designed in 2008. Given a 256-bit key and a 96-bit nonce, it turns sixteen 32-bit words into an endless stream of pseudo-random bytes using only adding, rotating and XORing, and that stream is XORed with the message. There are no table lookups and no special hardware, so it's fast on phones and immune to the cache-timing leaks that trouble software AES. Paired with the Poly1305 authenticator, it's the second cipher, after AES-GCM, that almost every secure connection on the internet can use.

How it works

The state is a 4×4 grid of 32-bit words: four fixed constants (the ASCII text "expand 32-byte k"), the eight words of the key, a 32-bit block counter and the three words of the nonce.

To make 64 bytes of key stream, the cipher copies the state and runs 20 rounds, as ten double rounds. Each round applies the quarter round four times, once to each group of 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. In the first round of a pair the four quarter rounds go down the columns of the grid, and in the second they go along the diagonals, so every word soon influences every other. At the end the original state is added back to the result, which stops anyone from running the rounds in reverse. What's left is the 64 bytes of key stream for that counter. Add 1 to the counter and repeat for the next block. To encrypt, XOR the stream with the message, and to decrypt, do it again.

Addition mod 2³², rotation and XOR all take the same time whatever the data, which is why ChaCha20 is easy to implement without leaking the key through timing. The code listing below is the whole cipher apart from the loop around the block function. The project's tests check it against the numbers in RFC 8439: the quarter round of section 2.1.1, the block of section 2.3.2 and the encrypted text of section 2.4.2. They also check random keys and messages against OpenSSL.

Poly1305 and the AEAD

A stream cipher on its own doesn't detect changes. Flip a bit of the ciphertext and the same bit flips in the plaintext. That's why ChaCha20 is paired with Poly1305, a message authentication code Bernstein designed in 2005. Poly1305 treats the message as a series of 16-byte numbers and evaluates a polynomial at a secret point, modulo the prime 2¹³⁰ − 5, then adds a second secret and keeps 128 bits as the tag. The combination, ChaCha20-Poly1305, works like AES-GCM. The first block of key stream (counter 0) supplies the one-time Poly1305 key, the message is encrypted from counter 1, and the tag covers the associated data and the ciphertext. Decryption recomputes the tag first and releases nothing if it doesn't match. Our library implements all of this and agrees with OpenSSL on random inputs, and it rejects a single flipped bit.

History and use

ChaCha20 is a variant of Bernstein's earlier Salsa20 (2005), with a rearranged quarter round that spreads changes faster. The IETF adopted a version with a 32-bit counter and 96-bit nonce for TLS as RFC 7539 in 2015, and replaced it with RFC 8439 in June 2018. OpenSSH added it soon after the TLS adoption, and Cloudflare introduced it as an alternative cipher suite in 2015. It's now used in TLS 1.2 and 1.3, SSH, IPsec, DTLS, WireGuard, S/MIME 4.0 and OTRv4, among others.

Its big advantage is speed without hardware support. On a processor with AES instructions, AES-GCM is faster. On one without, such as many phones and embedded devices, ChaCha20-Poly1305 is usually faster and may use less power. That's why browsers and servers offer both and let the client choose. A variant, XChaCha20-Poly1305, has a 192-bit nonce that's safe to choose at random.

Security

• No practical attack on the full 20 rounds is known. The construction is generally considered secure in the standard models.
• Nonce reuse is fatal, as in every stream cipher. Two messages under one key and nonce give the XOR of the plaintexts (the one-time pad page explains why). Each message needs its own nonce.
• Timing. Implementations are naturally less prone to timing attacks than table-based AES.
• Protocol issues. In SSH, the cipher has been implicated in the Terrapin attack. That's a flaw in how the SSH handshake is protected and not in ChaCha20 itself.

The code

// ChaCha20. The state is sixteen 32-bit words: four constants, the 256-bit key, a block counter and the 96-bit nonce.
function rotl(v, n) { return ((v << n) | (v >>> (32 - n))) >>> 0; }

// The quarter round mixes four words with only additions, rotations and XORs.
function quarterRound(x, a, b, c, d) {
  x[a] = (x[a] + x[b]) >>> 0; x[d] = rotl(x[d] ^ x[a], 16);
  x[c] = (x[c] + x[d]) >>> 0; x[b] = rotl(x[b] ^ x[c], 12);
  x[a] = (x[a] + x[b]) >>> 0; x[d] = rotl(x[d] ^ x[a], 8);
  x[c] = (x[c] + x[d]) >>> 0; x[b] = rotl(x[b] ^ x[c], 7);
}

// One 64-byte block of key stream: ten double rounds (columns, then diagonals), then add the starting state back in.
function chachaBlock(state) {
  var x = state.slice(), out = [], i;
  for (i = 0; i < 10; i++) {
    quarterRound(x, 0, 4, 8, 12); quarterRound(x, 1, 5, 9, 13); quarterRound(x, 2, 6, 10, 14); quarterRound(x, 3, 7, 11, 15);
    quarterRound(x, 0, 5, 10, 15); quarterRound(x, 1, 6, 11, 12); quarterRound(x, 2, 7, 8, 13); quarterRound(x, 3, 4, 9, 14);
  }
  for (i = 0; i < 16; i++) { var w = (x[i] + state[i]) >>> 0; out.push(w & 255, (w >>> 8) & 255, (w >>> 16) & 255, w >>> 24); }
  return out;   // XOR these 64 bytes with the message, then add 1 to the counter (state[12]) for the next block
}

Common questions