Do AEADs also authenticate the nonce?

Question

I'd like to include an authenticated timestamp in my messages. I'm wondering if I can save a little space by putting the timestamp in the nonce.

Concrete example:

1. Let's say I'm using XChaCha20-Poly1305 with a shared secret key.
2. I generate the nonce/IV by concatenating an 8-byte timestamp and a 16-byte random value.
3. I send concat(nonce, ciphertext, auth_tag)
4. The receiver runs the decrypt+verify procedure and it succeeds.

Can the receiver then extract the timestamp part of the nonce and trust that it is authentic?

With a more "traditional" composition, like AES-CBC-then-HMAC, the nonce is obviously authenticated. Is that still the case for these newer AEADs?

Answer 1

Yes, AEAD constructions always authenticate the nonce. If they didn't then the integrity and authentication of the resulting plaintext after decryption would not be ensured.

You can see the definition in RFC 5116: An Interface and Algorithms for Authenticated Encryption, section 2.1. Authenticated Encryption:

The nonce is authenticated internally to the algorithm, and it is not necessary to include it in the AD input. The nonce MAY be included in P or A if it is convenient to the application.

Not all AEAD ciphers may necessarily keep to the letter of this RFC (the inclusion of the authentication tag in the ciphertext is debatable if you ask me - I consider it a separate field). However, I haven't seen any AEAD cipher that doesn't authenticate the nonce by design.

---

You're writing that

With a more "traditional" composition, like AES-CBC-then-HMAC, the nonce is obviously authenticated.

This is obviously not true. Yes, it is possible to design such a scheme and any competent cryptographer would not for get to authenticate the IV. There are even tries to standardize such a scheme, see e.g this scheme based on CBC with HMAC-SHA-1.

Less competent protocol designers are however free to shoot themselves in the foot when designing or implementing such a scheme. When using a well designed / reviewed / tested library and an AEAD scheme such mistakes are avoided.