4
$\begingroup$

I have been stuck all day trying to understand how to show that an Encrypt-and-Mac ($SE_{EaM}$) scheme is not IND-CCA secure. I have seen this similar post, however it is slightly different and the notation in the selected answer confuses me.

The line of thought I want to follow is this: While the $MAC$ is perfectly UF-CMA secure it could still reveal information on the message since its computed directly from it and not the ciphertext (like in encrypt-then-mac). Consequently this would mean that $SE_{EaM}$ is not even IND-CPA secure, and therefore not IND-CCA secure. I want to know first if this line of reasoning is sound.

In terms of actually showing this, is it feasible to simply suppose that the $MAC$ scheme could afford no privacy to the message whatsoever. The post I referenced seems to have done that by adding the message in the clear to the actual tag ($t = m|t$), if I misunderstood I would appreciate clarification. If this is valid how could I use this in a IND-CPA game of $SE_{EaM}$?

I hope it will then become clearer how to show in a reduction that since IND-CCA implies IND-CPA, my $SE_{EaM}$ scheme is not IND-CCA. Or maybe I am looking at it completely wrong, in which case do let me know.

Thanks and happy new year!

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ The direction you are looking at works. Indeed IND-CCA implies IND-CPA so you can just break the CPA game. Another direction you can think about is that a MAC can be deterministic (in fact, most are). Try to think about the ramifications of that. $\endgroup$
    – Yehuda Lindell
    Commented Jan 1, 2018 at 6:17
  • $\begingroup$ Thanks for your answer. I thought about a deterministic MAC, say if $t = F_k(m)$, that would mean that identical messages would produce the same tags. In that case however can you still claim that a MAC scheme is UF-CMA secure? $\endgroup$
    – Nooby
    Commented Jan 1, 2018 at 19:42
  • $\begingroup$ Why not? Look at the definition of a MAC closely and you'll work it out. $\endgroup$
    – Yehuda Lindell
    Commented Jan 1, 2018 at 21:09
  • $\begingroup$ Yes I see. Then how would an IND-CPA game for an authenticated encryption scheme work, for instance what oracles would an adversary $A$ have access to, encryption or tag, both? and what rules exist? My understanding is that $A$ is meant to choose $m_0, m_1$, but I do not know if he may he have the ciphertexts and/or tags of both of these ready for comparison, say when receiving back a challenge ciphertext like this $c' = c(m_b)|t$, $t$ being sent in the clear and allowing for immediate comparison. $\endgroup$
    – Nooby
    Commented Jan 1, 2018 at 22:17
  • $\begingroup$ Search the literature; it's not hard to find. $\endgroup$
    – Yehuda Lindell
    Commented Jan 2, 2018 at 6:22

1 Answer 1

Reset to default
2
$\begingroup$

There is an excellent paper from Bellare and Namprempre that addresses the security properties of composite schemes in a rigorous and formal manner. Regarding IND-CPA security of Encrypt-And-MAC the paper has this to say:

E&M does not provide IND-CPA. E&M does not preserve privacy because the MAC could reveal information about the plaintext. This is true regardless of whether the MAC is weakly or strongly unforgeable. We provide details assuming that the MAC is strongly unforgeable below.

Let $\mathcal{MA = (K_m, T , V)}$ be a given MA scheme. We define an MA scheme $\mathcal{MA'}$ which is the same as the given one except that it prepends the first bit of the message to the tag. Formally $\mathcal{MA' = (K_m, T', V')}$ has the same key generation algorithm as the given MA scheme and the following tagging and verification algorithms:

Algorithm $\mathcal{T'(K, M)}$
Parse $M$ as $x||M'$ where $x$ is a bit
Return $x||\mathcal{T}(K, M)$

Algorithm $\mathcal{V'(K, M, \tau)}$
Parse $M$ as $x||M'$ where $x$ is a bit
Parse $\tau$ as $s||\tau'$ where $s$ is a bit
If $x = s$ and $\mathcal{V}(K, M, \tau') = 1$ then return $1$
Else return $0$

It is easy to see that if $\mathcal{MA}$ is SUF-CMA secure then $\mathcal{MA'}$ is SUF-CMA secure. However, if $\mathcal{MA'}$ is used as the base message authentication scheme in the E&M composition method, the resulting symmetric encryption scheme will not achieve IND-CPA because the first bit of the message is provided to the adversary via the MAC. The adversary can use this to break the scheme in the IND-CPA sense as follows. It queries its $\mathrm{LR}$ oracle with two messages $M_0$, $M_1$ such that the first bit of $M_0$ is $0$ and the first bit of $M_1$ is $1$. It gets back ciphertext $C = C'||\tau$ . It lets $s$ be the first bit of $\tau$ . As per our construction above, $s$ is the first bit of $M_b$ and hence $s = b$, so the adversary returns $s$. The advantage of this adversary is one.

In fact, we can make a stronger statement. Not only do there exist schemes for which the E&M method fails to provide IND-CPA, but it will fail to be so for most of the commonly defined MA schemes, including CBC-MAC and HMAC, because the latter are MACs. Indeed, an adversary can use the MAC present in the ciphertext of the composite scheme to see whether the same message has been encrypted twice, something which should not be possible if the scheme is to meet a strong notion of privacy like IND-CPA. This attack is successful regardless of whether the underlying MAC is weakly or strongly unforgeable.

E&M does not provide IND-CCA and NM-CPA. Since both IND-CCA and NM-CPA imply IND-CPA, the above means that E&M provides neither IND-CCA nor NM-CPA secure.

So your line of reasoning that you provided in your question is correct. We can use the fact that a MAC can leak information about the plaintext to break such a schemes IND-CPA security. Then, it follows that, since IND-CCA implies IND-CPA, a scheme that is not IND-CPA is not IND-CCA.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes I had come across this paper but did not want to copy it straight, wanted to instead come up with a different method in my answer. I am currently trying to devise such IND-CPA game, either for a mac tag that concatenates the message or a deterministic mac. Many thanks. $\endgroup$
    – Nooby
    Commented Jan 2, 2018 at 6:48

Your Answer

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

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