Keyed cryptographic (MAC)

Poly1305

Designed by Daniel J. Bernstein (2005). A polynomial-evaluation MAC over the prime 2¹³⁰ − 5: extremely fast, with a clean information-theoretic security proof. Always used with a fresh per-message key (typically derived from a stream cipher), which is why ChaCha20-Poly1305 pairs the two so naturally.

How it works

The message is split into 16-byte chunks, each interpreted as a 128-bit integer plus a marker bit. These are coefficients of a polynomial P(r) evaluated at a 128-bit key r modulo 2¹³⁰ − 5, then masked with a second 128-bit key s. The result is a 128-bit tag.

tag = ( P_msg(r) mod (2^130 - 5) ) + s  mod 2^128

At a glance

The one-time-key rule

Poly1305 keys must be fresh per message. Reusing (r, s) for two different messages lets an attacker recover r via linear algebra and forge subsequent tags freely. ChaCha20-Poly1305 satisfies this by deriving (r, s) from ChaCha20’s output keystream with the per-message nonce.

Where it is used

• TLS 1.3 , TLS_CHACHA20_POLY1305_SHA256 cipher suite.
• WireGuard , ChaCha20-Poly1305 as the only AEAD.
• Noise framework , the default symmetric cipher choice.
• libsodium , crypto_aead_chacha20poly1305_ietf.
• OpenSSH , chacha20-poly1305@openssh.com.

Information-theoretic security

With a uniformly-random one-time key, Poly1305’s forgery probability is bounded by ⌈|m|/16⌉ / 2¹⁰⁶. Not just “hard” , provably small against unbounded adversaries (as long as the key is one-time). This is a different (stronger) security notion than HMAC’s computational PRF security.

References

• D. J. Bernstein , The Poly1305-AES message-authentication code (2005)
• RFC 8439 , ChaCha20-Poly1305 for IETF Protocols
• HMAC · GMAC