Do Carter–Wegman MACs allow key reuse if the MAC tag is kept secret?

Question

Poly1305 (and GHASH) are secure authenticators, but only for one use. Thus, nonce reuse in Poly1305-AES, ChaCha20-Poly1305, and AES-GCM all reveal the authentication key. However, my understanding is that this is because (in Poly1305-AES, ChaCha20-Poly1305, and AES-GCM) the output of the hash function is encrypted using a stream cipher, and as such nonce reuse gives away the XOR of the hashes.

Suppose that one uses AES in ECB mode to encrypt the authentication tag instead (using a secret key that is unrelated to the other keys, the message, and the nonce). In this case, nonce reuse gives away no information unless the auth tags collide (which will only happen with probability about $2^{-56}$ or so). Similarly, one could use Blake2 or Keccak to hash a nonce, secret key, and the tag to produce a larger tag.

At least this is all my understanding. I am not a cryptographer, and I could be wrong! Am I?

Note: I do not plan on using this in any actual software.

Answer 1

You can use methods for hiding the output of the polynomial hash that don't require nonces, such as encrypting with a block-cipher of matching block-size or hashing it with a keyed hash (PRF).

Not using a nonce reduces the security bounds (security decreases as the attacker sees more messages using the same key), makes it incompatible with stream ciphers and increases latency, but avoids the risk of total failure due to nonce reuse.

You can avoid the reduced security bounds while keeping nonce misuse resistance by hashing both the nonce and the polynomial hash output, but the other downsides remain.

The Poly1305 paper justifies the use of nonces as follows:

There are several reasons that Poly1305-AES uses nonces.

First, comparable protocols without nonces have security bounds that look like $C ( C + D ) L / 2^{106}$ rather than $D L / 2^{106}$ -- here $C$ is the number of messages authenticated by the sender, $D$ is the number of forgery attempts, and $L$ is the maximum message length -- and thus cannot be used with confidence for large $C$.

Second, nonces allow the invocation of AES to be carried out in parallel with most of the other operations in Poly1305-AES, reducing latency in many contexts.

Third, most protocols have nonces anyway, for a variety of reasons: nonces are required for secure encryption, for example, and nonces allow trivial rejection of replayed messages.

In the popular XSalsa20Poly1305 combination, you already have a severe confidentiality failure if you reuse nonces, so a MAC failure on top of that doesn't seem to be a big deal. You could use Salsa20 as a hash instead of a stream cipher to hide the polynomial hash output, but that'd add a non-parallelizable Salsa20 computation (SIMD implementations of Salsa20 benefit from parallelism, even in software), making it expensive for small messages.