Poly1305

Poly1305 is a universal hash family designed by Daniel J. Bernstein for use in cryptography. ^[1]

As with any universal hash family, Poly1305 can be used as a one-time message authentication code to authenticate a single message ^[2] or as a one-time pad used to conceal the content of a single message, in both cases using a key shared between sender and recipient.

Originally Poly1305 was proposed as part of Poly1305-AES, ^[3] a Carter–Wegman authenticator ^{[4] [5] [1]} that combines the Poly1305 hash with AES-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 using XSalsa20 in the NaCl crypto_secretbox_xsalsa20poly1305 authenticated cipher, ^[6] and then using ChaCha in the ChaCha20-Poly1305 authenticated cipher ^{[7] [8] [1]} deployed in TLS on the internet. ^[9]

Description

Definition of 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}$.

Use as a one-time authenticator

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.

Use in Poly1305-AES as a Carter–Wegman authenticator

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.

Use in NaCl and ChaCha20-Poly1305

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]

Security

The security of Poly1305 and its derivatives against forgery follows from its bounded difference probability as a universal 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[\operatorname {Poly1305} _{r}(m_{1})-\operatorname {Poly1305} _{r}(m_{2})\equiv d{\pmod {2^{128}}}]\leq {\frac {8\lceil L/16\rceil }{2^{106}}},}$$

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

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

Of one-time authenticator

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.

Of NaCl and ChaCha20-Poly1305

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}}}.}$$

Of Poly1305-AES

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]

Speed

Poly1305-AES can be computed at high speed in various CPUs: for an n-byte message, no more than 3.1n + 780 Athlon cycles are needed, ^[3] for example. The author has released optimized source code for Athlon, Pentium Pro/II/III/M, PowerPC, and UltraSPARC, in addition to non-optimized reference implementations in C and C++ as public domain software. ^[12]

Implementations

Below is a list of cryptography libraries that support Poly1305:

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

See also

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

References

1. Aumasson, Jean-Philippe (2018). "Chapter 7: Keyed Hashing". Serious Cryptography: A Practical Introduction to Modern Encryption. No Starch Press. pp. 136–138. ISBN   978-1-59327-826-7.
2. Bernstein, Daniel J. (2008-05-01). "Protecting communications against forgery". In Buhler, Joe; Stevenhagen, Peter (eds.). Algorithmic number theory: lattices, number fields, curves and cryptography. Mathematical Sciences Research Institute Publications. Vol. 44. Cambridge University Press. pp. 535–549. ISBN   978-0521808545 . Retrieved 2022-10-14.
3. Bernstein, Daniel J. (2005-03-29). "The Poly1305-AES message-authentication code". In Gilbert, Henri; Handschuh, Helena (eds.). Fast Software Encryption: 12th international workshop. FSE 2005. Lecture Notes in Computer Science. Paris, France: Springer. doi: 10.1007/11502760_3 . ISBN   3-540-26541-4 . Retrieved 2022-10-14.
4. Wegman, Mark N.; Carter, J. Lawrence (1981). "New Hash Functions and Their Use in Authentication and Set Equality". Journal of Computer and System Sciences. 22 (3): 265–279. doi:10.1016/0022-0000(81)90033-7.
5. Boneh, Dan; Shoup, Victor (January 2020). A Graduate Course in Applied Cryptography (PDF) (Version 0.5 ed.). §7.4 The Carter-Wegman MAC, pp. 262–269. Retrieved 2022-10-14.
6. Bernstein, Daniel J. (2009-03-10). Cryptography in NaCl (Technical report). Document ID: 1ae6a0ecef3073622426b3ee56260d34.
7. Nir, Y.; Langley, A. (May 2015). ChaCha20 and Poly1305 for IETF Protocols. doi: 10.17487/RFC7539 . RFC 7539.
8. Nir, Y.; Langley, A. (June 2018). ChaCha20 and Poly1305 for IETF Protocols. doi: 10.17487/RFC8439 . RFC 8439.
9. Langley, A.; Chang, W.; Mavrogiannopoulos, N.; Strombergson, J.; Josefsson, S. (June 2016). ChaCha20-Poly1305 Cipher Suites for Transport Layer Security (TLS). doi: 10.17487/RFC7905 . RFC 7905.
10. Halevi, Shai; Krawczyk, Hugo. "MMH: Software Message Authentication in the Gbit/Second Rates". In Biham, Eli (ed.). Fast Software Encryption. FSE 1997. Lecture Notes in Computer Science. Springer. doi: 10.1007/BFb0052345 . ISBN   978-3-540-63247-4.
11. Bernstein, Daniel J. (2005-02-27). "Stronger security bounds for Wegman-Carter-Shoup authenticators". In Cramer, Ronald (ed.). Advances in Cryptology—EUROCRYPT 2005, 24th annual international conference on the theory and applications of cryptographic techniques. EUROCRYPT 2005. Lecture Notes in Computer Science. Aarhus, Denmark: Springer. doi: 10.1007/11426639_10 . ISBN   3-540-25910-4.
12. A state-of-the-art message-authentication code on cr.yp.to

External links

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