Poly1305 is a Message Authentication Code (MAC) that, when paired with a stream cipher like ChaCha20, provides authenticated encryption, meaning it ensures both the confidentiality and integrity of your data.
Let’s see this in action. Imagine you have a secret message and a shared secret key. You want to send this message securely, ensuring no one can tamper with it during transit and that only someone with the key can decrypt it.
Here’s a simplified conceptual flow. We’ll use ChaCha20 as our stream cipher and Poly1305 as our MAC.
First, ChaCha20 generates a pseudorandom keystream based on a secret key, a nonce, and a counter. This keystream is then XORed with the plaintext to produce ciphertext.
Plaintext: "This is a secret message."
Key: "0123456789abcdef0123456789abcdef" (32 bytes)
Nonce: "fedcba9876543210" (8 bytes)
Keystream (first 25 bytes): "k8yT5hR7jL2p1qW9sX4zC6vB3n"
Ciphertext (Plaintext XOR Keystream): "k8yT5hR7jL2p1qW9sX4zC6vB3n" XOR "This is a secret message."
Now, this ciphertext alone doesn’t tell you if it’s been altered. That’s where Poly1305 comes in. It takes the ciphertext and a secret key (the same secret key used for ChaCha20) to generate a short, fixed-size tag.
Poly1305’s magic lies in its polynomial evaluation over a finite field, specifically modulo 2^130 - 5. It treats the input data (in this case, the ciphertext) as coefficients of a polynomial. The secret key is used to define the polynomial’s evaluation point.
Ciphertext: "k8yT5hR7jL2p1qW9sX4zC6vB3n"
Key: "0123456789abcdef0123456789abcdef"
Poly1305 Tag (16 bytes): "a1b2c3d4e5f678901234567890abcdef"
When you send this, you send both the ciphertext and the Poly1305 tag. The recipient, possessing the same secret key, performs the exact same ChaCha20 encryption (to get the keystream) and then the exact same Poly1305 MAC calculation on the received ciphertext. If the calculated tag matches the received tag, you have high confidence that the data is authentic and unaltered.
The power of Poly1305, especially when used with ChaCha20, is its speed and simplicity. It’s designed to be incredibly fast on modern processors, often outperforming even hardware-accelerated AES-GCM in software. The polynomial arithmetic is efficient, and the entire process avoids complex lookup tables. It’s a prime example of a modern, secure, and performant authenticated encryption scheme.
The most surprising thing about Poly1305 is how it manages to be so secure with such simple arithmetic. It doesn’t rely on modular exponentiation like RSA or complex S-boxes like AES. Instead, it uses straightforward polynomial multiplication and addition modulo a carefully chosen prime number (or more accurately, 2^130 - 5, which is a Mersenne prime). This simplicity, combined with its speed, makes it incredibly attractive for applications where performance is critical, such as TLS 1.3.
When implementing Poly1305, it’s crucial to understand that the Poly1305 key is derived from the ChaCha20 key. Typically, the first 32 bytes of the ChaCha20 output (after processing a zero-filled block) are used as the secret key for Poly1305. This ensures that the MAC key is unique for each encryption, even if the ChaCha20 key is reused.
The next challenge you’ll encounter is understanding how to securely manage the nonces for ChaCha20.