The Poly1305 Algorithm

The Poly1305 Algorithm

Introduction

A message authentication code, or MAC, is a short tag that proves that a message came from someone who knows a secret key and that nobody changed it. Most MACs build on a hash function or a block cipher. Poly1305 takes a different path. It is built on simple arithmetic, a polynomial evaluated modulo a prime number.

Daniel Bernstein designed Poly1305 to be very fast and easy to implement without side channels. Its key is a one-time key. It may authenticate one message and no more. That sounds like a heavy limit, but it fits well in practice, because the key can come from a stream cipher such as ChaCha20, which makes a fresh key for every message. This is how ChaCha20-Poly1305 works. This guide covers Poly1305 on its own.

Table of Contents

• History and Standards
• The Idea
• The Key and Clamping
• Message Blocks
• The Accumulator and the Tag
• Why the Key Is One-Time
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

Bernstein published the design in 2005, in a paper titled “The Poly1305-AES message-authentication code”. In that version, the MAC needs a 128-bit AES key, a second 128-bit key, and a non-secret nonce. AES encrypts the nonce, and the result is a unique, secret value for each message. As the paper says, there is nothing special about AES here. Any keyed function that gives a unique 16-byte string per nonce will do.

The IETF later used Poly1305 together with the ChaCha20 stream cipher in RFC 8439, “ChaCha20 and Poly1305 for IETF Protocols”. There, ChaCha20 makes the one-time key for each message. The pair is used in TLS, where TLS 1.3 lists TLS_CHACHA20_POLY1305_SHA256 as a cipher suite, and in the WireGuard VPN. Standalone Poly1305 is the same function that appears inside those constructions. The ChaCha20-Poly1305 guide and the XChaCha20-Poly1305 guide show it in use.

The Idea

Poly1305 is a polynomial MAC. The message is cut into blocks, and each block becomes a number. The numbers are the coefficients of a polynomial. The key contains a secret value r, and the tag is the polynomial evaluated at r, modulo a prime, plus a second secret value s:

tag = ( c1 * r^q + c2 * r^(q-1) + ... + cq * r )  mod (2^130 - 5)  +  s   mod 2^128

The formula is evaluated with Horner’s method, which a later section shows. The prime 2^130 - 5 is just above 2 to the 128. A 16-byte block, which is a number below 2^128, fits well below the prime, and the arithmetic is fast on both 32-bit and 64-bit processors. The tag has 128 bits, because s is added modulo 2^128.

The Key and Clamping

The 32-byte key splits into two halves. The first 16 bytes are r, and the last 16 bytes are s. Both are read as little-endian numbers.

Before r is used, 22 of its bits are forced to zero. This is called clamping. The standard says that the top four bits of bytes 3, 7, 11, and 15 must be clear, and the bottom two bits of bytes 4, 8, and 12 must be clear. In one step, this is an AND with a mask:

r = r and 0x0ffffffc0ffffffc0ffffffc0fffffff

Clamping does not weaken the key much, because r still has about 106 free bits. It exists for the implementer. With these bits clear, the partial products in a multiplication on 32-bit limbs stay small, so the carries never overflow a machine word. This is what lets Poly1305 run quickly without special instructions, and in constant time.

Message Blocks

Poly1305 cuts the message into blocks of 16 bytes. The last block may be shorter. Each block is read as a little-endian number, and then a byte 0x01 is appended to the block, just after its last byte:

• A full block becomes a 129-bit number, with a one at bit 128.
• A short block of k bytes becomes a number with a one at bit 8k.

The appended byte has a job. It makes blocks of different lengths different numbers, so that a message and the same message with zero bytes added give different tags. Without it, the last block 7075 and the block 707500 would be the same number.

The Accumulator and the Tag

Poly1305 keeps a number called the accumulator, acc, which starts at zero. For each block n, in order:

acc = ( acc + n ) * r  mod (2^130 - 5)

After the last block, the tag is:

tag = ( acc + s ) mod 2^128

written as 16 little-endian bytes. This last reduction is by 2^128, not by the prime. The sum acc + s can be larger than 2^128, and its high bits are simply dropped. Each block is first added, and then everything is multiplied by r. This is Horner’s method for evaluating a polynomial, and it needs only one multiplication per block. The empty message has no blocks, so its accumulator stays zero, and its tag is just s.

Why the Key Is One-Time

The security of Poly1305 holds only if the pair (r, s) is used for one message. The value s hides the accumulator. If s were not there, the tag would be a polynomial in r that an attacker could solve. With s, each tag looks random.

If a key is used twice, s cancels out. Take two messages of one block each, n1 and n2, under the same key. Their tags are n1*r + s and n2*r + s, up to the reductions. Subtracting them leaves (n1 - n2) * r. Dividing by n1 - n2 gives r, up to a handful of possible values, because the tags lose the top two bits of the accumulator. Clamping then tells the candidates apart, because only the true r has all of its required bits clear. Once r is known, s follows from one of the tags, and the attacker can compute valid tags for any message under that key.

The worked example below shows this attack with real numbers. This is why ChaCha20-Poly1305 derives a new key for every nonce, and why a repeated nonce breaks it.

Interactive Visualizer

The visualizer above runs this exact algorithm. Enter a one-time key as 64 hex digits and type a message of up to 127 bytes. Then click Compute tag. The log shows how r is clamped, how s is read, and then for each block, the number made from the block, the sum with the accumulator, and the new accumulator after the multiplication. The last row adds s and shows the tag. The default is the example from RFC 8439. When it ends, the page tells you how many tag bits change when one bit of your message is flipped.

A Worked Example

This is the example from Section 2.5.2 of RFC 8439. Byte strings are shown in byte order, from the first byte to the last. Numbers are shown as ordinary hexadecimal integers, with the most significant digit first, as the RFC prints them. A block read as a little-endian number therefore shows its bytes in reverse order. The key, written as 32 bytes, is:

85d6be7857556d337f4452fe42d506a80103808afb0db2fd4abff6af4149f51b

The key. The first half, 85d6be7857556d337f4452fe42d506a8, is r before clamping, which is the number a806d542fe52447f336d555778bed685. The mask removes the bits a0000002f00000033000000370000000, so the clamped r is 806d5400e52447c036d555408bed685. The second half, 0103808afb0db2fd4abff6af4149f51b, is s, which is the number 1bf54941aff6bf4afdb20dfb8a800301.

The message. Cryptographic Forum Research Group has 34 bytes, which makes three blocks: two full blocks and one of two bytes. All numbers below are in hexadecimal, and the prime is 3fffffffffffffffffffffffffffffffb.

Block 1. The bytes are 43727970746f6772617068696320466f. Read as a little-endian number, they are 6f4620636968706172676f7470797243. The appended byte 01 becomes the top byte, which gives 016f4620636968706172676f7470797243. The accumulator is zero, so the sum is the same. Multiplying by r gives b83fe991ca66800489155dcd69e8426ba2779453994ac90ed284034da565ecf, and reducing modulo the prime gives acc = 2c88c77849d64ae9147ddeb88e69c83fc.

Block 2. The bytes are 72756d2052657365617263682047726f. The number is 6f7247206863726165736552206d7572, and with the byte 01 it is 016f7247206863726165736552206d7572. The sum with the accumulator is 437febea505c820f2ad5150db0709f96e. The product with r is 21dcc992d0c659ba4036f65bb7f88562ae59b32c2b3b8f7efc8b00f78e548a26, and the reduced accumulator is 2d8adaf23b0337fa7cccfb4ea344b30de.

Block 3. The last block has two bytes, 7570, so the appended 01 lands at bit 16. The number is 7075, and with the byte 01 it is 017075. The sum is 2d8adaf23b0337fa7cccfb4ea344ca153. The product is 16d8e08a0f3fe1de4fe4a15486aca7a270a29f1e6c849221e4a6798b8e45321f, and the reduced accumulator is 28d31b7caff946c77c8844335369d03a7.

The tag. Adding s gives 2a927010caf8b2bc2c6365130c11d06a8. Cutting it to 128 bits gives a927010caf8b2bc2c6365130c11d06a8, and written as little-endian bytes, the tag is:

a8061dc1305136c6c22b8baf0c0127a9

Every number above is printed in the RFC, and the script that wrote this page checks the block numbers against the RFC text. Changing the last letter of the message to q gives the tag b28bf37f39a58b33c6a7cf011b41fcaf, which differs in 62 of the 128 bits. The empty message has the tag 0103808afb0db2fd4abff6af4149f51b, which is s itself.

Breaking a reused key. Suppose the same key authenticates two one-block messages, pay Alice 10 USD and pay Bobby 90 USD. The tags, as numbers, are e539fa06267362f1cf2823d734afaadb and 7e1d1dc12b9ccafacee89d2c113653db. Subtracting them modulo 2^128 and dividing by the difference of the two block numbers gives 9 possible values of r, one for each possible loss of the top bits. Only one of the nine has all of its clamped bits clear. It is 806d5400e52447c036d555408bed685, which is exactly the clamped r of the key. Subtracting n1 * r from the first tag then gives s = 1bf54941aff6bf4afdb20dfb8a800301. The key is fully recovered from two tags and two messages.

Python Implementation

This is a complete Poly1305. The function accumulators keeps the accumulator after each block, so you can print the steps shown above. The function verify compares tags in constant time, as a receiver should.

# poly1305.py
#
# Poly1305, the one-time message authentication code designed by Daniel
# Bernstein (RFC 8439). A 32-byte key splits into two numbers, r and s. The
# message is cut into 16-byte blocks, and each block becomes a number just above
# 2^128 times its length. The tag is a polynomial in r evaluated mod 2^130 - 5,
# plus s, cut to 128 bits. The key must be used for ONE message only.
# Python integers are not constant-time. Production code uses limb arithmetic.

P = (1 << 130) - 5

# clamping: these bits of r are forced to zero, so that the sums in the
# multiplication never carry too far
CLAMP = 0x0FFFFFFC0FFFFFFC0FFFFFFC0FFFFFFF


def split_key(key):
    """r is the first 16 bytes (clamped), s is the last 16 bytes. Both are little-endian numbers."""
    if len(key) != 32:
        raise ValueError("a Poly1305 key is 32 bytes")
    return int.from_bytes(key[:16], "little") & CLAMP, int.from_bytes(key[16:], "little")


def block_number(block):
    """A block of 1 to 16 bytes, with a byte 0x01 appended, read as a little-endian number."""
    return int.from_bytes(block + b"\x01", "little")


def accumulators(key, message):
    """The accumulator after each block."""
    r, _ = split_key(key)
    acc = 0
    out = []
    for i in range(0, len(message), 16):
        acc = (acc + block_number(message[i:i + 16])) * r % P
        out.append(acc)
    return out


def poly1305(key, message):
    _, s = split_key(key)
    accs = accumulators(key, message)
    acc = accs[-1] if accs else 0
    return ((acc + s) % (1 << 128)).to_bytes(16, "little")


def verify(key, message, tag):
    """Compare in constant time, as a receiver should."""
    expected = poly1305(key, message)
    difference = 0
    for a, b in zip(expected, tag):
        difference |= a ^ b
    return len(tag) == 16 and difference == 0


if __name__ == "__main__":
    key = bytes.fromhex("85d6be7857556d337f4452fe42d506a80103808afb0db2fd4abff6af4149f51b")
    message = b"Cryptographic Forum Research Group"
    tag = poly1305(key, message)
    print("Tag:      " + tag.hex())
    print("Verified: " + str(verify(key, message, tag)))
    print("Changed:  " + str(verify(key, message + b"!", tag)))

Running it produces this output:

Tag:      a8061dc1305136c6c22b8baf0c0127a9
Verified: True
Changed:  False

I checked this code against several independent sources before writing it up. It reproduces every intermediate value of the example in RFC 8439, Section 2.5.2: r, s, the three blocks, all three accumulators, the sum with s, and the tag. It also reproduces all 123 test vectors in Botan’s test file, which include the vectors of RFC 8439, vectors from poly1305-donna and libsodium, and long inputs designed to expose carry bugs, up to 2,091 bytes.

Security Status

If the key is used once, Poly1305 is secure. RFC 8439 says that forged messages are rejected with a probability of 1 - n/2^102 for a message of 16n bytes, even after 2^64 legitimate messages. In other words, a forgery succeeds with a probability of at most about n/2^102. For a one-block message, an attacker’s chance to guess a valid tag is therefore about one in 2^102. Proofs are in Bernstein’s paper.

The practical risks are about use, not the math. The first is key reuse, which the worked example shows. A protocol that derives the key from a nonce must never repeat a nonce. In ChaCha20-Poly1305, the one-time key is the start of the ChaCha20 output for the nonce, so a repeated nonce repeats the Poly1305 key. The second is side channels. An implementation with a variable-time multiplication or modular reduction leaks information about r, so real code uses constant-time arithmetic on limbs. The Python code in this guide does not. The third is truncation. A shorter tag is easier to guess, so use all 16 bytes.

FAQ

Is Poly1305 a hash function?

No, because it needs a secret key and it is secure only when that key is used once. A hash has no key. A general MAC such as HMAC is secure when one key is used for many messages, which is a stronger requirement.

Why is it called Poly1305?

Because it evaluates a polynomial, and because the prime modulus is 2^130 - 5. The number 1305 comes from the 130 bits and the 5.

Can I use Poly1305 as a general MAC, like HMAC?

Only with a fresh key for each message. HMAC and CMAC work with one key for many messages, and Poly1305 does not. In practice, Poly1305 appears inside an AEAD, such as ChaCha20-Poly1305, where the cipher makes the key.

What happens when the key is reused?

An attacker who sees two tags under one key can compute r, then s, and then forge tags for any message. The worked example shows this with numbers.

Why does clamping not weaken the key?

Clamping clears 22 of the 128 bits of r, which leaves about 106 bits. That is enough, because the forgery bound of n/2^102 comes from the clamped value. The cleared bits make fast and safe implementations possible. The clamp is also part of the definition. An implementation that skips it computes different tags, so every implementation must apply it.

What are the most common implementation mistakes?

There are five common ones. The first is to forget the appended 01 byte, which makes 7075 and 707500 equal. The second is to read the key or the blocks as big-endian numbers. The third is to skip the clamp. The fourth is a variable-time multiplication or reduction. The fifth is to reuse a key, or to cut the tag short.

References

1. Bernstein, Daniel J. “The Poly1305-AES Message-Authentication Code.” Fast Software Encryption (FSE) 2005, Lecture Notes in Computer Science 3557, Springer.

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. Botan project. “Poly1305 test vectors.” Available at: https://github.com/randombit/botan

4. Wikipedia. “Poly1305.” Available at: https://en.wikipedia.org/wiki/Poly1305