Can AES GCM mode detect an incorrect key and refuse to decrypt?

Question

I understand that AES in GCM mode produces an authentication tag that is used to ensure that a tampered with cipher text is not decrypted. However, if I pass the wrong key will AES in GCM mode detect that I am using the wrong key and give me an error message or will it give me back garbled data because I used the wrong decryption key?

Does the AES-GCM spec say that an error will be raised if the wrong key is used?

UPDATE The error does not have to indicate that the key was wrong, just that decryption should fail so incorrect clear text is not returned to the caller.

Answer 1

An AES-GCM-encrypted message is obtained per an encryption key $K_0$. As for any correct implementation of AES-GCM, we assume that legitimate encryption of multiple ciphertexts with $K_0$ uses $\text{IV}$ such that the counters (obtained by increment of the $\text{IV}$) do not overlap; and that the implementation of decryption gives an error message when the authentication check fails.

will AES in GCM mode detect that I am using the wrong key and give me an error message (..) ?

No, with strictly only what's stated. It is possible to exhibit a ciphertext (including $\text{IV}$) and two distinct keys $K_0$ and $K_1$ that both decipher successfully (and a plaintext that, encrypted with key $K_0$ and $\text{IV}$, encrypts to the ciphertext including $\text{IV}$ and authenticator tag, thus matching the wording in the above re-statement of the question).

But yes, if the ciphertext was prepared legitimately (which was my assumption in a first version of this answer). An attack against a given ciphertext, aiming at exhibiting $K_1$, has cost $p\,2^k$ AES encryption for probability $p$ of success and $k$-bit authentication tag, even if multiple ciphertexts are available. Prepared legitimately holds at least if one (or both) of the following holds:

• The key $K_0$ is chosen uniformly at random independently of $\text{IV}$ and the plaintext (even if the plaintext, $\text{IV}$, and $K_1$, are chosen maliciously). That includes any case where $K_0$ is kept secret from adversaries at least until production of the plaintext, which is a standard assumption.
• The $\text{IV}$ is chosen uniformly at random independently of $K_0$ and the plaintext (as is the case in some but not all legitimate uses of AES-GCM encryption); that's even if the plaintext, $K_0$, and $K_1$, are chosen maliciously.

Argument: from the structure of GCM it can be shown, under a model of AES as an ideal cipher, that the AES-GCM authenticator tag is a PRF of the key and $\text{IV}$, for any fixed message (plaintext, or ciphertext excluding $\text{IV}$ and authenticator tag).

---

Conclusion: AES-GCM encryption with secret key $K_0$, or with random unpredictable $\text{IV}$, makes it infeasible that later (including if $K_0$ leaks) anyone could find (much less encounter by accident) another key $K_1$ that allows decryption of the unmodified ciphertext (including $\text{IV}$ and authenticator), yielding almost certainly corrupted deciphered plaintext. However, that can be defeated by the party choosing $K_0$/doing the encryption/choosing the message; and the essential unmodified ciphertext hypothesis is artificial, for it goes against the rationale of using authenticated encryption.

Answer 2

GCM will fail to decrypt on any of the following conditions:

• Ciphertext manipulation, corruption, or truncation
• Incorrect nonce or authentication tag
• Incorrect key
• Implementation or device error during decryption

However the entire file needs to be processed for this to occur, and it will occur within a bound of probability, meaning there is a very small chance it can still succeed even though the plaintext will be wrong, the probability is primarily determined by the tag size, so the bigger the better.

Newer ciphers can make use of intermediate tags to detect a problem sooner, like 1MB into a 30GB file, saving substantial computation when an error occurs.

If you want to prevent processing of the file when an incorrect key is used, you can include a Key Check Value which is only a few bytes long, but not long enough to give away substantial information about the key or lower security beyond a reasonable amount. An 8-bit KCV gives a 256-to-1 chance than an incorrect key will be determined valid. However long your KCV is, assume it lowers security by that much (even if it may not), so take that and the key length into account if you use a KCV. My KCV genertion method is to encrypt an all 0-bit block, hash it, then truncate it to the desired length.

Answer 3

Any authenticated encryption mode will do this (at least assuming that the wrong key is independent of the correct one).

Specifically, authenticated encryption guarantees that an attacker who does not know the key will not be able to generate a forged message that would be accepted by the decryptor with a non-negligible probability.

If an attacker would be able to encrypt a message with one key, and have it be accepted as valid when decrypted by another (unrelated) key, then this property would obviously be violated. In particular, an attacker would be able to forge messages simply by picking a random key and using it to encrypt something.

Of course, if such a forged message created by encrypting with a different key was accepted, it would typically decrypt into random garbage. But the definition of unforgeability doesn't care about that; it just says that forged messages should not be accepted at all.*

---

Note that this argument does have a minor loophole: it only applies if the two keys are chosen independently, leaving open the possibility that a message encrypted with one key might be accepted and decrypted by another related key obtained by making some small change to the original key. Typically, definitions of authenticated encryption don't consider such related-key attacks, and indeed some authenticated encryption schemes do allow them. As fgrieu's answer shows, this includes AES-GCM, at least if the attacker has sufficient control over the original message.

---

Ps. Even with AES-GCM or other authenticated encryption schemes, it can still sometimes be useful to include an explicit "key check value" of some kind alongside the message. This applies particularly when the message is potentially very long (since GCM, like most AE schemes, needs to process the entire message to determine whether it's valid or not) and when the key is supplied manually by the user (e.g. in a key file or derived from a password entered by the user).

One simple way to create such a key check token for an authentic encryption scheme is to encrypt a zero-length message using the key. If the resulting ciphertext decrypts successfully, the key is almost surely correct. (Of course, an attacker might be able to replace the key check token with a different one, but that counts as malicious tampering that will be detected by the authentication on the actual message.)

---

^{*) As a minor exception, some weaker definitions of authenticated encryption may permit the attacker to modify a valid message and have it still be accepted, if the modification doesn't actually change the plaintext the message decrypts to. But most definitions forbid even that.}