# How to prove an encryption scheme is not CCA secure

Given the following context below, how does one show or prove the encryption scheme is NOT IND-CCA secure

The IND-CPA secure private-key encryption scheme for n-bit messages can be constructed from a pseudorandom function as follows $$F : \{0,1\}^n \times \{0,1\}^n → {0,1}^n$$ as follows:

• $$Gen(1^n)$$: Return $$k ← \{0,1\}^n$$
• $$Enc_k(m)$$: Pick $$r ← \{0,1\}^n$$ and compute $$s = m\oplus F_k(r)$$. Return $$c = (r,s)$$.
• $$Dec_k(c)$$: Parse $$c$$ as $$(r,s) \in \{0,1\}^n \times \{0,1\}^n$$ and return $$m = s\oplus F_k(r)$$.

How would one prove that this is NOT IND-CCA secure?

• Hint: What happens if you modify a ciphertext? – SEJPM Aug 18 '19 at 6:10

Let $$\Pi$$ denote the encryption scheme you just described, and $$\mathcal{A}$$ be the adversary trying to attack this scheme.

Define the experiment $$\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A}, \Pi}$$ as follows:

1. $$\mathcal{A}$$ has access to the encryption oracle $$E_k(\cdot)$$ and the decryption oracle $$D_k(\cdot)$$.
2. $$\mathcal{A}$$ outputs two messages $$m_0$$ and $$m_1$$.
3. A uniform bit $$b$$ is chosen, unknown to $$\mathcal{A}$$. $$\mathcal{A}$$ is given $$c=E_k(m_b)$$.
4. $$\mathcal{A}$$ is not allowed to query the decryption oracle on $$c$$. $$\mathcal{A}$$ however continues to have oracle access to both encryption and decryption.
5. $$\mathcal{A}$$ outputs bit $$b'$$. The result of the experiment is $$1$$, if $$b=b'$$, otherwise $$0$$.

So now, the scheme is considered CCA secure if the probability that the output of the above experiment is 1, is negligible. However, an adversary $$\mathcal{A}$$ could output $$m_0=0^n, m_1=1^n$$ and receive the challenge ciphertext $$c=(r,s)$$. It is not allowed to query $$D_k(\cdot)$$ on $$c$$. However, querying $$D_k(c') = D_k((r, s \oplus 0^{n-1}||1))$$ would return $$0^{n-1}||1$$ if $$c=E_k(m_0)$$, and $$1^{n-1}||0$$ if $$c=E_k(m_1)$$.

Depending on the result of the query, the output of $$\mathcal{A}$$ is equal to $$b$$ with probability 1.

• I request you to accept this answer if you feel it's explanatory. – Deepak K Aug 24 '19 at 15:39