7
$\begingroup$

Alice sends Bob a message using AES-GCM. Bob is a software developer with just enough cryptography knowledge to be dangerous. He wants to start processing data as soon as he receives it. He observes that he can ignore the tag and just decrypt the CTR-mode ciphertext.

In every mode I can think of it is possible to decrypt a message without performing the authentication part. Does there exist a standard or named mode of operation that makes it impractical to try to skip or defer authentication?

It seems like such a scheme would necessarily be two-pass. It's fine if the first pass is always authentication and the second pass is decryption.


I had two (incomplete) ideas for how such an encryption scheme might work. I include their descriptions because it might aid to better explain the question asked above.

My initial idea involved first encrypting plaintext using an unauthenticated algorithm and random IV. Then the ciphertext would be fed to some kind of HMAC. The first 128 bits of HMAC output would become the message tag. The remaining bits would not be published and instead be used as a tweak for encrypting the IV.

(This prevents the recipient from decrypting the message without first performing the MAC algorithm because otherwise the IV remains unknown to the recipient. One issue is that the IV isn't authenticated.)

My second idea was to try adapting an all-or-nothing-transform, "an unkeyed, invertible, randomized transformation, with the property that it is hard to invert unless all of the output is known."

$\endgroup$
  • 2
    $\begingroup$ One problem that I see that any kind of calculation can be executed while the result of verification (true / false) can likely be ignored by the receiver. I don't see any way of altering a calculation by the choice of accepting or not accepting the ciphertext. $\endgroup$ – Maarten Bodewes Jan 30 at 22:22
  • 1
    $\begingroup$ @MaartenBodewes: I agree, although one can at least try to ensure that, if the recipient does accept an invalid ciphertext, it will almost surely decrypt into nothing but unpredictable gibberish. $\endgroup$ – Ilmari Karonen Jan 30 at 22:47
4
$\begingroup$

There is a type of AEAD construction, exemplified for example by the CAESAR candidate AEZ, which splits up into two components:

  • An enciphering scheme: "an object that is like a conventional blockcipher except that the plaintext’s length is arbitrary and variable, and, additionally, there’s a tweak" (p. 1).
  • An encode-then-encipher mode that enciphers the concatenation of a plaintext with a fixed number of zeroes (or some other alternatives). On decryption, the authenticity check verifies that these final bits deciphered to zero.

The key thing is that in the enciphering scheme, a change to any bit of the ciphertext (or plaintext respectively) has a 50% chance of affecting every bit of the plaintext (or ciphertext respectively). So attempts to modify a ciphertext will yield garbled plaintexts, and those garbled plaintexts will be safe to reveal.

$\endgroup$
  • 1
    $\begingroup$ Heh, I like that solution. You can decrypt, but if anything is altered, then you get garbled text. Is comparable to bi-IGE in function and / or in implementation? $\endgroup$ – Maarten Bodewes Jan 30 at 22:11
  • 3
    $\begingroup$ Does this actually solve the problem though? I could still just not check for zeroes. Yes it would be a lot harder to control what the decrypted value is, but I could still get you to continue with an invalid value. $\endgroup$ – Maeher Jan 30 at 22:14
  • $\begingroup$ That's an extremely good point, Maeher. I guess we need additional safeguards. $\endgroup$ – Maarten Bodewes Jan 30 at 22:15
  • 2
    $\begingroup$ @Maeher The program may indeed continue from that invalid value, but I would think that even in that case, as long as an attacker cannot infer anything useful from the garbling nor control it in any significant way, that's about the best you can do. If you ignore the authenticity check, then the decryption produces either the original plaintext or a pseudorandom string of the same length. $\endgroup$ – Luis Casillas Jan 30 at 22:48
  • $\begingroup$ @MaartenBodewes I don't know enough about bi-IGE to tell. Looking at this paper it seems like the question comes down to whether bi_IGE is a strong PRP for every message length. $\endgroup$ – Luis Casillas Jan 30 at 23:08
1
$\begingroup$

I upvoted the previous answer on AEZ, because I am a huge fan of AEZ, and I think you should read the theory paper on it, because it's an important paper on understanding a lot about symmetric cryptography. AEZ, which is a variable-size block, tweakable cipher. It's very, very close to an all-or-nothing transform. Block ciphers are all-or-nothing, for the size of the block. Simple AES will give you complete garbage if there's a single bit error in either the ciphertext or key. An all-or-nothing system can be thought of as a block cipher with an arbitrarily large block.

But the real answer to your real question is that even that doesn't solve the problem you're mentioning. That problem is willful, criminal stupidity in a programmer. The person who values performance over correctness has long been a source of problems.

If Bob in your example was using a perfect all-or-nothing transform and didn't check the error, it would be bad. Arguably, just as bad. If Bob doesn't check other return codes, it's bad. If Bob is arbitrarily stupid, then we need to avoid his software as you can fix a bug but you can't fix stupid.

A good AEAD API will do something right, and return to Bob an error message (and no data). Inside that API, it may very well be decrypting as it goes along so as to reduce a timing side-channel. Bob should use that API.

Okay, mini-rant over. As cryptographers, we should consider things that make it easy for programmers to do the right thing. I'm glad you're considering that, because we should. Look at AEZ, as I think the principles in it are what you want, and the theory paper on it. A large-block, tweakable cipher is almost exactly what you want.

$\endgroup$

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.