Poly1305 on arvau

Wikipedia / Poly1305

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, a CarterWegman 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

. To do this, Poly1305:

as a little-endian 16-byte integer.
into consecutive 16-byte chunks.
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.
.
encoded in little-endian return a 16-byte hash.

, are:

, then:

, i.e., i.e..

Use as a one-time authenticator

is a secret 16-byte string interpreted as a little-endian integer, then

is called the authenticator. When the recipient receives an alleged (which may have been modified in transmit by an adversary), they can verify its authenticity by testing whether

that will pass verification.

must not be reused for two messages. If the adversary learns

, they can subtract

. 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 be the authenticator on the is an independent uniform random hash value that serves as a one-time pad to conceal it. Poly1305-AES uses AES-128 is encoded as a 16-byte little-endian integer.

is reused between messages.

forgeries, and can \operatorname{AES}_k from a uniform random permutation is very small.) The adversary's chance of success at a single forgery is at most:

, 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 with the XSalsa20 stream cipher to generate a per-message key stream 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 uses the first 32 bytes of the ChaCha stream cipher output to generate a one-time Poly1305 key, discards the next 32 bytes, and uses the rest to encrypt the message. XChaCha20-Poly1305 using XChaCha instead of ChaCha or XSalsa20 has also been described.

Security

The security of Poly1305 and its derivatives against forgery follows from its bounded difference probability as a universal hash family is any 16-byte string interpreted as a little-endian integer, then

is a uniform random Poly1305 key.

This property is sometimes called -almost-Δ-universality, or -AΔU, in this case.

Of one-time authenticator

bytes is:

for simplicity.

Of NaCl and ChaCha20-Poly1305

For NaCl crypto_secretbox_xsalsa20poly1305 and ChaCha20-Poly1305 against XSalsa20 or ChaCha as pseudorandom functions bytes is at most:

Of Poly1305-AES

The security of Poly1305-AES against forgery follows from the CarterWegmanShoup structure, which instantiates a CarterWegman authenticator with a permutation to generate the per-message pad. against AES-128 as a pseudorandom permutation forgeries is at most:

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.