13
$\begingroup$

I have implemented a simple encryption/decryption program based on AES-256 in CBC mode1.

Actually, it is more precise to describe it as a compression+encryption / decryption+decompression program.

If one provides the wrong key to the decryption+decompression function, the decompression stage will explicitly fail, as expected, since the decrypted content (being based on the wrong key) will be just noise.

I would like to modify the decryption phase of the scheme so that it detects on its own that the wrong key has been used, before it proceeds to the decompression phase. I am looking for a scheme to support this functionality that does not weaken the overall cryptographic strength of the framework.

A naive approach would be to generate the encrypted content as2

AES256_CBC(key, iv, SENTINEL_STRING + plaintext)

where SENTINEL_STRING is a string that the decryption phase can know in advance. While I am being naive about it, I could make the SENTINEL_STRING be equal to the key, for example.

I imagine there are pretty standard ways to solve this problem. In fact, for all I know, the design of AES-256-CBC already has built into it a way to check that decryption succeeded.

I hope someone can enlighten me on these matters.

Also, if this problem is common enough to have a generally accepted name (suitable as search engine fodder) please let me know.


1 For what it's worth, my current implementation of this uses Python's pycrypto module, but an earlier implementation used Perl's Crypto::CBC package. Both versions can reciprocally decrypt+decompress files compressed+encrypted by the other. I bother mentioning all this to stress the fact that this question is primarily about AES-256-CBC in general, and not about any specific implementation of it.

2 I hope my ad-hoc notation here is not too stupid. I mean it as a shorthand for "encrypt the string SENTINEL_STRING + plaintext with AES-256 in CBC mode, using the key key and initialization vector iv".

$\endgroup$
  • 2
    $\begingroup$ CBC mode is vulnerable to padding oracle attacks and it is removed in TLS 1.3. In TLS 1.3, we have only Authenticated Encryption (AE) modes like AES-GCM and ChaCha-Poly1305. It better to switch since AE gives you not only confidentiality but also integrity and authentication. $\endgroup$ – kelalaka Aug 18 at 8:56
  • $\begingroup$ Your search engine fodder is "authenticated encryption." Also: (a) you should not be using CBC at all; (b) you really ought to read a modern crypto book first, I recommend Aumasson's Serious Cryptography. $\endgroup$ – Luis Casillas Aug 20 at 18:41
34
$\begingroup$

You should use an authenticated encryption mode. There are several reasons for that, but one (relatively minor) one is that it automatically gives you the ability to detect incorrect keys, since the authentication will fail.

If you insist on using a traditional non-authenticated encryption mode, or if you'd like to have some way of distinguishing "incorrect key" from "corrupted ciphertext", you can include a key check value together with the ciphertext, and verify it before attempting decryption. There are several possible ways to implement one.

A traditional method is to encrypt an all-zero block using the raw block cipher (i.e. "ECB mode") and use the resulting ciphertext as the key check value, but note that this makes it possible for an attacker to tell whether two messages have been encrypted using the same key by comparing the key check values. Alternatively, assuming that you're using an authenticated encryption mode anyway, you could just generate the key check value by encrypting an empty message using the same mode. Assuming that you're using a unique nonce / IV for each encryption, as you should be, this should eliminate the information leak by making every key check value also unique.


(BTW, note that compressing data before encryption can leak (extra) information about the plaintext. Basically, this happens because all general-purpose encryption schemes necessarily leak information about the length of the plaintext, and compression makes the plaintext length depend on its content. Padding reduces this leak slightly, but does not eliminate it. This has been used in actual attacks.)

$\endgroup$
  • 1
    $\begingroup$ @kjo: That's one situation where authenticated encryption might not be necessary. That said, I would recommend using it anyway, since it costs you basically nothing. As for using the encrypted IV/nonce as the key check value, I wouldn't recommend that without careful analysis, since for some encryption modes (including, notably, CBC) revealing the encrypted nonce leaks the first block of the plaintext(!). That said, e.g. encrypting a (possibly truncated) hash of the nonce should be safe, as should hashing the block cipher output and using that as the key check value. $\endgroup$ – Ilmari Karonen Aug 18 at 11:53
  • 1
    $\begingroup$ (Actually, if you have a cryptographic hash function available, as you probably do, simply concatenating the key with the nonce and hashing the result should make a fine key check value.) $\endgroup$ – Ilmari Karonen Aug 18 at 11:54
  • 2
    $\begingroup$ @kjo: It probably isn't. The situations where I know of it having been exploited are ones where either secret data is combined with data an attacker can control before being compressed and encrypted (as in the CRIME/BREACH attacks on HTTPS) or where the data is split into small segments in a way that allows the length of encrypted segments to leak information (as in the attacks on encrypted live voice chat). Your scheme doesn't look like either of those, but of course that doesn't prove that the leak doesn't matter. $\endgroup$ – Ilmari Karonen Aug 18 at 13:48
  • 2
    $\begingroup$ You could use the master secret to calculate two secrets using a KDF with a specific info string (and possibly even an included salt), and then include the output of one secret. That's, in my opinion, better than the original key check value, which is just dangerous (e.g. when combined with CTR mode and a counter of zero). Actually, the original KDF only has the advantage that you don't need to perform any other operations than encryption with the key (which means it also works for e.g. 3DES where the parity bits may differ). $\endgroup$ – Maarten Bodewes Aug 18 at 22:06
  • 2
    $\begingroup$ You derive one encryption key and one key check value using two iterations of a KDF, e.g. one with label "ENC", and one with label "KCV". The label is just additional information included in the KDF calculation. You can then check the KCV before you decide to decrypt, if you keep it with the ciphertext. There are relatively easy KDF constructs that can be created using a hash function, but nobody would fault you from using a single hash call as long as your input is well defined (statically sized). $\endgroup$ – Maarten Bodewes Aug 20 at 10:23
3
$\begingroup$

Ilmari Karonen already mentioned using an authenticated encryption mode, which would solve the concerns, but should you not go that way, please note the flaw in your premise:

If one provides the wrong key to the decryption+decompression function, the decompression stage will explicitly fail, as expected, since the decrypted content (being based on the wrong key) will be just noise.

Pretty much any wrong key or change in the ciphertext will decrypt to something which is not valid for the decompression algorithm you used, and that it will detect (and hopefully your program will detect that error). But that isn't guaranteed.

A trivial solution would be to include an HMAC/hash of the plaintext/compressed content, which would allow you to validate that you decrypted the right content.

This is even more important taking into account that your use case is long-term storage. I wouldn't be surprised if it was possible to truncate one such file at the right boundary that it was unnoticed not only by the AES-CBC but also by the underlying compression function. Just adding a key-check value won't detect that issue.

Since you are aiming for storage, it probably won't matter for you, but note that if this was used in eg. an online protocol, detecting decompression errors would provide an oracle to an attacker that sent your decrypter multiple corrupted blocks, based on the difference of time it needed for processing it.

$\endgroup$
  • 1
    $\begingroup$ I guess that depending on the modes of failure that including a MAC and a key check value (or separate KDF value as KCV, see my comment below Ilmari's answer) would be a good idea. As indicated, a KCV is to detect if the key is correct or not, the MAC if the integrity of the data is preserved (although, of course, the KCV can also be altered in some situations). $\endgroup$ – Maarten Bodewes Aug 18 at 22:25
  • 1
    $\begingroup$ @MaartenBodewes I am presenting why the OP should care about an integrity check. kjo may wish to add that plus a KCV. Actually, I am not sure what exactly drives his need of such check, which would influence what to check and where. Personally, I would probably add a 1.byte of the password hash, similarly to the zip format, thus we are only giving out a tiny bit of information on the password itself, requiring bruteforcing attempts to decrypt the whole file to test their guesses. $\endgroup$ – Ángel Aug 20 at 0:15
  • $\begingroup$ OK, although I think the single byte is useful for transmitting the least amount of data. There is no need to decrypt a whole file to guess a password, even on most AEAD schemes; just decrypting a few blocks without verifying the authentication tag is enough. $\endgroup$ – Maarten Bodewes Aug 20 at 10:25
  • $\begingroup$ @MaartenBodewes: yes, in real scenarios, usually you know what kind of file or file is expected to be encrypted, and checking the first decrypted block for a known magic number would be enough (in the case of the OP the compression method used has probably a signature). $\endgroup$ – Ángel Aug 21 at 18:56
1
$\begingroup$

There is no way to detect the wrong key before decrypting: I can create a message M, a totally valid and legitimate key K, and then I encrypt the message with a different key K': Any information that I give you about the key K will be totally legitimate and fine, it will just not be about the key I used to encrypt the message.

You can try to include additional information, but whatever you ask for, I can supply you with information that would be correct with the key K, and then use the key K'.

I can even start encrypting using K, encrypt 90% of the message that way, and use K' for the remaining 10%. So there is no way to detect an incorrect key other than decrypting the complete message, and checking that the decrypted message is valid.

$\endgroup$
  • 2
    $\begingroup$ That's true, but it is possible to safely distinguish between "this message might be valid, but clearly not encrypted with this key" and "at least a part of this message has been encrypted with this key, but the rest is invalid" without having to process the full message in the first case. This distinction can be useful if you expect the receiver to sometimes attempt decryption with the wrong key (e.g. because they mistyped the passphrase the key was derived from) even in the absence of any malicious attacks, and if verifying the full message just to catch a typo may be undesirably slow. $\endgroup$ – Ilmari Karonen Aug 18 at 21:35
  • 1
    $\begingroup$ True, and it may be very useful if only part of the message is received. I had to show why signature verification failed on message that was cut in two, but I had to process the whole file for that (I told them that a separate FTP process could not indicate that the file upload was finished, sigh). $\endgroup$ – Maarten Bodewes Aug 18 at 22:09

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.