# Why is an Encrypt-and-MAC scheme with deterministic MAC not IND-CPA secure?

I'm preparing myself to exam, but I have a lot of troubles with rigorous proofs. It's the task from two-years ago exam. At the bottom I reminded one definition.

Let $(Gen_E,Enc,Dec)$ be an IND-CPA-secure encryption scheme.

Let $(Gen_M,Mac,Vrfy)$ be a secure MAC.

Define an encryption scheme as follows:

• $Gen'$ upon input $1^n$, generates $k_1 \leftarrow Gen_E(1^n), k_2 \leftarrow Gen_M(1^n)$,

• $Enc'$ upon input key $(k_1,k_2)$ and message $m \in \lbrace 0,1 \rbrace^*$, computes $c=Enc_{k_1}(m)$ and $t=Mac_{k_2}(m)$ and outputs $(c,t)$.

• $Dec'$ upon input key $(k_1,k_2)$ and ciphertext $(c,t)$, outputs $Dec_{k_1}(c)$ if $Vrfy_{k_2}\left( Dec_{k_1}(c),t \right)=1$ and outputs $\perp \not\in \mathcal{M}_n$ otherwise.

Prove that this construction is not even IND-CPA-secure when the Mac algorithm is deterministic.

Reminder (IND-CPA-secure).

An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$ is IND-CPA-secure if for any PPT adversary $\mathcal{A}$ it holds that $Pr[PrivK^{cpa}_{\mathcal{A}}(n)=1]-1/2$ is negligible function, where $PrivK^{cpa}_{\mathcal{A}}(n)$ denotes the output of the following experiment:

(a) Let $k \leftarrow Gen(1^n)$

(b) The adversary $\mathcal{A}$ is given input $1^n$ and oracle access to $Enc_k(\cdot)$. It outputs a pair of messages $m_0, m_1 \in \mathcal{M}_n$ of the same length.

(c) Let $b \in \lbrace 0,1 \rbrace$ be chosen uniformly at random. Then a ciphertext $c \leftarrow Enc_k(m_b)$ is computed and given to $\mathcal{A}$.

(d) $\mathcal{A}$ is given the challenge ciphertext $c$ and oracle access to $Enc_k(\cdot)$. It outputs a bit $b'$.

(e) The output of the experiment is $1$ if $b'=b$, and $0$ otherwise.

If you could help me with the rigorous proof, I'd be really grateful for your time.

-

I'm a little bit confused by your notation (what's $1^n$ supposed to mean? based on context, it looks like a key or a passphrase, but I've never seen that notation before), but the exercise itself seems to just amount to proving that an Encrypt-and-MAC scheme, using a deterministic MAC of the plaintext which is sent in plain, cannot be IND-CPA secure.

To prove that, keep in mind that there's nothing in the IND-CPA definition saying that the adversary cannot use the encryption oracle on the challenge messages. Since the MAC is deterministic and sent in plain, the adversary can just compare the MAC parts of two encrypted messages to determine (with very high probability) whether they encode the same plaintext.

-
$1^n = \underbrace{1 1 \ldots 1}_n$. The security parameter $n$ needs to be given to algorithms in the form of $1^n$ in order for algorithms to run in time bounded by a polynomial in $n$ instead of $||n||=\log_2(n)$. –  BiggBen1989 Oct 28 '12 at 18:37
@BiggBen: $\:$ It doesn't need to be given that way, it could be given to the $\hspace{1.5 in}$ algorithm as an arbitrary length $n$ string. $\;\;$ –  Ricky Demer Oct 28 '12 at 20:12
I think I do not understand some statements. What does it exactly mean, that "MAC is deterministic"? And if MAC parts of these two messages are equal? Could you help me with understanding how (un)likely is such event? –  BiggBen1989 Oct 30 '12 at 0:23
@BiggBen1989 "'Deterministic' simply means that, given the same input, the algorithm always produces the same output. That is, if $m=m'$ and $k=k'$, then $Mac_k(m)=Mac_{k'}(m')$. As for "the MAC part of the message", I simply meant $t$ in the output $(c,t)$ of $Enc'$. (Ps. I've flagged your (non-)answer for the mods to convert to a comment. Hopefully they can move my comment too, but if not, I can just repost it.)" by Ilmari Karonen –  Hendrik Brummermann Oct 30 '12 at 11:29
OK, thanks @Hendrik. :) I was kind of hoping you guys might have some handy "move comments" button to go with the answer-to-comment conversion feature, but I guess not. Thanks for going the extra mile, anyway. (Ps. I guess the two BiggBen1989's ought to be merged...) –  Ilmari Karonen Oct 30 '12 at 13:17

If you encrypt the same message twice, the MAC part will be identical in both cases. This violates semantic security (IND-CPA) and leads to an immediate distinguishing attack.

-