Poly1305

Short description: Universal hash family used for message authentication in cryptography

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

As with any universal hash family, Poly1305 can be used as a one-time message authentication code to authenticate a single message using a secret key shared between sender and recipient, similar to the way that a one-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, a Carter–Wegman authenticator 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, and then using ChaCha in the ChaCha20-Poly1305 authenticated cipher deployed in TLS on the internet.

Description

Definition of Poly1305

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

1. Interprets [math]\displaystyle{ r }[/math] as a little-endian 16-byte integer.
2. Breaks the message [math]\displaystyle{ m = (m[0], m[1], m[2], \dotsc, m[L - 1]) }[/math] 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 [math]\displaystyle{ r }[/math] modulo the prime [math]\displaystyle{ 2^{130} - 5 }[/math].
5. Reduces the result modulo [math]\displaystyle{ 2^{128} }[/math] encoded in little-endian return a 16-byte hash.

The coefficients [math]\displaystyle{ c_i }[/math] of the polynomial [math]\displaystyle{ c_1 r^q + c_2 r^{q - 1} + \cdots + c_q r }[/math], where [math]\displaystyle{ q = \lceil L/16\rceil }[/math], are:

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

with the exception that, if [math]\displaystyle{ L \not\equiv 0 \pmod{16} }[/math], then:

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

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

Use as a one-time authenticator

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

[math]\displaystyle{ a := \bigl(\operatorname{Poly1305}_r(m) + s\bigr) \bmod 2^{128} }[/math]

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

[math]\displaystyle{ a' \mathrel{\stackrel?=} \bigl(\operatorname{Poly1305}_r(m') + s\bigr) \bmod 2^{128}. }[/math] Without knowledge of [math]\displaystyle{ (r, s) }[/math], the adversary has probability [math]\displaystyle{ 8\lceil L/16\rceil/2^{106} }[/math] of finding any [math]\displaystyle{ (a', m') \ne (a, m) }[/math] that will pass verification.

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

[math]\displaystyle{ \begin{align} 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{align} }[/math]

for [math]\displaystyle{ m_1 \ne m_2 }[/math], they can subtract

[math]\displaystyle{ a_1 - a_2 \equiv \operatorname{Poly1305}_r(m_1) - \operatorname{Poly1305}_r(m_2) \pmod{2^{128}} }[/math]

and find a root of the resulting polynomial to recover a small list of candidates for the secret evaluation point [math]\displaystyle{ r }[/math], and from that the secret pad [math]\displaystyle{ s }[/math]. 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 uses the Carter–Wegman structure to authenticate many messages by taking [math]\displaystyle{ a_i := H_r(m_i) + p_i }[/math] to be the authenticator on the ith message [math]\displaystyle{ m_i }[/math], where [math]\displaystyle{ H_r }[/math] is a universal hash family and [math]\displaystyle{ p_i }[/math] is an independent uniform random hash value that serves as a one-time pad to conceal it. Poly1305-AES uses AES-128 to generate [math]\displaystyle{ p_i := \operatorname{AES}_k(i) }[/math], where [math]\displaystyle{ i }[/math] is encoded as a 16-byte little-endian integer.

Specifically, a Poly1305-AES key is a 32-byte pair [math]\displaystyle{ (r, k) }[/math] of a 16-byte evaluation point [math]\displaystyle{ r }[/math], as above, and a 16-byte AES key [math]\displaystyle{ k }[/math]. The Poly1305-AES authenticator on a message [math]\displaystyle{ m_i }[/math] is

[math]\displaystyle{ a_i := \bigl(\operatorname{Poly1305}_r(m_i) + \operatorname{AES}_k(i)\bigr) \bmod 2^{128}, }[/math]

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

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

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

The message number [math]\displaystyle{ i }[/math] must never be repeated with the same key [math]\displaystyle{ (r, k) }[/math]. If it is, the adversary can recover a small list of candidates for [math]\displaystyle{ r }[/math] and [math]\displaystyle{ \operatorname{AES}_k(i) }[/math], 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 [math]\displaystyle{ i }[/math] 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 [math]\displaystyle{ (r_i, s_i) }[/math] 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. ChaCha20-Poly1305 does the same but with ChaCha instead of XSalsa20.

Security

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

[math]\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}}, }[/math]

where [math]\displaystyle{ r }[/math] is a uniform random Poly1305 key.

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

Of one-time authenticator

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

[math]\displaystyle{ \begin{align} \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{align} }[/math]

Here arithmetic inside the [math]\displaystyle{ \Pr[\cdots] }[/math] is taken to be in [math]\displaystyle{ \mathbb Z/2^{128}\mathbb Z }[/math] 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 [math]\displaystyle{ \delta }[/math] 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 [math]\displaystyle{ D }[/math] attempts of messages up to [math]\displaystyle{ L }[/math] bytes is at most:

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

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. If an adversary sees [math]\displaystyle{ C }[/math] authenticated messages and attempts [math]\displaystyle{ D }[/math] forgeries of messages of up to [math]\displaystyle{ L }[/math] bytes, and if the adversary has distinguishing advantage at most [math]\displaystyle{ \delta }[/math] against AES-128 as a pseudorandom permutation, then the probability the adversary succeeds at any one of the [math]\displaystyle{ D }[/math] forgeries is at most:

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

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)

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, 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.

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

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