# Is Poly1305 an information-theoretically secure MAC?

I have heard some people say that the Poly1305 authenticator is a "nuclear" MAC i.e. it is information-theoretically secure. After reading the paper I see it is based on the Wegman-Carter MAC which is supposedly the natural authentication pairing with the one-time pad cipher.

Is it true though that Poly1305 is really an information-theoretically secure MAC? Here is an excerpt from the paper:

# 1 Introduction

This paper introduces and analyzes Poly1305-AES, a state-of-the-art secret-key message-authentication code suitable for a wide variety of applications.

Poly1305-AES computes a 16-byte authenticator Poly1305r(m, AESk(n)) of a variable-length message m, using a 16-byte AES key k, a 16-byte additional key r, and a 16-byte nonce n. Section 2 of this paper presents the complete definition of Poly1305-AES.

Poly1305-AES has several useful features:

• Guaranteed security if AES is secure. The security gap is small, even for long-term keys; the only way for an attacker to break Poly1305-AES is to break AES. Assume, for example, 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 a probability above δ. Then, with probability at least 0.999999−δ, all of the 275 forgeries are rejected.
• Cipher replaceability. If anything does go wrong with AES, users can switch from Poly1305-AES to Poly1305-AnotherFunction, with an identical security guarantee. All the effort invested in the non-AES part of Poly1305-AES can be reused; the non-AES part of Poly1305-AES cannot be broken.

So it appears Poly1305 is only secure if AES is secure. So in theory if I do not like AES I can swap it out for something else like ChaCha20 (as many have done e.g. SSH and TLS 1.3). However then the authentication is still only as secure as ChaCha20 which in itself is not information-theoretically secure. So then, what if I need an authentication tag that will remain secure for a long period of time (100+ years) and even resist cryptanalysis indefinitely?

I understand the point of the Poly1305 is to re-use the keys for many messages as long as the nonce changes each time. However, assume a hypothetical system which has many one-time pads generated by a HWRNG and they are pre-shared between two parties via a physical exchange. The key material for each message is divided up as follows:

• 92 byte key for encrypting the 92 byte message using XOR $$\oplus$$
• 16 byte Poly1305 encryption key $$k$$ (formerly the AES key)
• 16 byte Poly1305 additional key $$r$$
• 16 byte Poly1305 nonce $$n$$

So in this scenario the $$k$$, $$r$$ and $$n$$ are unique and truly random per message sent. So per one-time pad encrypted and authenticated message it uses up 140 bytes of true random data. Now given that this construction creates the Poly1305 tag:

Poly1305$$_r$$($$m$$, AES$$_k$$($$n$$))

Can the AES$$_k$$($$n$$) portion be simply replaced with $$k$$ $$\oplus$$ $$n$$? In other words, encrypt the nonce with a one-time pad. Will this remain theoretically secure indefinitely?

So in this scenario the $$k$$, $$r$$ and $$n$$ are unique and truly random per message sent. […] Now given that this construction creates the Poly1305 tag:

$$\textsf{Poly1305}_r(m, \textsf{AES}_k(n))$$

Can the $$\textsf{AES}_k(n)$$ portion be simply replaced with $$k \oplus n$$?

Yes, but it's still needlessly complicated. As long as each 128-bit key $$k$$ is random and used only once, you can omit the nonce $$n$$ entirely and just use $$\textsf{Poly1305}_r(m, k)$$ directly.

In fact, the only purpose of the AES encryption in Poly1305-AES is to construct a "pseudo-OTP" (i.e. a pseudorandom bit sequence) by encrypting a sequence of nonce values. If you already have a true one time pad, you do not need this step at all, and can just use a 128-bit segment of the pad (which, of course, must not be reused for this or any other purpose) directly as the input to the Poly1305 function.

Can the $AES_k(n)$ portion be simply replaced with $k \oplus n$?

No, but you're close, it would be replaced with $k + n$, where $+$ is addition modulo $2^{128}$; then it becomes informational theoretic.

Here's why: Poly1305 is based on a polynomial universal hash. This is a hash where we select a finite field $GF(p^i)$, select a private value $x \in GF(p^i)$, interpret the message being authenticated as a series of value $m_a, m_{a-1}, ..., m_1$, and compute the value:

$$m_a x^a + m_{a-1} x^{a-1} + ... + m_1 x^1 + f(k)$$

where the above additions and multiplications are done in $GF(p^i)$, and $f(k)$ is the 'unknown encrypted nonce' ($AES_k(n)$ in the Poly1305, $k$ in your case).

The idea here is if someone is able to find a second message and tag that authentications with the same nonce, then we can 'subtract' the two polynomials, and find a polynomial in $x$ that evaluates to 0. And because $GF(p^i)$ is a field, that polynomial has no more than $a$ zeros; that is, unless $x$ is one of $a$ out of $p^i$ possible values, that polynomial won't be zero).

Now, with Poly1305, they use the values $p = 2^{130}-5$ and $i = 1$. What this means is that the operation that adds $k$ is not bitwise xor; instead, it is modular addition. Now, the above proof assumes that the addition is actually modulo $2^{130}-5$, not $2^{128}$; it turns out that it isn't hard to show that this increases the possible number of 0's by a relatively small factor. I don't know of any corresponding proof if you replace the addition with xor, and hence using xor would appear to be foolhardy.

• If the $AES_k(n)$ part can be replaced with $k+n$ and the result is still secure (even more secure than the original one), why is the MAC even using AES (or "a block cipher") at all? – Paŭlo Ebermann Jun 18 '17 at 8:24
• @PaŭloEbermann I presume that key reuse is the main concern here. Note that GCM mode only uses a single key for AES in CTR mode. Key expansion is more expensive and doubling the key size (like SIV unfortunately does) is unpractical. – Maarten Bodewes Jun 18 '17 at 12:21
• @PaŭloEbermann: Maarten is right, is $k + n$, each value $k$ can be used once; if you reuse $k$ values for different messages, you lose security (just like you lose security in OTP if you reuse keys). Poly1305-AES uses AES to convert a predictable nonce into an unpredictable $AES_k(n)$ value. BTW: GMAC (the authentication part of GCM) is essentially the same, except that it has $p=2, i=128$ (and the $+$ operation is actually $\oplus$) – poncho Jun 18 '17 at 12:29
• Reading the sample code in the paper, the encryption of the nonce (AES$_k$($n$)) is pre-computed and is passed as a separate parameter (input) into the Poly1305 function. The Poly1305 function does not take the $k$ as an additional input. So therefore it seems that the encryption of the nonce is independent (mutually exclusive) and not related to the inner workings of the Poly1305 MAC or polynomial universal hashes. In the original design, AES-CTR (or ChaCha20) is computing a keystream, then that keystream is XORed with the nonce. So it should be stronger if you XOR the nonce with a OTP. – lightspeeder Jun 18 '17 at 17:57
• @lightspeeder: did you go through the Proof of the security guarantee section of the paper? If you did, you'll see that it depends on the AES output being combined with modular addition; relying on the fact that $H_r(m) = H_r(m_0) + g$ occurs with only a tiny probability. If you replace the addition with xor, then the equivalent would be $H_r(m) = H_r(m_0) \oplus g$, I don't know of any specific probability bound of that (and it would appear to be foolish to depend on it without one). BTW: if you feel like you have to use xor, consider GMAC... – poncho Jun 18 '17 at 18:18

No, it is not information-theoretically secure as a MAC. Poly1305-AES, like GHASH and a few other MACs, is based on a construction due to Carter and Wegman which does meet information-theoretic security for a single message.

Replacing $\text{AES}_k(n)$ with a true one-time pad might work, but seems unnecessary. As long as the number of messages authenticated with a given key remains fairly small, forging a Poly1305-AES tag is nearly as hard as breaking AES. Realistically this is about the strongest security guarantee you can ask for, and should suffice for nearly all applications.

• However the security of AES is not proven, nor guaranteed to be secure indefinitely, so anything relying on AES for encryption or authentication seems to fall far short of the requirements for an information-theoretically secure system. – lightspeeder Jun 22 '17 at 21:12
• Using non-standard crypto because you need an "indefinitely secure" system is infinitely more dangerous than relying on well-tested primitives like AES. The likelihood of whoever implements this "indefinitely secure" crypto screwing up is much higher than the likelihood of a practical break in AES. – pg1989 Jun 22 '17 at 22:12
• Using only "standard" crypto can get you into much more trouble, especially "well-tested", "safe" primitives and protocols from "NIST" e.g. Dual EC DRBG, cooked elliptic curves etc. When talking about 100 year security literally no-one recommends use of a single primitive like AES. It's already vulnerable to various side channel attacks if not implemented perfectly. If AES holds up to another 10-20 years of cryptanalysis and still remains secure I would be very surprised. You could look into robust combiners for long term security as well, but they come without the information-theoretic proof. – lightspeeder Jun 24 '17 at 3:20
• Everything you've said is either incorrect or irrelevant. For example, side-channel attacks only affect long-term security if you use the same key the whole time. Further, we have mature AES implementations written by smart people that aren't vulnerable to side channel attacks. – pg1989 Jun 24 '17 at 4:42
• Also note there is not a single shred of evidence that any elliptic curve standard has been "cooked", whatever that means. Yes, DualEC was backdoored, but that only affects that particular DRBG design. – pg1989 Jun 24 '17 at 4:45