Necessary to authenticate nonce if authentication-key is derived from nonce?

Question

Lets suppose my messages are composed like this: unique_message_nonce + encrypted_message + mac

Because I don't have an AEAD-scheme, I can encrypt and authenticate my message in two ways:

1. Use authenticated-encryption for message:

   let key = KDF(key: master_key, info: "Key:" + unique_message_nonce)
   let nonce = KDF(key: master_key, info: "Nonce:" + unique_message_nonce)
   let (encrypted_message, mac) = AuthEnc(key: key, nonce: nonce, message: message)
   

2. Encrypt the message and compute MAC over unique_file_nonce + encrypted_message:

   let encryption_key = KDF(key: master_key, info: "EncKey:" + unique_message_nonce)
   let encryption_nonce = KDF(key: master_key, info: "EncNonce:" + unique_message_nonce)
   let encrypted_message = Enc(key: encryption_key, nonce: encryption_nonce, message: message)
   
   let mac_key = KDF(key: master_key, info: "MACKey:" + unique_message_nonce)
   let mac = Auth(key: mac_key, message: unique_file_nonce + encrypted_message)
   

Is the first one secure?

Usually, you would use the 2nd one and authenticate everything because if s.o. tempers with the nonce, he might be able to alter the plaintext without changing the MAC.

However, as far as I can see, in the 1st one the unique_message_nonce is implicitly included in the MAC:

• If s.o. changes unique_message_nonce, key will change too and the authentication will fail
• Without knowing master_key, an attacker cannot manipulate unique_message_nonce to create a malicious key

Answer 1

Yes. Assuming KDF and AuthEnc are secure and you are using them with correct prameter lengths, the first one is secure.

Usually, you would use 2nd and authenticate everything because if s.o. tempers with the nonce, he might be able to alter the plaintext without changing the MAC.rrect parameter lengths, yes your first scheme is secure.

In any proper AE(AD) scheme, the nonce is used in both the ciphertext and the MAC generation so tampering with it will inevitably lead to a MAC verification failure.

The only thing I would change is dropping the nonce calculation. There is not really a point in deriving the nonce from your master key, if you already know unique_message_nonce is actually unique (and that is all that most popular AEAD schemes like GCM and CCM need).

I would even prefer version one over the second one. It is a lot simpler for the developer and AE(AD) schemes were built for just what you want. The fewer steps you have to do yourself, the fewer errors you can make.