2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is what expected. If the tag is incorrect = there is something wrong. The incorrect key,IV, tag, and computation errors can because. It is a good call from the designers. The library, though, still need to provide the means to decrypt. The last parts make this question, off-topic here. $\endgroup$ – kelalaka Oct 4 '20 at 20:56
  • $\begingroup$ How does the last part make the question off topic here? $\endgroup$ – ams Oct 4 '20 at 20:57
  • $\begingroup$ I am not asking how to write the code to detect if the key is invalid? I am asking what the does the AES-GCM spec say should happen if the wrong key is used? I will remove the references to the code. $\endgroup$ – ams Oct 4 '20 at 21:02
  • 1
    $\begingroup$ NIST 800-38d. As far as I can see doesn't mandate! $\endgroup$ – kelalaka Oct 4 '20 at 21:06
  • $\begingroup$ Any of key, nonce, ciphertext, or tag being wrong will equally cause authentication to fail, so while it will with overwhelming probability give an error, that error won't specifically indicate wrong key. $\endgroup$ – dave_thompson_085 Oct 5 '20 at 2:38
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A properly designed KCV will not lower security at all; at best, it gives an attacker a way to test a potential key, however with most ciphertext modes, such ways already exist at about the same cost... $\endgroup$ – poncho Oct 5 '20 at 13:03
  • $\begingroup$ @poncho I agree, but then you are making the assumption that it is properly designed (I have seen them copy paste key bits), hence my assumption that it will lower security. my method should not lower security, especially if you use an expensive hash or something like bcrypt $\endgroup$ – Richie Frame Oct 5 '20 at 21:05
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In "Any authenticated encryption mode will do this", we need to ponder what "this" is. AES-GCM does not insure that the same cryptogram can't be accepted under two unrelated keys, yielding widely different deciphered plaintexts, $\endgroup$ – fgrieu Oct 6 '20 at 18:31
  • $\begingroup$ @fgrieu: Noted, and amended. (BTW, I would've liked to include a less vague reference your new answer, but I'm not sure I fully understand it myself. Maybe an example of a message that is accepted by two AES-GCM keys, or an outline of how to construct one, could help make it a bit more accessible?) $\endgroup$ – Ilmari Karonen Oct 6 '20 at 21:41
  • $\begingroup$ To be honest, I'm not seeing the detailed process to generate that ($K_0$, $K_1$,ciphertext) [with IV and tag in ciphertext] passing decryption that I'm talking about. But I do see that finding it for fixed known $K_0$, $K_1$ is a matter of arithmetic in a large Galois Field involving little AES, thus I trust reputable others (including poncho and squeamish ossifrage) and that article that it is easy. Note: I'm uncomfortable with your "wrong key is independent of the correct one". My condition is: $K_0$ or IV is unknown to who defines plaintext. $\endgroup$ – fgrieu Oct 7 '20 at 6:40
  • $\begingroup$ @fgrieu: My basic assumption is that $K_1$ is unknown to whoever chooses $K_0$, IV and plaintext, and vice versa. In particular, in reducing the problem of detecting incorrect keys to unforgeability, I'm assuming that the "incorrect" key $K_1$ is chosen by the challenger and not known to the attacker, whose task is to exhibit (a "correct" key $K_0$ and) a message that is accepted as valid when decrypted using (both $K_0$ and) $K_1$. Clearly, if the attacker can do this (including the parts in parentheses) they can also do it without the parts in parentheses, thus breaking unforgeability. $\endgroup$ – Ilmari Karonen Oct 7 '20 at 14:03
  • $\begingroup$ … Of course, this reduction breaks down if the attacker may somehow choose $K_0$ as a function of (some information about) $K_1$ (that is not made available to the attacker in the course of a standard unforgeability challenge), even if they might not straight up learn $K_1$ itself, or, conversely, if the challenger may decide to cooperate with the attacker and choose $K_1$ after the fact based on $K_0$ (or on any other values chosen by the attacker). Hence my extra requirement that the two keys be chosen independently of each other. $\endgroup$ – Ilmari Karonen Oct 7 '20 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.