How to prove an encryption scheme is not CCA secure

Question

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?

Answer 1

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 \Big((r, s \oplus (0^{n-1}\|1)\;) \Big)$ 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.