# 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.
• $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. $\;\;$ – user991 Oct 28 '12 at 20:12
• @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