With AES encryption and a known key and plaintext, can an attacker create a different key and plaintext resulting in the same ciphertext?

Question

In short: with AES encryption can an attacker create a new key2 and plaintext2 so that AES_key1(plaintext1) = AES_key2(plaintext2)

If so, can it be solved by just applying for instance a MAC like AES-GCM or an AES-CTR with a SHA256 HMAC?

Intended application: The encryption of a file. Every client having the key can decrypt the file. The encrypted file is handled blindly by a server (without knowing the key) by its SHA256 hash. When a new client is handed over a false key with the hosted file, he should be able to detect it is the wrong key. And not getting any other (noisy) binary from the same encrypted file as a result. Noting that an attacker delivering the false key has access to the original key, the ciphertext and thus also the plaintext.

(The option of identical files being encrypted with different keys should be there. So deterministic encryption is not my intention)

An other possible easy solution I thought of would be to store the hash of the secret key together with the encrypted file on the server and send it to the client to verify. But I actually prefer using a well known out-of-the-box solution, and not something I came up with. Is applying a MAC / HMAC enough to guarantee only one key results in the given ciphertext.

Hope my intention is clear, and someone knowledgeable can point me in the right direction.

Answer 1

For basic AES, it is easy to find two keys in this way. Take any $key1$ and $plaintext1$ and compute $c=AES_{key1}(plaintext1)$. Then, take any $key2$ and compute $plaintext2 = AES^{-1}_{key2}(c)$. It follows that $AES_{key1}(plaintext1) = AES_{key2}(plaintext2)$. Having said this, if AES is used in an authenticated encryption mode with a MAC, this may not necessarily be possible. I wish to stress that there is no guarantee that not, and such a thing would need to be proven. In particular, if you did the standard encrypt-then-MAC (with different keys), then this would be vulnerable in exactly the same way, since the "encryption" part is unchanged. Bottom line, this should be possible to achieve, but it's certainly not guaranteed, and often doesn't hold at all.