Assume Alice authenticates a message $M$ with nonce $N$ and secret key $K$, creating authenticator $A$. She then sends $A$ across the network.
The Poly1305 paper does not seem to specify whether it is possible for an adversary, whom has seen $A$, to determine whether $A$ is just random bytes or has characteristics of an output from poly1305.
For someone interested in deniability, this is an important distinction. Are poly1305 authenticators distinguishable from random data?
No, they are not distinguishable from random.
The Poly1305-AES authenticator is defined as:
$$ (((c_1 r^q + c_2 r^{q−1} + ... + c_q r^1 ) \bmod {(2^{130} - 5)}) + \operatorname{AES}_k (N)) \bmod 2^{128} $$
Since it is the sum of an AES output and some other number modulo $2^{128}$, it is PRF if:
AES output looks like PRF as long as you see less than ~$2^{64}$ of them and $k$ and $r$ are required to be independent (since they are chosen from a uniform distribution), so the authenticators are indistinguishable from random at least as long as you see significantly fewer than $2^{64}$ of them.
Yes, the authenticator might be distinguishable from random data if the key has some structure. For example, if the first half of the key is 0 or if the authenticated message has zero length, the authenticator tag will be exactly the second half of the key.
See the following python code for proof:
import tlslite
import random
# poly1305 will leak the second half of the key if
second_half = [1, 3, 3, 7, 1, 3, 3, 7, 1, 3, 3, 7, 1, 3, 3, 7]
# the first half of the key is 0
first_half = [0]*16
poly_key = first_half + second_half
poly = tlslite.utils.poly1305.Poly1305(poly_key)
message = b"this text does not matter"
print(list(poly.create_tag(message)))
# or the authenticated message is empty
first_half = [random.randrange(256) for _ in range(16)]
poly_key = first_half + second_half
poly = tlslite.utils.poly1305.Poly1305(poly_key)
message = b""
print(list(poly.create_tag(message)))
# in both cases, tag will be the second half of the key
