How can a Encrypt-And-MAC scheme be insecure if the encryption is CCA secure?

Question

I was presented with this seemingly paradoxical information, and am hoping someone can explain what I'm missing here.

I have an encrypt-and-mac scheme here.If I want to transmit message m to Bob, I'd first Enc_k1(m) = c, MAC_k2(m) = t, and then send c||t over to Bob. So far, I understand that this scheme provides no integrity on the cipher-text itself, since the tag only verifies the original message and nothing else.

However, I am also presented with that Enc_k1 is CCA secure.

And then I was told that the Enc-and-MAC scheme is NOT CCA secure.

How can this be? If the encryption itself is CCA secure, the only way the scheme is not CCA secure is if and only if the MAC is not CCA insecure, but I have no idea if that even makes sense.

If it is possible, how can an attacker provide a possible CCA attack?

Answer 1

Note that the security notion targeted by MACs is not IND-CCA, but EUF-CMA (Existentially Unforgability against Chosen Message Attacks). You can read the formal definition on page 156 here: https://cseweb.ucsd.edu/~mihir/papers/gb.pdf.

Suppose we have a MAC scheme $M =(\mathcal{K}, \mathsf{MAC}, \mathsf{VF})$ which is EUF-CMA secure. Let's create another MAC scheme $M' = (\mathcal{K}, \mathsf{MAC}', \mathsf{VF}')$ which is still EUF-CMA secure, but which provides absolutely no privacy of the message. It is defined as follows:

$$\mathsf{MAC}'_K(m) := m || \mathsf{MAC}_K(m)\\ \mathsf{VF}'_K(m, t) = \mathsf{VF}'_K(m, m' || t') := \text{return 1 iff } m = m' \text{ and } \mathsf{VF}_K(m, t') = 1.$$

I leave it to you to prove that $M'$ is EUF-CMA secure. However, what can you say about the security of your combined scheme with $M'$ as the MAC function?

If you are interested in learning more about the E&A mode and the security of generic composition in general (i.e., EtA vs AtE vs E&A), then the standard reference is: "Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm " - containing full proofs and counter-examples. For more on AtE and E&A in particular, look at "The order of encryption and authentication for protecting communications (Or: how secure is SSL?)".