Poly1305 and the Arithmetic of a One-Time Key

Poly1305 computes a tag from a message and a 256-bit key by evaluating a polynomial modulo $2^{130} - 5$. The message is split into 16-byte chunks, each chunk is interpreted as a little-endian integer with an extra high bit appended, and the result is accumulated as $\sum m_i r^i$ in the field. The final tag is that value plus a secret $s$ modulo $2^{128}$.

The design is unusual in two ways. It uses a prime just below a power of two, which makes reduction cheap on general-purpose hardware. And it is a one-time MAC: the security argument collapses completely if the same $r$ is used for two messages. That second property is not a minor caveat; it is the reason Poly1305 is almost always paired with a stream cipher that supplies a fresh key per message.

The prime and why it is shaped that way

The modulus $p = 2^{130} - 5$ is prime. Its binary form is a one followed by 130 zeros minus five, which means that $2^{130} \equiv 5 \pmod p$. Any accumulator that exceeds 130 bits can be reduced by taking the high part, multiplying by 5, and adding it back to the low 130 bits. The reduction is a shift, a multiply by a small constant, and an add, with no division and no table.

The field is 130 bits wide, which is wider than the 128-bit tag that is finally produced. That extra two bits of headroom matters for the security bound. The polynomial evaluation produces a value in a field of size roughly $2^{130}$, and the tag is the low 128 bits of that value plus $s$. The two-bit gap means that for any pair of distinct messages, the number of keys that cause a collision is bounded by the degree of the polynomial divided by the field size, and the division by $2^{130}$ rather than $2^{128}$ keeps the bound below $2^{-128}$ for messages of reasonable block count.

The message encoding adds a high bit to each chunk. Each 16-byte block is read as a little-endian integer and then has $2^{128}$ added to it. This ensures that no block is zero, so a message with trailing zero blocks cannot be confused with a shorter message. It also means the polynomial has degree equal to the number of blocks, and a message of $n$ blocks contributes a term of degree $n$ to the difference polynomial between two messages.

The clamp

The key is 32 bytes: 16 bytes of $r$ followed by 16 bytes of $s$. The $r$ value is clamped before use by clearing four bits and setting two:

/* r is the first 16 bytes of the key, little-endian */
r[3] &= 15;
r[7] &= 15;
r[11] &= 15;
r[15] &= 15;
r[4] &= 252;
r[8] &= 252;
r[12] &= 252;

The clamp clears 22 bits in total: four bits from each of bytes 3, 7, 11, and 15, and two bits from each of bytes 4, 8, and 12. What remains is a 106-bit multiplier, which is why the forgery bound in the original analysis is expressed against $2^{106}$ rather than $2^{128}$. The purpose is arithmetic: implementations hold the accumulator in five 26-bit limbs on a 64-bit machine, and the clamp guarantees that a limb product plus the incoming accumulator fits in a register without overflow. The clamp also removes a class of degenerate keys, since it forces enough bits to be fixed that $r$ cannot take every value in the field. It is not a tunable parameter; it is part of the definition, and an implementation that skips it produces tags that other implementations reject.

The clamp also means the effective key space is smaller than 128 bits. That is acceptable because the security bound is derived from the field size and the degree of the difference polynomial, not from the entropy of $r$ alone. The bound in the original analysis is of the order of the message block count divided by $2^{106}$, so a message of a few thousand blocks still leaves the forgery probability far below any practical threshold, while an extremely long message under one key erodes the guarantee.

Why one use only

Suppose the same $r$ is used for two messages $M$ and $M’$, with tags $t$ and $t’$. The tags are

$$t = \left(\sum_i m_i r^i \bmod p\right) + s \bmod 2^{128}, \qquad t’ = \left(\sum_i m’_i r^i \bmod p\right) + s \bmod 2^{128}$$

Subtracting eliminates $s$:

$$t - t’ \equiv \sum_i (m_i - m’_i) r^i \pmod p$$

The attacker knows $t - t’$ modulo $2^{128}$ but not modulo $p$, because the subtraction happened after the modular reduction and the truncation to 128 bits. That gap is what the two extra bits of field width buy. Each candidate value modulo $p$ consistent with the known residue modulo $2^{128}$ yields at most as many roots as the degree of the difference polynomial, so a single pair over short messages narrows $r$ to a small set that can be enumerated, and a few pairs pin it down. Once $r$ is known, $s$ follows from any tag, and the attacker can forge for arbitrary messages.

The practical attack is not a search over $2^{130}$ values. It is a polynomial root-finding problem: the difference polynomial has degree equal to the longer message’s block count, and its roots modulo $p$ can be found with standard algorithms in time polynomial in the degree. Two messages of a few blocks each give a low-degree polynomial whose roots are easy to enumerate, and the true $r$ is among them. The attacker verifies candidates against a third tag and recovers the key.

This is why the construction is called one-time. A nonce-reuse bug in a protocol that uses Poly1305 directly, rather than through an authenticated cipher that derives the key per nonce, is a total break, not a degradation. The tag does not become weaker; the key becomes recoverable.

Where the key comes from

In practice Poly1305 is not used with a random independent key per message chosen by a key distribution system. It is used inside ChaCha20-Poly1305, where the Poly1305 key is the first 32 bytes of the ChaCha20 keystream for a given nonce, and the message is encrypted with the rest of that keystream. The nonce is 96 bits and must be unique per key. Reusing a nonce in that construction both repeats the keystream and repeats the Poly1305 key, which is a double failure.

RFC 8439 specifies the AEAD construction: the associated data is padded to a 16-byte boundary, the ciphertext is padded likewise, and both are authenticated along with their lengths encoded as 64-bit little-endian values. The length encoding is what prevents a message and its associated data from being reinterpreted as a different split of the same bytes. Without it, moving bytes across the boundary between associated data and ciphertext would preserve the tag.

The AEAD construction also fixes the tag to 16 bytes. Truncation is not part of the standard, and implementations that expose a shorter tag are outside the specification. The 128-bit tag is the low 128 bits of the polynomial evaluation plus $s$, so it is a full-width value with no structural weakness at the top.

Performance shape

The arithmetic is designed for 64-bit registers. The accumulator is held in five 26-bit limbs, and the multiply-accumulate step for one block is the five limb-by-limb products of the accumulator against $r$ plus the corresponding products against the message block, with carries folded in. The reduction after each block uses the identity $2^{130} \equiv 5$ to fold the high bits back, which is a shift and a multiply by five, both cheap. On a 64-bit machine the per-block cost is a small constant number of instructions and no memory traffic beyond the input, which is why Poly1305 is competitive with hash-based MACs on processors without a dedicated hash engine.

The message must be processed sequentially because each block multiplies the accumulated value by $r$ and adds the next block. There is no parallelism within a single tag. Implementations that need throughput on long messages can interleave the MAC with the cipher, since ChaCha20’s keystream generation is parallel across blocks and the MAC consumes blocks in order.

The final partial block, if any, is padded with a 1 byte followed by zeros before being added, and that padding is part of the authenticated data. A message whose length is a multiple of 16 has no partial block. The distinction matters because an implementation that pads with zeros only, without the 1 byte, will accept a message and its zero-extended variant as having the same tag, which is a length-extension-style ambiguity in a construction that otherwise has none.

What the tag does and does not bind

Poly1305 authenticates a byte string under a key. In the AEAD construction the byte string includes the associated data, the ciphertext, and both lengths, so the tag binds the split as well as the content. It does not bind a nonce, a sequence number, or a direction. Those must be supplied by the protocol, either by including them in the associated data or by deriving the key from them. A record that is valid under nonce $N$ is not automatically valid in a different position in the stream, and an implementation that accepts a replayed record because the tag checks out has authenticated the bytes and nothing else.

The same separation between authenticating bytes and acting on their meaning appears in the HMAC construction, and the length ambiguity that padding can introduce is the same one CMAC handles with its two subkeys. Poly1305’s particular contribution is the arithmetic: a prime close to a power of two, a clamped multiplier, and a proof that holds only for a single use.