11
$\begingroup$

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?

$\endgroup$

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
10
  • 3
    $\begingroup$ 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? $\endgroup$ Jun 18, 2017 at 8:24
  • 1
    $\begingroup$ @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. $\endgroup$
    – Maarten Bodewes
    Jun 18, 2017 at 12:21
  • 1
    $\begingroup$ @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$) $\endgroup$
    – poncho
    Jun 18, 2017 at 12:29
  • $\begingroup$ 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. $\endgroup$ Jun 18, 2017 at 17:57
  • 1
    $\begingroup$ @lightspeeder: looking at it further, it would appear that, if $m$ is the 16 byte message with the value $2^{128}-1$, and $m_0$ is the 16 byte message with the value $2^{128}-4$, and $g = 2^{128}-5$, then $H_r(m) = H_r(m_0) \oplus g$ for about half of all possible $r$ values. Hence, if you modify Poly1305 by replacing the addition with xor, then the modified MAC is easy to break; get the MAC for $m$, and then you have quite a good probability of guessing the MAC for $m_0$ $\endgroup$
    – poncho
    Jun 18, 2017 at 18:58
2
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 22, 2017 at 21:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – pg1989
    Jun 22, 2017 at 22:12
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 24, 2017 at 3:20
  • 2
    $\begingroup$ "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." Read these slides, particularly about knowing weaknesses in many curve choices, then searching (using supercomputers) many choices of SHA1($s$) to find a weak curve then publish $s$. The real kicker is the curves were generated by Jerry Solinas at NSA (the same NSA who backdoored DualEC). The NIST curves are definitely backdoored. $\endgroup$ Jun 24, 2017 at 18:16
  • 3
    $\begingroup$ Students are entitled to their opinions, but perhaps you should write to the NSA and Pentagon to tell them they are doing it all wrong by using non-standard cryptography. After all NSA uses non-standard Suite A for anything actually important. Also the Washington-Moscow hotline, Cyber Security emergency link and the Pentagon use one-time pads. Information-theoretic security has its place. God have mercy on whoever relies on mere NIST standards, with "epic" standards like DualEC, P-256, AES-CBC-128 and CBC-MAC. $\endgroup$ Jul 1, 2017 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.