Key Encryption: Does it need to be Authenticated?

Alice wants to store files $m_i$ on Bob's untrusted cloud storage platform, with the additional restriction that she can only store one master key $k$ herself.

She encrypts the files with keys $k_i$ respectively and obtains $c_i := Enc_{k_i}(m_i) $. She also encrypts the keys as $k'_i := Enc_k(k_i)$ and sends the tuples $(k'_i,c_i)$ to Bob to store.

Seems quite natural that the encryption mode used for the $c_i$ be authenticated encryption. But for the $k'_i$, due to the high entropy nature of the payload and the fact they are used only for decrypting authenticated encryption, it seems that the encryption $Enc_k(k_i)$ does not need to be authenticated.

Is that true? If so, what is a more formal and coherent argument for it? If not, what attack does this relaxation enable?

If it was possible for an AEAD cipher to validate when the wrong key a random key was used then I guess the cipher would be considered insecure. As such I think that the exclusion of the key in the calculation would make much of a difference.

On the other hand, it is unlikely to the extreme that an input AD would be handled as key in a block cipher. So including it into the AD should not make most algorithms insecure either. I'm still slightly worried about the internal MAC algorithm though; it could be that there is a weird mathematical relation that could be exploited; I don't think there is any specific requirement to avoid that.

Generally however I would not treat a key as data. That's probably more dangerous and tricky design-wise. Keys might be stored in containers that don't make the data available (e.g. in a hardware keystore or TPM). Even if you do not plan to use protected keys right now, it would exclude this option in the future.

So what other options are there:

1. Include the ciphertext of the wrapped key as AEAD data. That way the key is double protected. However, if you use the wrong mode (such as counter mode) then an attacker could make bitwise changes in the key and additional data, which would make me a bit uncomfortable. So I'd use a key wrapping mode designed for the purpose in that case or fall back on CBC with a zero IV (yuk). That should not give the attacker much control over the key value.

2. Instead of wrapping the keys, derive the keys using key derivation data (e.g. label / info / sequence counter / salt) stored with the ciphertext. If you want you can then include the stored key derivation data in the AD. This has the drawback that you cannot directly use random keys (generated locally) to encrypt the data.

Conclusion: I would be more worried about how you wrap or derive the keys used with the data. Including the derived keys themselves in the AD is a bad idea, but you could include other data such as the ciphertext or derivation data within the AD and make it harder for an adversary to create a wrapped key / ciphertext combination.

In addition to the special wrapping mode I would also recommend using 256 bit keys to avoid multi-target attacks. Using a special wrapping mode or key derivation would protect against related key attacks. With this kind of use case you might also have to worry about changes in files and adversaries swapping ciphertext contents of files.