Poly1305 is a universal hash family designed by Daniel J. Bernstein in 2002 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,

and then using ChaCha in the ChaCha20-Poly1305 authenticated cipher

Description

Definition of Poly1305

Poly1305 takes a 16-byte secret key <math>r</math> and an <math>L</math>-byte message <math>m</math> and returns a 16-byte hash <math>\operatorname{Poly1305}_r(m)</math>.

To do this, Poly1305:

Security

The security of Poly1305 and its derivatives against forgery follows from its bounded difference probability as a universal hash family:

If <math>m_1</math> and <math>m_2</math> are messages of up to <math>L</math> bytes each, and <math>d</math> is any 16-byte string interpreted as a little-endian integer, then

<math display="block">

\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>r</math> is a uniform random Poly1305 key.

where <math>\epsilon = 8\lceil L/16\rceil/2^{106}</math> in this case.

Of one-time authenticator

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

<math display="block">

\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>\Pr[\cdots]</math> is taken to be in <math>\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>\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>D</math> attempts of messages up to <math>L</math> bytes is at most:

<math display="block">

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

</math>

Of Poly1305-AES

The security of Poly1305-AES against forgery follows from the Carter&ndash;Wegman&ndash;Shoup structure, which instantiates a Carter&ndash;Wegman authenticator with a permutation to generate the per-message pad.

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

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

  • 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