6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good question; originally, early CW MACs (such as UMAC) did exactly what you suggest; they computed a universal hash, and then SHA-hashed it (along with the nonce); you didn't run into trouble unless the nonce and the UH output collided. That hasn't been the fashion recently, and I'm not sure why. Now, with GCM, one original design goal was to be pipelinable; that's why it didn't (say) AES encrypt the UH output. I don't know why (say) Poly1305-AES doesn't do that, given that it was designed with software in mind. $\endgroup$ – poncho Feb 17 '16 at 1:26
5
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As many AEAD ciphers use AES-CTR or a stream cipher internally, nonce reuse will definitely be an issue for GCM, EAX, CCM and the stream ciphers in the answer. It of course depends on the threat model which loss of security is worse (personally I would consider the loss of integrity / authenticity a bigger issue than loss of confidentiality for most protocols requiring transport security). $\endgroup$ – Maarten Bodewes Feb 17 '16 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.