Is nonce-less Encrypt-then-HMAC as secure as poly1305

Question

While reading https://crypto.stackexchange.com/a/88732/87450 I noticed that it suggests encrypt-then-HMAC as a defense for partition attacks. However as far as I know unlike poly1305, HMAC does not make use of nonces and in the poly1305 paper DJB says:

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 $DL/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.

Doesn't that mean that HMAC is an inferior choice compared to poly1305 if we consider all threats except partition attacks?

Answer 1

Doesn't that mean that HMAC is an inferior choice compared to poly1305 if we consider all threats except partition attacks?

One attack against a MAC with a limited intermediate state [1] is one which tries to find a collision in that intermediate state between two different MAC evaluations; the attacker can then use that intermediate collision to generate a forgery.

Poly1305 has an internal intermediate state of 130 bits; in contrast, HMAC-SHA256 has an intermediate state of256 bits; this much larger intermediate state implies that finding internal collisions is much harder.

---

[1]: That is, processes the message in one pass, and summarizes the message it has processed so far in a bounded number of bits.

Answer 2

Even though they have slightly different properties, both Poly1305 and HMAC take a key and a message, and return an authenticator. A nonce is not a parameter they have.

The nonce is a parameter of the encryption and decryption functions. For a given key, different nonces are likely to generate different ciphertexts. And in an encrypt-then-MAC construction, different ciphertexts are consequently likely to produce different authenticators.

So, using a HMAC doesn’t prevent usage of a nonce. The nonce is not used by the MAC function itself, especially in an encrypt-then-MAC construction.

It also means that a static (or reused) nonce can be catastrophic no matter what MAC is being used.