Are poly1305 authenticators distinguishable from random data?

Question

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?

Answer 1

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:

• the AES output is PRF and
• the two numbers are independent.

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.

Answer 2

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