Poly1305 is a universal hash family designed by Daniel J. Bernstein in 2002 for use in cryptography.
[1][2] 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,[3] 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,[2] 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.
, i.e., to have their top four bits clear; and to have the bytes
is a secret 16-byte string interpreted as a little-endian integer, then
If a sender and recipient share the 32-byte secret key
in advance, chosen uniformly at random, then the sender can transmit an authenticated message
When the recipient receives an alleged authenticated message
(which may have been modified in transmit by an adversary), they can verify its authenticity by testing whether
and find a root of the resulting polynomial to recover a small list of candidates for the secret evaluation point
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
is an independent uniform random hash value that serves as a one-time pad to conceal it.
where 16-byte strings and integers are identified by little-endian encoding.
, the adversary has low probability of forging any authenticated messages that the recipient will accept as genuine.
The adversary's chance of success at a single forgery is at most:
If it is, the adversary can recover a small list of candidates for
The NaCl crypto_secretbox_xsalsa20poly1305 authenticated cipher uses a message number
[8] The security of Poly1305 and its derivatives against forgery follows from its bounded difference probability as a universal hash family: If
is any 16-byte string interpreted as a little-endian integer, then
, the adversary's success probability for any forgery attempt
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
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
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.
against AES-128 as a pseudorandom permutation, then the probability the adversary succeeds at any one of the
For instance, assuming that messages are packets up to 1024 bytes; that the attacker sees 264 messages authenticated under a Poly1305-AES key; that the attacker attempts a whopping 275 forgeries; and that the attacker cannot break AES with probability above δ; then, with probability at least 0.999999 − δ, all the 275 are rejectedPoly1305-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,[2] 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] Below is a list of cryptography libraries that support Poly1305: