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?
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.