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?

  • 1
    $\begingroup$ 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? $\endgroup$
    – Seth
    Sep 29, 2015 at 3:36
  • 1
    $\begingroup$ If the MAC is deterministic it will produce identical tags for identical messages, thus leaking if they're the same. $\endgroup$ Sep 29, 2015 at 20:30

1 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?)".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.