Poly1305 is auniversal hash family designed byDaniel J. Bernstein in 2002 for use incryptography.^[1][2]

As with any universal hash family, Poly1305 can be used as a one-timemessage authentication code to authenticate a single message using a secret key shared between sender and recipient,^[3]similar to the way that aone-time pad can be used to conceal the content of a single message using a secret key shared between sender and recipient.

Originally Poly1305 was proposed as part of Poly1305-AES,^[2] a Carter–Wegman authenticator^[4][5][1]that combines the Poly1305 hash withAES-128 to authenticate many messages using a single short key and distinct message numbers.Poly1305 was later applied with a single-use key generated for each message usingXSalsa20 in theNaCl crypto_secretbox_xsalsa20poly1305 authenticated cipher,^[6]and then usingChaCha in theChaCha20-Poly1305 authenticated cipher^[7][8][1]deployed inTLS on the internet.^[9]

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

1. Interprets${\displaystyle r}$ as alittle-endian 16-byte integer.
2. Breaks the message${\displaystyle m=(m[0],m[1],m[2],\dots ,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(\mathrm{mod}16)}$, then:

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

The secret key${\displaystyle r=(r[0],r[1],r[2],\dots ,r[15])}$ is restricted to have the bytes${\displaystyle r[3],r[7],r[11],r[15]\in \{0,1,2,\dots ,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,\dots ,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:=({\mathrm{Poly1305}}_r(m)+s){mod2}^{128}}$$

is called theauthenticator 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 analleged authenticated message${\displaystyle (a^{\prime },m^{\prime })}$ (which may have been modified in transmit by an adversary), they can verify its authenticity by testing whether

$${\displaystyle a^{\prime }\stackrel{?}{=}({\mathrm{Poly1305}}_r(m^{\prime })+s){mod2}^{128}.}$$Without knowledge of${\displaystyle (r,s)}$, the adversary has probability${\displaystyle 8\lceil L/16\rceil /2^{106}}$ of finding any${\displaystyle (a^{\prime },m^{\prime })\ne (a,m)}$ that will pass verification.

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

for${\displaystyle m_1\ne m_2}$, they can subtract

$${\displaystyle a_1-a_2\equiv {\mathrm{Poly1305}}_r(m_1)-{\mathrm{Poly1305}}_r(m_2)(\mathrm{mod}{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^[2] 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 theith 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 usesAES-128 to generate${\displaystyle p_i:={\mathrm{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:=({\mathrm{Poly1305}}_r(m_i)+{\mathrm{AES}}_k(i)){mod2}^{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 candistinguish${\displaystyle {\mathrm{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 {\mathrm{AES}}_k(i)}$, as with the one-time authenticator, and use that to forge messages.

TheNaCl crypto_secretbox_xsalsa20poly1305 authenticated cipher uses a message number${\displaystyle i}$ with theXSalsa20 stream cipher to generate a per-messagekey 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 withChaCha instead ofXSalsa20.^[8]XChaCha20-Poly1305 using XChaCha20 instead of XSalsa20 has also been described.^[10]

The security of Poly1305 and its derivatives against forgery follows from itsbounded difference probability as auniversal hash family:If${\displaystyle m_1}$ and${\displaystyle m_2}$ are messages of up to${\displaystyle L}$ bytes each, and${\displaystyle d}$ is any 16-byte string interpreted as a little-endian integer, then

$${\displaystyle Pr[{\mathrm{Poly1305}}_r(m_1)-{\mathrm{Poly1305}}_r(m_2)\equiv d(\mathrm{mod}{2}^{128})]\le \frac{8\lceil L/16\rceil }{2^{106}},}$$

where${\displaystyle r}$ is a uniform random Poly1305 key.^{[2]: Theorem 3.3, p. 8}

This property is sometimes called${\displaystyle ϵ}$-almost-Δ-universality over${\displaystyle \mathbb{Z}/2^{128}\mathbb{Z}}$, or${\displaystyle ϵ}$-AΔU,^[11]where${\displaystyle ϵ=8\lceil L/16\rceil /2^{106}}$ in this case.

With a one-time authenticator${\displaystyle a=({\mathrm{Poly1305}}_r(m)+s){mod2}^{128}}$, the adversary's success probability for any forgery attempt${\displaystyle (a^{\prime },m^{\prime })}$ on a message${\displaystyle m^{\prime }}$ of up to${\displaystyle L}$ bytes is:

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

ForNaCl crypto_secretbox_xsalsa20poly1305 andChaCha20-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 aspseudorandom 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.^[12]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 apseudorandom permutation, then the probability the adversary succeeds at any one of the${\displaystyle D}$ forgeries is at most:^[2]

$${\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)^[2]

Poly1305-AES can be computed at high speed in various CPUs: for ann-byte message, no more than 3.1n + 780 Athlon cycles are needed,^[2] for example.The author has released optimizedsource code forAthlon,Pentium Pro/II/III/M,PowerPC, andUltraSPARC, in addition to non-optimizedreference implementations inC andC++ aspublic domain software.^[13]

Below is a list of cryptography libraries that support Poly1305:

• Botan
• Bouncy Castle
• Crypto++
• Libgcrypt
• libsodium
• Nettle
• OpenSSL
• LibreSSL
• wolfCrypt
• GnuTLS
• mbed TLS
• MatrixSSL

• ChaCha20-Poly1305 – an AEAD scheme combining the stream cipher ChaCha20 with a variant of Poly1305

• Poly1305-AES reference and optimized implementation by author D. J. Bernstein
• Fast Poly1305 implementation in C on github.com
• NaClone-time authenticator andauthenticated cipher using Poly1305

• Advanced Encryption Standard
• Internet Standards
• Message authentication codes
• Public-domain software with source code

• Articles with short description
• Short description is different from Wikidata