4
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ $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)$. $\endgroup$
    – BiggBen1989
    Oct 28, 2012 at 18:37
  • $\begingroup$ 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? $\endgroup$
    – BiggBen1989
    Oct 30, 2012 at 0:23
  • $\begingroup$ @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 $\endgroup$
    – Hendrik Brummermann
    Oct 30, 2012 at 11:29
  • $\begingroup$ 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...) $\endgroup$
    – Ilmari Karonen
    Oct 30, 2012 at 13:17
  • $\begingroup$ @IlmariKaronen, there is, but I forgot to select the checkbox. Sorry. $\endgroup$
    – Hendrik Brummermann
    Oct 30, 2012 at 20:35
2
$\begingroup$

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.

Improve this answer
$\endgroup$

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.