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

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?

• Is this homework? Some things to consider: What happens if a message is repeated? Can you construct a MAC that is unforgeable under a chosen message attack, but that leaks information about the input?
– Seth
Sep 29 '15 at 3:36
• If the MAC is deterministic it will produce identical tags for identical messages, thus leaking if they're the same. Sep 29 '15 at 20:30

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?