Poly1305

Poly1305 takes a 16-byte secret key ${\displaystyle r}$ and an ${\displaystyle L}$-byte message ${\displaystyle m}$ and returns a 16-byte hash ${\displaystyle \operatorname {Poly1305} _{r}(m)}$. To do this, Poly1305:[3][1]

1. Interprets ${\displaystyle r}$ as a little-endian 16-byte integer.
2. Breaks the message ${\displaystyle m=(m[0],m[1],m[2],\dotsc ,m[L-1])}$ into consecutive 16-byte chunks.
3. Interprets the 16-byte chunks as 17-byte little-endian integers by appending a 1 byte to every 16-byte chunk, to be used as coefficients of a polynomial.
4. Evaluates the polynomial at the point ${\displaystyle r}$ modulo the prime ${\displaystyle 2^{130}-5}$.
5. Reduces the result modulo ${\displaystyle 2^{128}}$ encoded in little-endian return a 16-byte hash.

The coefficients ${\displaystyle c_{i}}$ of the polynomial ${\displaystyle c_{1}r^{q}+c_{2}r^{q-1}+\cdots +c_{q}r}$, where ${\displaystyle q=\lceil L/16\rceil }$, are:

$${\displaystyle c_{i}=m[16i-16]+2^{8}m[16i-15]+2^{16}m[16i-14]+\cdots +2^{120}m[16i-1]+2^{128},}$$

with the exception that, if ${\displaystyle L\not \equiv 0{\pmod {16}}}$, then:

$${\displaystyle c_{q}=m[16q-16]+2^{8}m[16q-15]+\cdots +2^{8(L{\bmod {1}}6)-8}m[L-1]+2^{8(L{\bmod {1}}6)}.}$$

The secret key ${\displaystyle r=(r[0],r[1],r[2],\dotsc ,r[15])}$ is restricted to have the bytes ${\displaystyle r[3],r[7],r[11],r[15]\in \{0,1,2,\dotsc ,15\}}$, i.e., to have their top four bits clear; and to have the bytes ${\displaystyle r[4],r[8],r[12]\in \{0,4,8,\dotsc ,252\}}$, i.e., to have their bottom two bits clear. Thus there are ${\displaystyle 2^{106}}$ distinct possible values of ${\displaystyle r}$.

If ${\displaystyle s}$ is a secret 16-byte string interpreted as a little-endian integer, then

$${\displaystyle a:={\bigl (}\operatorname {Poly1305} _{r}(m)+s{\bigr )}{\bmod {2}}^{128}}$$

is called the authenticator for the message ${\displaystyle m}$. If a sender and recipient share the 32-byte secret key ${\displaystyle (r,s)}$ in advance, chosen uniformly at random, then the sender can transmit an authenticated message ${\displaystyle (a,m)}$. When the recipient receives an alleged authenticated message ${\displaystyle (a',m')}$ (which may have been modified in transmit by an adversary), they can verify its authenticity by testing whether

$${\displaystyle a'\mathrel {\stackrel {?}{=}} {\bigl (}\operatorname {Poly1305} _{r}(m')+s{\bigr )}{\bmod {2}}^{128}.}$$

Without knowledge of ${\displaystyle (r,s)}$, the adversary has probability ${\displaystyle 8\lceil L/16\rceil /2^{106}}$ of finding any ${\displaystyle (a',m')\neq (a,m)}$ that will pass verification.

However, the same key ${\displaystyle (r,s)}$ must not be reused for two messages. If the adversary learns

$${\displaystyle {\begin{aligned}a_{1}&={\bigl (}\operatorname {Poly1305} _{r}(m_{1})+s{\bigr )}{\bmod {2}}^{128},\\a_{2}&={\bigl (}\operatorname {Poly1305} _{r}(m_{2})+s{\bigr )}{\bmod {2}}^{128},\end{aligned}}}$$

for ${\displaystyle m_{1}\neq m_{2}}$, they can subtract

$${\displaystyle a_{1}-a_{2}\equiv \operatorname {Poly1305} _{r}(m_{1})-\operatorname {Poly1305} _{r}(m_{2}){\pmod {2^{128}}}}$$

and find a root of the resulting polynomial to recover a small list of candidates for the secret evaluation point ${\displaystyle r}$, and from that the secret pad ${\displaystyle s}$. The adversary can then use this to forge additional messages with high probability.

The original Poly1305-AES proposal[3] uses the Carter–Wegman structure[4][5] to authenticate many messages by taking ${\displaystyle a_{i}:=H_{r}(m_{i})+p_{i}}$ to be the authenticator on the ith message ${\displaystyle m_{i}}$, where ${\displaystyle H_{r}}$ is a universal hash family and ${\displaystyle p_{i}}$ is an independent uniform random hash value that serves as a one-time pad to conceal it. Poly1305-AES uses AES-128 to generate ${\displaystyle p_{i}:=\operatorname {AES} _{k}(i)}$, where ${\displaystyle i}$ is encoded as a 16-byte little-endian integer.

Specifically, a Poly1305-AES key is a 32-byte pair ${\displaystyle (r,k)}$ of a 16-byte evaluation point ${\displaystyle r}$, as above, and a 16-byte AES key ${\displaystyle k}$. The Poly1305-AES authenticator on a message ${\displaystyle m_{i}}$ is

$${\displaystyle a_{i}:={\bigl (}\operatorname {Poly1305} _{r}(m_{i})+\operatorname {AES} _{k}(i){\bigr )}{\bmod {2}}^{128},}$$

where 16-byte strings and integers are identified by little-endian encoding. Note that ${\displaystyle r}$ is reused between messages.

Without knowledge of ${\displaystyle (r,k)}$, the adversary has low probability of forging any authenticated messages that the recipient will accept as genuine. Suppose the adversary sees ${\displaystyle C}$ authenticated messages and attempts ${\displaystyle D}$ forgeries, and can distinguish ${\displaystyle \operatorname {AES} _{k}}$ from a uniform random permutation with advantage at most ${\displaystyle \delta }$. (Unless AES is broken, ${\displaystyle \delta }$ is very small.) The adversary's chance of success at a single forgery is at most:

$${\displaystyle \delta +{\frac {(1-C/2^{128})^{-(C+1)/2}\cdot 8D\lceil L/16\rceil }{2^{106}}}.}$$

The message number ${\displaystyle i}$ must never be repeated with the same key ${\displaystyle (r,k)}$. If it is, the adversary can recover a small list of candidates for ${\displaystyle r}$ and ${\displaystyle \operatorname {AES} _{k}(i)}$, as with the one-time authenticator, and use that to forge messages.

The NaCl crypto_secretbox_xsalsa20poly1305 authenticated cipher uses a message number ${\displaystyle i}$ with the XSalsa20 stream cipher to generate a per-message key stream, the first 32 bytes of which are taken as a one-time Poly1305 key ${\displaystyle (r_{i},s_{i})}$ and the rest of which is used for encrypting the message. It then uses Poly1305 as a one-time authenticator for the ciphertext of the message.[6] ChaCha20-Poly1305 does the same but with ChaCha instead of XSalsa20.[8]

With a one-time authenticator ${\displaystyle a={\bigl (}\operatorname {Poly1305} _{r}(m)+s{\bigr )}{\bmod {2}}^{128}}$, the adversary's success probability for any forgery attempt ${\displaystyle (a',m')}$ on a message ${\displaystyle m'}$ of up to ${\displaystyle L}$ bytes is:

$${\displaystyle {\begin{aligned}\Pr[&a'=\operatorname {Poly1305} _{r}(m')+s\mathrel {\mid } a=\operatorname {Poly1305} _{r}(m)+s]\\&=\Pr[a'=\operatorname {Poly1305} _{r}(m')+a-\operatorname {Poly1305} _{r}(m)]\\&=\Pr[\operatorname {Poly1305} _{r}(m')-\operatorname {Poly1305} _{r}(m)=a'-a]\\&\leq 8\lceil L/16\rceil /2^{106}.\end{aligned}}}$$

Here arithmetic inside the ${\displaystyle \Pr[\cdots ]}$ is taken to be in ${\displaystyle \mathbb {Z} /2^{128}\mathbb {Z} }$ for simplicity.

For NaCl crypto_secretbox_xsalsa20poly1305 and ChaCha20-Poly1305, the adversary's success probability at forgery is the same for each message independently as for a one-time authenticator, plus the adversary's distinguishing advantage ${\displaystyle \delta }$ against XSalsa20 or ChaCha as pseudorandom functions used to generate the per-message key. In other words, the probability that the adversary succeeds at a single forgery after ${\displaystyle D}$ attempts of messages up to ${\displaystyle L}$ bytes is at most:

$${\displaystyle \delta +{\frac {8D\lceil L/16\rceil }{2^{106}}}.}$$

The security of Poly1305-AES against forgery follows from the Carter–Wegman–Shoup structure, which instantiates a Carter–Wegman authenticator with a permutation to generate the per-message pad.[11] If an adversary sees ${\displaystyle C}$ authenticated messages and attempts ${\displaystyle D}$ forgeries of messages of up to ${\displaystyle L}$ bytes, and if the adversary has distinguishing advantage at most ${\displaystyle \delta }$ against AES-128 as a pseudorandom permutation, then the probability the adversary succeeds at any one of the ${\displaystyle D}$ forgeries is at most:[3]

$${\displaystyle \delta +{\frac {(1-C/2^{128})^{-(C+1)/2}\cdot 8D\lceil L/16\rceil }{2^{106}}}.}$$

For instance, assuming that messages are packets up to 1024 bytes; that the attacker sees 2⁶⁴ messages authenticated under a Poly1305-AES key; that the attacker attempts a whopping 2⁷⁵ forgeries; and that the attacker cannot break AES with probability above δ; then, with probability at least 0.999999 − δ, all the 2⁷⁵ are rejected

— Bernstein, Daniel J. (2005)[3]