The XChaCha20-Poly1305 Algorithm

The XChaCha20-Poly1305 Algorithm

Introduction

ChaCha20-Poly1305 is a fast, popular authenticated encryption cipher, and it has one weak spot that is easy to overlook. Its nonce has only 96 bits. If you pick nonces at random, which is the simplest thing to do, the chance that two of them collide grows steadily as you encrypt more messages under one key. A collision is serious, because it breaks both secrecy and authenticity.

XChaCha20-Poly1305 fixes that with one extra step and a longer nonce. The nonce grows from 96 to 192 bits, which is so large that you can generate it randomly for every message and stop worrying. This guide builds on the ChaCha20-Poly1305 guide. If you have not read it, the ChaCha20 core and Poly1305 are explained there in more detail.

Table of Contents

• History and Status
• The Nonce Problem
• HChaCha20
• Building the AEAD
• Poly1305 in Short
• Decryption
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History and Status

The extended-nonce idea comes from Daniel Bernstein’s XSalsa20, which extends the nonce of Salsa20 in the same way. Scott Arciszewski of Paragon Initiative Enterprises wrote it up for ChaCha as an Internet-Draft, draft-irtf-cfrg-xchacha. The draft is not an RFC, and the version used here, number 03 from January 2020, has expired. Even so, the construction is widely implemented.

The draft lists WireGuard, libsodium, Tink, and Go’s crypto/chacha20poly1305 library among the projects that already implement XChaCha20-Poly1305. LibreSSL implements it as well, and Google’s HPolyC uses the XChaCha12 variant.

Be careful with the WireGuard entry. Its data packets use the ordinary ChaCha20-Poly1305 of RFC 8439, with a nonce made of 32 zero bits and a 64-bit packet counter. WireGuard uses XChaCha20-Poly1305 only for its cookie reply message, with a random 24-byte nonce.

Libsodium names its version crypto_aead_xchacha20poly1305_ietf_encrypt. The ietf in the name marks the layout of RFC 8439, with a 32-bit block counter and a 12-byte nonce. Bernstein’s original ChaCha instead has a 64-bit counter and a 64-bit nonce.

The Nonce Problem

The draft explains why a longer nonce helps. It also gives two numbers for 192-bit random nonces: they collide with probability one half after about 2⁹⁶ messages, and a more conservative threshold of 2⁻³² collision probability still allows 2⁸⁰ messages under one key.

You can check the second figure with the birthday formula. For n random nonces of b bits, the chance of a collision is about n² / 2^(b+1). Setting this equal to 2⁻³² and solving for n gives n = 2^((b + 1 - 32) / 2). For a 96-bit nonce that is about 2^32.5 messages, a little over 6 billion. For a 192-bit nonce it is about 2^80.5 messages. A 96-bit random nonce is therefore workable only when the key sees a small number of messages, while a 192-bit nonce makes the question irrelevant.

HChaCha20

The extra nonce bits go into HChaCha20, a small function that turns a 256-bit key and a 128-bit nonce into a new 256-bit key. It is based on the same ChaCha state as ChaCha20, with one difference in how the state is filled:

cccccccc cccccccc cccccccc cccccccc      c = constants
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk      k = key
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
nnnnnnnn nnnnnnnn nnnnnnnn nnnnnnnn      n = the 16-byte nonce, with no block counter

In ChaCha20, the last row holds a block counter and a 96-bit nonce. HChaCha20 uses all four words of the last row for the 128-bit nonce. It then runs the 20 ChaCha rounds as usual. At the end it does not add the original state back in. It takes the first row and the last row of the final state, and those eight words are the new key.

Building the AEAD

XChaCha20-Poly1305 splits the 24-byte nonce in two parts and uses each for its own job:

1. Make a subkey. Run HChaCha20 with the key and the first 16 bytes of the nonce. The 32-byte result is the subkey.
2. Make a 12-byte nonce. Take four zero bytes and put the last 8 bytes of the nonce after them.
3. Run ChaCha20-Poly1305. Use the subkey and the 12-byte nonce in the ordinary AEAD of RFC 8439.

That is the whole change. The ordinary AEAD then works like this. ChaCha20 block number 0 is not used for encryption. Its first 32 bytes become the one-time Poly1305 key. The data is encrypted with ChaCha20 starting at block counter 1. A Poly1305 tag is then computed over the associated data, the ciphertext, and their lengths.

Splitting the nonce in this way has a pleasant effect. If two messages share only the last 8 bytes of the nonce, they get different subkeys, so their keystreams are unrelated. If they share only the first 16 bytes, they get the same subkey but different ChaCha20 nonces. Either way, a partial collision does no harm.

Interactive Visualizer

The visualizer above runs this exact algorithm. Enter a 256-bit key, a 24-byte nonce, associated data, and a message in hex. The log shows the HChaCha20 state, the subkey, each keystream block, and each step of Poly1305. To decrypt, paste the ciphertext and tag into the message box and click Decrypt. Change one hex digit first, and the tag check fails.

Poly1305 in Short

Poly1305 is a one-time authenticator. Its 32-byte key is split into two halves, r and s. The half r has some bits cleared, which is called clamping. The data is cut into 16-byte blocks. Each block, with a byte of value 1 added at its end, is read as a number. The accumulator is updated for every block, with arithmetic modulo the prime 2^130 - 5:

acc = (acc + block) * r  mod (2^130 - 5)
tag = (acc + s) mod 2^128

For the AEAD, the data fed into Poly1305 has four parts. First comes the associated data, padded with zeros to a multiple of 16 bytes. Then comes the ciphertext, padded the same way. The last two parts are 8-byte little-endian numbers: the length of the associated data and the length of the ciphertext.

Decryption

The receiver derives the same subkey and one-time key, and it recomputes the tag over the associated data and the ciphertext that arrived. If the tag does not match, decryption stops and no plaintext is released. Otherwise ChaCha20 decrypts the data from block counter 1. A good implementation compares the tags in constant time.

This order differs from AES-CCM and AES-SIV. Their tags cover the plaintext, so they must decrypt first. Poly1305 covers the ciphertext, so the receiver can check the tag before decrypting a single byte. No unverified plaintext ever exists.

A Worked Example

This is the example from Appendix A.1 of the draft. The key is 808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9f, the nonce is 404142434445464748494a4b4c4d4e4f5051525354555657, and the associated data is 50515253c0c1c2c3c4c5c6c7. The plaintext is the 114-byte sentence Ladies and Gentlemen of the class of '99: If I could offer you only one tip for the future, sunscreen would be it.

HChaCha20. First, the algorithm’s own test vector. For the key 00 01 02 ... 1f and the nonce 000000090000004a0000000031415927, the starting state is:

61707865 3320646e 79622d32 6b206574
03020100 07060504 0b0a0908 0f0e0d0c
13121110 17161514 1b1a1918 1f1e1d1c
09000000 4a000000 00000000 27594131

After the 20 rounds the state is:

423b4182 fe7bb227 50420ed3 737d878a
0aa76448 7954cdf3 846acd37 7b3c58ad
77e35583 83e77c12 e0076a2d bc6cd0e5
d5e4f9a0 53a8748a 13c42ec1 dcecd326

The first row and the last row, 423b4182 fe7bb227 50420ed3 737d878a d5e4f9a0 53a8748a 13c42ec1 dcecd326, written out as bytes, are the subkey 82413b4227b27bfed30e42508a877d73a0f9e4d58a74a853c12ec41326d3ecdc. The draft lists the same values.

The example’s subkey. The first 16 bytes of the nonce are 404142434445464748494a4b4c4d4e4f. HChaCha20 with the key gives the subkey 4a8ac0c0296222bafe959faabe06a45b89a3cee444fef6e3d77659a53f49ee32. The last 8 bytes of the nonce are 5051525354555657, so the ChaCha20 nonce is 000000005051525354555657.

The Poly1305 key. ChaCha20 block 0 under that subkey and nonce starts with 7b191f80f361f099094f6f4b8fb97df847cc6873a8f2b190dd73807183f907d5. The first half, 7b191f80f361f099094f6f4b8fb97df8, is in byte order. It is read as a little-endian number, so the last byte is the most significant. After clamping, that number is r = 087db98c0b6f4f0809f061f0001f197b, written with the most significant byte first. The second half, read the same way, is s = d507f983718073dd90b1f2a87368cc47. This is why the digits look reversed.

Encryption. The 114 bytes use two keystream blocks, with counters 1 and 2. The ciphertext starts with bd6d179d3e83d43b9576579493c0e939572a1700252bfaccbed2902c21396cbb.

The tag. The data fed to Poly1305 is 160 bytes, which is 10 blocks of 16. The last block holds the two lengths: 0c000000000000007200000000000000, which is 12 for the associated data and 114 for the ciphertext. The tag comes out as:

c0875924c1c7987947deafd8780acf49

All of these values match the draft. Changing one bit of the first 16 bytes of the nonce gives the completely different subkey cf9092a2a9fa7a37b4e68ab09ceecc04d0232dbd2bf80880644c10915b675959, and changing one bit of the last byte changes the ChaCha20 nonce to 000000005051525354555656.

Python Implementation

This is a complete XChaCha20-Poly1305: the ChaCha20 block function, HChaCha20, Poly1305, and the AEAD. It also includes the ordinary 12-byte-nonce ChaCha20-Poly1305 of RFC 8439.

# xchacha.py
#
# XChaCha20-Poly1305: ChaCha20-Poly1305 (RFC 8439) with a 192-bit nonce.
# HChaCha20 turns the key and the first 16 bytes of the nonce into a fresh
# subkey. The subkey and the last 8 bytes of the nonce, prefixed by four zero
# bytes, then feed the ordinary ChaCha20-Poly1305 AEAD. A 192-bit nonce is long
# enough to be chosen at random for every message.

MASK = 0xFFFFFFFF
CONSTANTS = (0x61707865, 0x3320646E, 0x79622D32, 0x6B206574)


def rol(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] = rol(s[d] ^ s[a], 16)
    s[c] = (s[c] + s[d]) & MASK
    s[b] = rol(s[b] ^ s[c], 12)
    s[a] = (s[a] + s[b]) & MASK
    s[d] = rol(s[d] ^ s[a], 8)
    s[c] = (s[c] + s[d]) & MASK
    s[b] = rol(s[b] ^ s[c], 7)


def twenty_rounds(s):
    """Ten double rounds: four column rounds, then four diagonal rounds."""
    for _ in range(10):
        quarter_round(s, 0, 4, 8, 12)
        quarter_round(s, 1, 5, 9, 13)
        quarter_round(s, 2, 6, 10, 14)
        quarter_round(s, 3, 7, 11, 15)
        quarter_round(s, 0, 5, 10, 15)
        quarter_round(s, 1, 6, 11, 12)
        quarter_round(s, 2, 7, 8, 13)
        quarter_round(s, 3, 4, 9, 14)


def words_le(data):
    return [int.from_bytes(data[i:i + 4], "little") for i in range(0, len(data), 4)]


def bytes_le(words):
    return b"".join(w.to_bytes(4, "little") for w in words)


def chacha20_block(key, counter, nonce):
    """One 64-byte keystream block (RFC 8439): 32-byte key, 32-bit counter, 12-byte nonce."""
    state = list(CONSTANTS) + words_le(key) + [counter] + words_le(nonce)
    working = list(state)
    twenty_rounds(working)
    return bytes_le([(a + b) & MASK for a, b in zip(working, state)])


def hchacha20(key, nonce16):
    """The 256-bit subkey: the first and last rows of the state after 20 rounds, without the final addition."""
    if len(key) != 32 or len(nonce16) != 16:
        raise ValueError("HChaCha20 takes a 32-byte key and a 16-byte nonce")
    state = list(CONSTANTS) + words_le(key) + words_le(nonce16)
    twenty_rounds(state)
    return bytes_le(state[0:4] + state[12:16])


def chacha20_crypt(key, counter, nonce, data):
    out = bytearray()
    for i in range(0, len(data), 64):
        block = chacha20_block(key, counter + i // 64, nonce)
        out += bytes(a ^ b for a, b in zip(data[i:i + 64], block))
    return bytes(out)


def poly1305(key, message):
    """Poly1305 one-time authenticator (RFC 8439): a 32-byte key makes a 16-byte tag."""
    r = int.from_bytes(key[:16], "little") & 0x0FFFFFFC0FFFFFFC0FFFFFFC0FFFFFFF
    s = int.from_bytes(key[16:], "little")
    p = (1 << 130) - 5
    acc = 0
    for i in range(0, len(message), 16):
        block = message[i:i + 16]
        acc = ((acc + int.from_bytes(block + b"\x01", "little")) * r) % p
    return ((acc + s) & ((1 << 128) - 1)).to_bytes(16, "little")


def pad16(data):
    return data + bytes(-len(data) % 16)


def mac_data(aad, ciphertext):
    return pad16(aad) + pad16(ciphertext) + len(aad).to_bytes(8, "little") + len(ciphertext).to_bytes(8, "little")


def aead_encrypt(key, nonce12, plaintext, aad=b""):
    """ChaCha20-Poly1305 (RFC 8439). Returns ciphertext followed by the 16-byte tag."""
    otk = chacha20_block(key, 0, nonce12)[:32]
    ciphertext = chacha20_crypt(key, 1, nonce12, plaintext)
    return ciphertext + poly1305(otk, mac_data(aad, ciphertext))


def aead_decrypt(key, nonce12, data, aad=b""):
    if len(data) < 16:
        raise ValueError("the input is shorter than the tag")
    ciphertext, received = data[:-16], data[-16:]
    otk = chacha20_block(key, 0, nonce12)[:32]
    expected = poly1305(otk, mac_data(aad, ciphertext))
    difference = 0
    for a, b in zip(expected, received):
        difference |= a ^ b
    if difference:
        raise ValueError("authentication failed")
    return chacha20_crypt(key, 1, nonce12, ciphertext)


def derive(key, nonce24):
    if len(key) != 32:
        raise ValueError("the key is 32 bytes")
    if len(nonce24) != 24:
        raise ValueError("the nonce is 24 bytes")
    return hchacha20(key, nonce24[:16]), bytes(4) + nonce24[16:]


def encrypt(key, nonce24, plaintext, aad=b""):
    subkey, nonce12 = derive(key, nonce24)
    return aead_encrypt(subkey, nonce12, plaintext, aad)


def decrypt(key, nonce24, data, aad=b""):
    subkey, nonce12 = derive(key, nonce24)
    return aead_decrypt(subkey, nonce12, data, aad)


if __name__ == "__main__":
    key = bytes.fromhex("808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9f")
    nonce = bytes.fromhex("404142434445464748494a4b4c4d4e4f5051525354555657")
    aad = bytes.fromhex("50515253c0c1c2c3c4c5c6c7")
    message = b"Ladies and Gentlemen of the class of '99: If I could offer you only one tip for the future, sunscreen would be it."
    sealed = encrypt(key, nonce, message, aad)
    print("Key:        " + key.hex())
    print("Nonce:      " + nonce.hex())
    print("Subkey:     " + derive(key, nonce)[0].hex())
    print("Ciphertext: " + sealed[:-16].hex())
    print("Tag:        " + sealed[-16:].hex())
    print("Recovered:  " + decrypt(key, nonce, sealed, aad).decode())
    try:
        decrypt(key, nonce, bytes([sealed[0] ^ 1]) + sealed[1:], aad)
    except ValueError as error:
        print("Tampered:   " + str(error))

Running it produces this output:

Key:        808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9f
Nonce:      404142434445464748494a4b4c4d4e4f5051525354555657
Subkey:     4a8ac0c0296222bafe959faabe06a45b89a3cee444fef6e3d77659a53f49ee32
Ciphertext: bd6d179d3e83d43b9576579493c0e939572a1700252bfaccbed2902c21396cbb731c7f1b0b4aa6440bf3a82f4eda7e39ae64c6708c54c216cb96b72e1213b4522f8c9ba40db5d945b11b69b982c1bb9e3f3fac2bc369488f76b2383565d3fff921f9664c97637da9768812f615c68b13b52e
Tag:        c0875924c1c7987947deafd8780acf49
Recovered:  Ladies and Gentlemen of the class of '99: If I could offer you only one tip for the future, sunscreen would be it.
Tampered:   authentication failed

I checked this code against several independent sources before writing it up. The ordinary AEAD reproduces the example of RFC 8439, section 2.8.2, including the one-time Poly1305 key and the exact data fed to Poly1305, and its Poly1305 matches the example of section 2.5.2. HChaCha20 reproduces the draft’s test vector, and the full cipher reproduces the draft’s example with the subkey, the Poly1305 key, the ciphertext, and the tag. It also passes the Wycheproof test suite for XChaCha20-Poly1305, with 246 valid cases reproduced exactly and 60 invalid ones rejected. Finally, using the HChaCha20 subkey, its AEAD half agrees with the OpenSSL that ships inside Node.js on 300 random cases. Changing any byte of the output makes decryption fail.

Limitations

This is a faithful teaching version of the cipher, not a production one:

• Still a nonce-respecting mode. A random 192-bit nonce makes collisions negligible, but if you do reuse a nonce with different messages, the cipher loses secrecy and authenticity like any other ChaCha20-Poly1305. For nonce-misuse resistance, see AES-SIV.
• Python is slow. Real implementations use vector instructions, and this one does a single block at a time.
• Not constant-time. Python integers are not suitable for secret data, and the tag check here is only a simple loop.
• No streaming. The code works on whole messages in memory.

Security Status

The draft states that if ChaCha20-Poly1305 is a secure AEAD cipher and ChaCha is a secure pseudorandom function, then XChaCha20-Poly1305 is secure. The security argument for HChaCha20 follows the one for HSalsa20 in the XSalsa20 paper. The words kept as output are the constants and the nonce positions of the state, rows 0 and 3, and the argument relies on these being public inputs.

No practical attack on XChaCha20-Poly1305 is known. The draft recommends it for systems that encrypt a large number of messages with randomly chosen nonces. Because it is a standard ChaCha20-Poly1305 after the first step, the limits of that cipher still apply to each message. The block counter is 32 bits, and block 0 makes the Poly1305 key, so RFC 8439 caps the plaintext at 274,877,906,880 bytes, which is nearly 256 GB.

The nonce rule has a clear algebraic reason. Poly1305 hides its accumulator by adding s. A repeated nonce reuses the same r and s for two messages. Subtracting the two tags cancels s and leaves the difference of two accumulators, which is a polynomial in r. The attacker can solve it for r, with a handful of candidates, because the tags are cut to 128 bits. Once r is known, s follows from any known tag, and the attacker can compute valid tags for any ciphertext under that nonce.

FAQ

How is XChaCha20-Poly1305 different from ChaCha20-Poly1305?

The only change is the nonce. XChaCha20-Poly1305 takes 24 bytes instead of 12, and it turns the first 16 of them into a new key with HChaCha20. After that step it is the same cipher.

Can I use random nonces?

Yes, and that is the reason it exists. A random 192-bit nonce can be used for 2⁸⁰ messages before the chance of a collision reaches about 2⁻³², which no real system will reach.

Is XChaCha20-Poly1305 an IETF standard?

It is only an Internet-Draft that expired in 2020, though the construction is implemented in many libraries. The ordinary ChaCha20-Poly1305 it builds on is RFC 8439.

Is it nonce-misuse resistant?

Not at all, since a repeated nonce still breaks it, just as in the standard cipher. The larger nonce only makes accidental repeats very unlikely. For misuse resistance, use a mode such as AES-SIV.

Why is the final state not added back in HChaCha20?

The draft defines HChaCha20 that way, following HSalsa20 in the XSalsa20 paper. The output words are the constants and the nonce positions, which the security argument treats as public inputs.

References

1. Arciszewski, S. “XChaCha: eXtended-nonce ChaCha and AEAD_XChaCha20_Poly1305.” Internet-Draft draft-irtf-cfrg-xchacha-03, January 2020. Available at: https://datatracker.ietf.org/doc/draft-irtf-cfrg-xchacha/

2. Nir, Y. and Langley, A. “ChaCha20 and Poly1305 for IETF Protocols.” RFC 8439, 2018. Available at: https://www.rfc-editor.org/rfc/rfc8439

3. Bernstein, D.J. “Extending the Salsa20 Nonce.” Workshop Record of SASC 2011.

4. Google. “Project Wycheproof: XChaCha20-Poly1305 test vectors.” Available at: https://github.com/C2SP/wycheproof

5. Donenfeld, J. “WireGuard: Protocol and Cryptography.” Available at: https://www.wireguard.com/protocol/

6. Libsodium documentation. “XChaCha20-Poly1305 construction.” Available at: https://doc.libsodium.org/secret-key_cryptography/aead/chacha20-poly1305/xchacha20-poly1305_construction