Does there exist a mode of operation that forces mac-then-decrypt?

Question

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."

Answer 1

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.

Answer 2

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.