ChaCha20-Poly1305, in depth: the ARX stream cipher, the Poly1305 one-time MAC, a verified RFC 8439 implementation, nonce rules and when to choose it over AES-GCM

ChaCha20: the keystream generator

ChaCha20 turns a 256-bit key, a 32-bit block counter and a 96-bit nonce into 64-byte blocks of keystream. The state is sixteen 32-bit words: four constants, eight key words, the counter and three nonce words. The core operation is the quarter round, which mixes four words with add, rotate and XOR (ARX):

import struct

MASK = 0xFFFFFFFF

def rotl(x, n):
    return ((x << n) | (x >> (32 - n))) & MASK

def quarter_round(s, a, b, c, d):
    s[a] = (s[a] + s[b]) & MASK; s[d] = rotl(s[d] ^ s[a], 16)
    s[c] = (s[c] + s[d]) & MASK; s[b] = rotl(s[b] ^ s[c], 12)
    s[a] = (s[a] + s[b]) & MASK; s[d] = rotl(s[d] ^ s[a], 8)
    s[c] = (s[c] + s[d]) & MASK; s[b] = rotl(s[b] ^ s[c], 7)

def chacha20_block(key, counter, nonce):
    state = [0x61707865, 0x3320646E, 0x79622D32, 0x6B206574]
    state += list(struct.unpack("<8I", key))
    state += [counter] + list(struct.unpack("<3I", nonce))
    w = state[:]
    for _ in range(10):                      # 10 double rounds = 20 rounds
        quarter_round(w, 0, 4, 8, 12); quarter_round(w, 1, 5, 9, 13)
        quarter_round(w, 2, 6, 10, 14); quarter_round(w, 3, 7, 11, 15)
        quarter_round(w, 0, 5, 10, 15); quarter_round(w, 1, 6, 11, 12)
        quarter_round(w, 2, 7, 8, 13); quarter_round(w, 3, 4, 9, 14)
    out = [(x + y) & MASK for x, y in zip(w, state)]
    return struct.pack("<16I", *out)

def chacha20_xor(key, counter, nonce, data):
    out = bytearray()
    for i in range(0, len(data), 64):
        ks = chacha20_block(key, counter + i // 64, nonce)
        out += bytes(x ^ y for x, y in zip(data[i:i + 64], ks))
    return bytes(out)

Three details carry the security. Addition mod 2^32 is nonlinear over XOR, which is what makes the function hard to invert. The rotations move bits between positions so every output bit soon depends on every input bit. And the final step adds the original state back; without it, anyone could run the rounds backwards from a keystream block to recover the key. Columns then diagonals means each double round mixes every word with every other.

The specification gives a test vector for one quarter round: inputs 0x11111111, 0x01020304, 0x9b8d6f43 and 0x01234567 must become 0xea2a92f4, 0xcb1cf8ce, 0x4581472e and 0x5881c4bb. The code above reproduces it. Check that first whenever you port the cipher; it catches swapped rotation amounts and endianness mistakes in seconds.

Poly1305: a polynomial evaluated at a secret point

Poly1305 authenticates a message with a 32-byte one-time key split into two halves, r and s. The message is cut into 16-byte chunks. Each chunk is read as a little-endian number with an extra 1 bit appended just above its top byte, so that trailing zero bytes still change the value. An accumulator is updated as acc = (acc + chunk) times r, modulo the prime 2^130 - 5. The tag is acc + s modulo 2^128. In other words, the message is evaluated as a polynomial at the secret point r, then masked with s.

P1305 = (1 << 130) - 5

def poly1305(key, msg):
    r = int.from_bytes(key[:16], "little") & 0x0FFFFFFC0FFFFFFC0FFFFFFC0FFFFFFF
    s = int.from_bytes(key[16:], "little")
    acc = 0
    for i in range(0, len(msg), 16):
        n = int.from_bytes(msg[i:i + 16] + b"\x01", "little")
        acc = (acc + n) * r % P1305
    return ((acc + s) % (1 << 128)).to_bytes(16, "little")

The mask on r is called clamping. It clears a few bits so that fast implementations can split r into limbs and multiply without overflow; it is part of the specification, not an optimisation you can skip. The prime 2^130 - 5 was chosen because reduction modulo it is cheap: the bits above position 130 are multiplied by 5 and added back.

The word one-time is literal. Poly1305 is secure only if each (r, s) pair authenticates a single message. Two tags under the same key give an attacker two polynomial equations in r, which can be solved, after which they can forge tags for any message. The AEAD construction exists to make this impossible to get wrong, as long as nonces never repeat.

This Python is for learning only. Its big-integer arithmetic takes time that depends on the values, so it is not constant-time, and production code must use a vetted library.

The AEAD construction

The AEAD glues the parts together in a fixed way. ChaCha20 block 0 under the message's key and nonce produces 64 bytes; the first 32 become the Poly1305 key, so every nonce yields a fresh one-time key. Encryption uses blocks 1 onward. The MAC covers the associated data, the ciphertext, padding to 16-byte boundaries and both lengths, so an attacker cannot shift bytes between the header and the body.

import hmac

def pad16(b):
    return b"\x00" * (-len(b) % 16)

def mac_input(aad, ct):
    return (aad + pad16(aad) + ct + pad16(ct)
            + struct.pack("<QQ", len(aad), len(ct)))

def seal(key, nonce, plaintext, aad=b""):
    otk = chacha20_block(key, 0, nonce)[:32]          # one-time Poly1305 key
    ct = chacha20_xor(key, 1, nonce, plaintext)        # encryption starts at block 1
    return ct + poly1305(otk, mac_input(aad, ct))

def open_(key, nonce, sealed, aad=b""):
    if len(sealed) < 16:
        raise ValueError("ciphertext too short")
    ct, tag = sealed[:-16], sealed[-16:]
    otk = chacha20_block(key, 0, nonce)[:32]
    if not hmac.compare_digest(poly1305(otk, mac_input(aad, ct)), tag):
        raise ValueError("authentication failed")      # never return plaintext
    return chacha20_xor(key, 1, nonce, ct)

Note the order in open_: the tag is recomputed and compared in constant time with hmac.compare_digest before any plaintext exists. Decrypting first and checking later invites code paths that act on forged data.

Verifying against a production library

To check the implementation, compare it with the pyca cryptography package, whose ChaCha20Poly1305 class implements RFC 8439:

import os
from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305
from cryptography.exceptions import InvalidTag

for n in [0, 1, 15, 16, 17, 64, 65, 200]:
    k, nonce = os.urandom(32), os.urandom(12)
    msg, aad = os.urandom(n), os.urandom(n % 7 * 3)
    assert seal(k, nonce, msg, aad) == ChaCha20Poly1305(k).encrypt(nonce, msg, aad)

k, nonce = os.urandom(32), os.urandom(12)
ct = ChaCha20Poly1305(k).encrypt(nonce, b"attack at dawn", b"hdr")
bad = bytearray(ct); bad[0] ^= 1
try:
    ChaCha20Poly1305(k).decrypt(nonce, bytes(bad), b"hdr")
except InvalidTag:
    print("tampered ciphertext rejected")

The lengths are chosen to hit the edges: empty input, partial chunks, exact multiples of 16 and of 64, and one byte past a block boundary. Both the reference code and the library reject a flipped ciphertext bit and a changed associated-data byte. For a real system, call the library directly; the reference exists so you understand what it does.

A worked example of the data flow: a 100-byte message with a 13-byte header uses keystream blocks 1 and 2 (64 + 36 bytes). The MAC input is 13 bytes of header, 3 bytes of padding, 100 bytes of ciphertext, 12 bytes of padding and 16 bytes of lengths, 144 bytes or nine Poly1305 chunks. The sealed output is 116 bytes.

Operating it safely: nonces, limits and keys

Nonces. The 96-bit nonce must never repeat under one key. Reuse leaks the XOR of the two plaintexts, because both were XORed with the same keystream, and it reuses the Poly1305 key, which lets an attacker recover r and forge messages. Two safe patterns exist. A counter per key works when one sender owns the key and its state survives restarts; TLS 1.3 and WireGuard both derive nonces from per-connection record or packet counters. Random nonces work when many writers share a key, but a 96-bit random value is only safe for a bounded number of messages per key because of the birthday bound, so rotate keys well before around 2^32 messages.

Extended nonces. XChaCha20-Poly1305 uses a 192-bit nonce, derived through a step called HChaCha20, so random nonces are safe at almost any volume. It is widely implemented, for example in libsodium, but its IRTF specification (draft-irtf-cfrg-xchacha) expired as an Internet-Draft and never became an RFC. Use it when a library you trust supports it and you control both ends.

Message size. With a 32-bit block counter starting at 1, one message can use at most 2^32 - 1 blocks of 64 bytes, just under 256 GiB. Libraries enforce this; streaming formats should chunk large files into many sealed records anyway, so that corruption is caught early and memory stays bounded.

Keys. Use 32 random bytes from the operating system, or derive them with a KDF such as HKDF from a key exchange like X25519, as described in the Diffie-Hellman article. Never use a password directly as the key.

In application code the whole API is three calls with the pyca library: key = ChaCha20Poly1305.generate_key(), ct = aead.encrypt(nonce, data, aad) and aead.decrypt(nonce, ct, aad), which raises InvalidTag on any tampering.

ChaCha20-Poly1305 versus AES-GCM

AES-GCM is the other mainstream AEAD. On CPUs with AES and carry-less multiply instructions, which covers most current x86 and Arm server cores, AES-GCM is usually as fast or faster. On CPUs without them, AES must be done in software, where table-based implementations leak timing through the cache and constant-time ones are slow; ChaCha20 is fast and constant-time there by construction. TLS stacks often let the client signal its preference so phones without AES hardware get ChaCha20. The side-channel article explains the cache-timing problem, and the AES article covers the block cipher itself.

Neither is misuse-resistant. If you cannot guarantee unique nonces, look at a nonce-misuse resistant mode such as AES-GCM-SIV (RFC 8452) instead of hoping.

Failure modes

• Nonce reuse after a restart resets a counter, after a VM snapshot is cloned, or when two processes share a key and a counter. Persist counters, and give each writer its own key.
• Releasing unverified plaintext, for example streaming decrypted bytes to a client before the final tag check. Buffer, or seal small records and verify each.
• Non-constant-time tag comparison with ==, which can leak how many bytes matched. Use a constant-time compare.
• Forgetting the associated data: headers such as record type or user id that are not bound as AAD can be swapped between messages without detection.
• Truncated tags to save space. Every removed byte weakens forgery resistance; keep all 16.
• Mixing variants: the original Bernstein ChaCha uses a 64-bit nonce and 64-bit counter, the IETF version a 96-bit nonce and 32-bit counter. Two libraries with different variants produce different output for the same key.

What to do next

1. Run the quarter-round test vector and the library comparison above to make sure you can read the construction end to end.
2. In your own code, find every place that encrypts with an AEAD and write down how its nonce is produced and why it cannot repeat.
3. Check that every decrypt path verifies the tag before any plaintext is used or logged.
4. List the header fields each message depends on and bind them as associated data.
5. Set a key-rotation rule based on message count, and test that it fires.
6. Read how WireGuard uses this AEAD with per-packet counters, as a model of nonce management done well.