Why is a MAC needed with CBC?

Question

I agree that for certain encryption systems or modes of operation, a MAC is indispensible.

The best example are probably stream ciphers (and therefore also block ciphers in OFB or CTR mode) that allow an attacker to arbitrarily flip bits in the ciphertext, resulting in flipped bits at the same position in the plaintext after decryption.

However, I somehow always thought that that wouldn't apply to "modern" block ciphers in some reasonable mode of operation, e.g. AES-CBC. Since there is no clear relation between a bit in the ciphertext and a bit in the plaintext, I thought that any small modification would cause a totally different plaintext.

That in mind, I thought it would be enough to simply concatenate the plaintext with some simple checksum to check for that kind of tampering; a cryptographic hash didn't even seem necessary to me.

But in reality, pretty much every reasonable application of AES-CBC also seems to be using MACs, so I'm almost certain that there is an error somewhere in my reasoning.

Answer 1

To see why CBC mode still needs a MAC to guarantee message integrity, first recall how CBC mode decryption works:

$$P_i = D_K(C_i) \oplus C_{i-1}$$

Here, $D_K$ denotes block cipher decryption using the key $K$, and $C_i$ and $P_i$ denote the $i$-th ciphertext and plaintext blocks respectively.

Now, consider what happens if you modify the encrypted message to replace $C_i$ with $C_i' = C_i \oplus X$ for some $i$. Now, the corresponding plaintext block $P_i'$ will be garbled, since $D_K(C_i')$ will in general bear no predictable resemblance to $D_K(C_i)$. However, the next plaintext block $P_{i+1}'$ will now become

$$P_{i+1}' = D_K(C_{i+1}) \oplus C_i' = D_K(C_{i+1}) \oplus C_i \oplus X = P_{i+1} \oplus X.$$

Thus, even with CBC mode, you can still flip arbitrary bits in any given plaintext block, provided that you don't mind the previous plaintext block being garbled. Whether this is actually practical depends on the what the plaintext is supposed to be, but it's generally not safe to assume that it isn't.

Of course, since the garbled block will, in general, be essentially random and unpredictable by the attacker, it might seem plausible that a simple non-cryptographic checksum could detect such modification. However, it's not entirely implausible for the attacker to be able to predict $D_K(C_i')$, and thus $P_i'$: for example, if the attacker has access to some known ciphertext/plaintext message pairs, this provides them with a bunch of blocks whose image under $D_K$ is known. If they choose $C_i'$ to be one of such blocks, they'll be able to predict $P_i'$, and if they can also guess the original plaintext block $P_i$, they may be able to spoof many non-cryptographic checksums.

(In particular, if the IV is sent alongside the message — as is usually done — flipping bits in the first plaintext block is particularly easily done just by flipping the corresponding bits in the IV. Thus, for the first block, CBC mode is just as malleable as CTR or OFB.)

The bottom line of all this is that, if you want to protect the integrity of your messages, you need to use an encryption mode that is actually designed to be provably non-malleable. In addition to the generic combination of a classical block cipher mode and a MAC, there also exist several authenticated encryption modes specifically designed for this purpose.

Answer 2

In addition to what mikeazo and Ilmari mentioned, there are also several chosen-ciphertext attacks on various modes of operation, which do not only endanger the message integrity, but also the message privacy, when no message authentication is used.

For example, such attacks on CBC mode were used to break the XML Encryption Standard, by analyzing the error messages from the receiver for various slightly modified versions of captured messages. With a MAC, these "forged" messages would not have been passed to the decryption algorithm (or the XML interpreter behind this) at all, but rejected due to a false MAC.

Answer 3

There are a few reasons for this.

One is for protocol flexibility. Many modern protocols support various modes (including streaming modes, which you already get why they need a MAC) and various configurations. One such configuration many support is integrity protection only. If you did something like what you propose, integrity protection only would have to be very different from a confidentiality+integrity protection configuration. Using the MAC in both cases makes the two different configurations very similar, thus leading to more code reuse, etc.

Another reason is for ease of analyzable/provable security. For example, "any secure channels protocol designed to work with any combination of secure encryption (against chosen plaintext attacks) and secure MAC must use the encrypt-then-authenticate method." Proving a statement like this (as is done in the linked paper) is important as it makes the life of cryptographic protocol designers much simpler. They don't have to prove that their specific way of doing things is secure if they use a generic construction that was already proved to be secure.