18
$\begingroup$

Let's start by saying I'm no cryptography expert, I'm just a developer, so feel free to correct me (using words, not downvotes) if what I'm saying is non-sense.

Context: I'm doing some crypto as a service for embedded devices. Users of this service don't have access to any key. They're only able to tell the device "use the key <index> to encrypt/decrypt this".

According to the NIST (Chapter 7.2), when decrypting a cipher using AES GCM, if the tag is wrong, the cipher should not be returned :

if they are identical, then the plaintext is returned; otherwise, FAIL is returned

This raises two questions.

First: how bad is it to return the wrong plaintext anyway? (but still returning an error, it would be up to the user to check it). Is there any mathematical reason for that? Could an attacker somehow leak the key by trying to decrypt forged ciphers?

Second: if the answer to the first question happens to be "it doesn't matter whether you return the wrong plain or not" then this is not an issue anymore. But otherwise: our AES driver is written in C, how can we prevent the cipher from being returned in case the tag is wrong? As far as I understand, to compute the tag the decryption process must be done entirely. The thing is the destination buffer of the decrypted cipher is a shared memory a potential attacker could have access to. Having a temporary buffer to store the resulting plaintext in order to compute the tag is not considered as it would not fit the device memory.

$\endgroup$
14
  • $\begingroup$ I personally don't know about implementations but, but in case of security we usually consider powerful attackers (even if just theoretical but bad design or implementations of systems might make them of practical danger) trying weaker goals. So, it's not enough that you prevent attackers from getting the key, we should consider them to be trying CCA-2 type attacks. So, aside from trying to distinguishing the cipher, an attacker might try to forge the ciphertext. GCM is made to handle that. $\endgroup$ Apr 13, 2021 at 13:06
  • 6
    $\begingroup$ "The thing is the destination buffer of the decrypted cipher is a shared memory a potential attacker could have access to." As written, this means an attacker could just read this buffer to get the decryption result, whether or not the tag is correct. So encryption is useless, you need to ensure that attackers don't have access to the memory of your client devices. $\endgroup$ Apr 13, 2021 at 13:11
  • 1
    $\begingroup$ I've already mentioned that. CTR mode is Ind-CPA secure, shortly meaning that the attackers chosen-plaintext doesn't help them. $\endgroup$
    – kelalaka
    Apr 13, 2021 at 14:19
  • 3
    $\begingroup$ I highly recommend you read this analysis of the EFail attacks on PGP-encrypted email, because it's one of the best real-life examples of why it's important to (a) not release the decryptions of forged ciphertexts and (b) to encrypt large content as a sequence of individually encrypted and authenticated chunks. (How to do the latter is tricky, and I cannot explain in this space.) $\endgroup$ Apr 13, 2021 at 23:40
  • 2
    $\begingroup$ @LuisCasillas I was about to post the same thing. OP, please read this. The PGP devs did exactly what you suggested ("still returning an error, it would be up to the user to check it") and got screwed hard. Learn from PGP's fuckup. $\endgroup$
    – Navin
    Apr 14, 2021 at 2:18

5 Answers 5

16
$\begingroup$

There is an article* that answers the question in the negative for GCM and CCM. The article introduces the first formalization of the Releasing Unverified Plaintext (RUP) setting. The related security notion is the Ind-RUP.

The security question is can an adversary forge messages with unverified messages? In this game, confidentiality is not relevant, since in the game the adversary is accessing the plaintext of the chosen messages. AES-GCM fails to satisfies this.

AE schemes such as GCM [34] and CCM [49] reduce to CTR mode in the RUP setting. This is because the adversary does not need to forge a ciphertext in order to obtain information about the corresponding (unverified) plaintext.


Your questions:

  1. It is very dangerous. AES-GCM internally uses CTR mode and bit flipping is very easy in the CTR mode. An attacker can easily change the ciphertext bit on their advantage. This is catastrophic if the structure of the message is known.

    One must never ignore the tag invalid!

    It is not about the leak of the key, CTR mode is IND-CPA secure. It is about changing the messages. This is why CTR mode can't have IND-CCA. GCM provides integrity and authentication and authenticated encryption > IND-CCAs

  2. For the second part you may benefit from is Q/A which provides a solution for the limited chunks for the GCM;


Also for general guide


*Thanks to Squeamish Ossifrage for pointing the article.

$\endgroup$
2
  • 2
    $\begingroup$ Note that #1 means that plaintext oracles might also be possible, and that may in turn lead to leaking information to an adversary. E.g. have 0..2 to be valid numbers encoded into two bits. Now if there is an error after flipping the low order bit then the new value is 3, so the old value was 2, as otherwise no error would have been generated. $\endgroup$
    – Maarten Bodewes
    Apr 14, 2021 at 9:30
  • $\begingroup$ @MaartenBodewes Yes, it is possible, however, never heard in the wild. $\endgroup$
    – kelalaka
    Apr 14, 2021 at 14:27
12
$\begingroup$

how can we prevent the cipher from being returned in case the tag is wrong ? As far as I understand, to compute the tag the decryption process must be done entirely.

Actually, GCM decryption can be done in a two-step procedure:

  • Step 1: compute the expected GCM tag (which is a function of the ciphertext, AAD, teh secret H value, combined with the nonce and the key. Compare the expected GCM tag with the one that's included with the message (and fail if they're not the same)

  • Step 2: decrypt the message

Normally, steps 1 and 2 are done interleaved, but if someone monitoring the buffer is a concern, the above is a viable appproach.

$\endgroup$
10
  • 2
    $\begingroup$ You may also want to adress that it is a really bad idea to return the decrypted message anyways on tag failure (as then we're essentially back to CTR security and the authentication is worth much less). $\endgroup$
    – SEJPM
    Apr 13, 2021 at 13:19
  • 1
    $\begingroup$ Isn't the whole point of AES GCM to compute the tag and decrypt the cipher at the same time ? Why not use something like CBC + HMAC then ? $\endgroup$
    – ShellCode
    Apr 13, 2021 at 14:04
  • 1
    $\begingroup$ What you're saying would indeed solve our problem but at the expense of performance. It would require us to send the ciphertext twice to the hardware (which we would like to avoid). $\endgroup$
    – ShellCode
    Apr 13, 2021 at 14:07
  • 1
    $\begingroup$ @ShellCode: hardware? I thought you mentioned you were doing it in C? $\endgroup$
    – poncho
    Apr 13, 2021 at 16:52
  • 1
    $\begingroup$ If the destination buffer is read-only to an attacker then you can store the information still encrypted upon receipt while calculating the authentication tag, then provide the device with an error or not, and then upon request decrypt parts of the ciphertext. This won't work if the buffer is writable as well, as an attacker could perform bit flips changing the plaintext message and maybe perform plaintext oracle attacks. You could also split up and reencrypt in smaller parts, but yeah, that's going to be expensive as well. $\endgroup$
    – Maarten Bodewes
    Apr 14, 2021 at 9:50
6
$\begingroup$

There are several reasons for an authenticated decryption (with AES-GCM or any other AE or AEAD mechanism) not to return any plaintext if the ciphertext is not authentic (i.e if the tag does not match).

One danger is if the calling code starts using the partially decrypted plaintext. Suppose the caller does something with the beginning of the plaintext, then learns that the ciphertext was not authentic. The caller must then undo whatever was done, since this could be entirely spurious. Undoing what has been done is not always possible: if you've already sent a message over the network, you can't unsend it. If you've created a file, you can remove it, but traces of the data may remain in storage.

Furthermore, the way in which the code reacted to the partially decrypted plaintext may have indirect characteristics that are useful to an attacker. Side channels in the response to the partially decrypted plaintext may reveal parts of this plaintext to an external observer. This can happen with authentic plaintext, of course, but the situation with non-authentic plaintext is worse. If the plaintext is authentic, you know that it was created by a trusted party, and that usually means that it is well-formed in some sense. If the plaintext is not authentic, it may be ill-formed: it may contain numbers that are out of range, strings with invalid content, etc.

There are further problems if the entity that requests the decryption is doing it on behalf of a client. That is, suppose that Alice processes messages from clients, and the first thing the client does is submit an access token which is protected by (for example) AES-GCM. The first thing Alice does is to decrypt the token, and she reads that the token contains Bob's identity, so she starts reading the information she has on Bob and revealing some of it to the client (because after all why would you prevent Bob from retrieving information about himself?). But the token was actually produced by Eve, who can't create a valid token for Bob (because she doesn't have the key shared between Bob and Alice). And so Alice started to reveal Bob's information to Eve, which she will realize once she gets to the end of the ciphertext and learns that the token was not authentic.

To avoid these problems, you must not start processing the content of an authenticated-encrypted message until you have verified its authenticity. Ideally, this is enforced at the level of a cryptographic API, which either returns the authentic plaintext or a failure code. Sometimes, this is not possible, for example on an embedded system that must decrypt a message that doesn't fit in RAM. In such cases, the layer that processes the partially decrypted plaintext must not look inside the content: all it may do is store it temporarily in a secure place. Effectively, that layer becomes part of the cryptographic processing code, and it must take care not to leak unauthenticated plaintext to its caller.

If the job of the intermediate layer is to reveal the plaintext to an untrusted caller (for example, if you're writing code in a secure enclave), then the intermediate layer must take care not to reveal any unauthentic plaintext. If you do reveal unauthentic plaintext, you're allowing your caller to decrypt arbitrary data, and not just the messages that it may be entitled to.

If your intermediate layer doesn't have enough memory to store the not-yet-authenticated decrypted plaintext, one possible trick is to encrypt it on the fly with an unauthenticated cipher, then have it decrypted.

  1. Generate a single-use key K₁ for an unauthenticated cipher, for example AES-CTR.
  2. For each chunk of the ciphertext:
    1. Perform a chunk of authenticated decryption, putting the result in secure memory. (By “secure memory”, I mean memory that belongs to your intermediate layer, and that is not shared with your untrusted caller.)
    2. Encrypt the result with the stream cipher, putting the result in shared memory.
  3. Verify the authenticity of the authenticated ciphertext.
    • If it isn't authentic, erase K₁. The untrusted caller has data encrypted with K₁ but does not have K₁, so it can't do anything with that data.
    • If it is authentic, reveal K₁ to the caller. In practice, you might as well do the decryption (this is often preferable for performance since your layer is typically closer to any possible hardware acceleration, but sometimes the situation is the other way round if your code is running in a secure enclave which has less good performance than the untrusted caller). The caller may have modified the shared memory, but doing the decryption of modified data doesn't give the caller any advantage, since we're willing to reveal the key anyway.
$\endgroup$
6
$\begingroup$

Is it acceptable to return the wrong plaintext if the tag is incorrect?

No. For one, it's against the spec quoted in question.

How bad is it to return the wrong plaintext anyway?

It's bad at least because if the AES-GCM API returned the wrong plaintext, then the software on top of the API might unwillingly use that wrong plaintext, just ignoring that it's wrong.

There is no risk to leak the key itself. But abusing such an invalid decryption API can let one encipher-and-authenticate arbitrary messages of their choice, which is typically not wanted.

Our AES implementation is written in C, how can we prevent the cipher from being returned in case the tag is wrong ?

Nothing beyond code obfuscation if adversaries can modify your code. If they can't, and can't inject fault, then it's enough to write correct code, and validate it. If there remains only the issue of fault injections, there are techniques to mitigate that, e.g. performing security checks twice at different times.

$\endgroup$
2
  • $\begingroup$ And what if we just put zeros in the output buffer if the tag is wrong ? It doesn't prevent an attacker from getting the decrypted cipher but it prevents API misuse. $\endgroup$
    – ShellCode
    Apr 14, 2021 at 9:35
  • 2
    $\begingroup$ @ShellCode: that modification fully solves the "invalid decryption API can let one encipher-and-authenticate arbitrary messages of their choice" issue; changes "software on top of the API might unwillingly use that wrong plaintext" to "software on top of the API might unwillingly use all-zero plaintext" (a different evil, lesser in a number of cases); and leaves "against the spec" unchanged. $\endgroup$
    – fgrieu
    Apr 14, 2021 at 9:47
3
$\begingroup$

Just an additional point of information from the field. The NIST spec is strict in not allowing this, and it has good properties if an API does not do this. For example it protects against naive usage of the API which streams partial responses to some processing code which might execute commands or reveal timing information in side channels. However the biggest drawback is, that the data must be buffered completely by the decryption function. This either means you always have to provide large input buffers or the API has to allocate and double copy data. It also means larger segments become hard to process.

This issue becomes relatively apparent in the Java Crypto Extension: when you use the OpenJDK and formerly Oracle implementation which does the required buffering you are compliant but might have performance impact. If you use the BouncyCastle implementation you get a faster streaming API but you must be aware the authentication is only checked when reading the last byte.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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