# CCA secure or not?

Let $F : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ be a PRF. And let the encryption function be $Enc{_k}(m) = r || (F{_k}(m) \bigoplus r \bigoplus 0^n)$ , where r's value is random. Is this system CCA secure?

I am having trouble deciding this. Since r's length is m(otherwise I wouldn't be able to XOR it with $F{_k}(m)$ I can just split the encrypted message into 2 equal parts, let's say L1 and R1. Then L1 would be equal to r and R1 would be $F{_k}(m) \bigoplus r \bigoplus 0^n$ . Now I know r , $0^n$ doesn't impact my XORING so I am left with $F{_k}(m)$. How can you decide if a random function is CCA secure.

Also I am aware that I might have started on the wrong thought process. Can someone please explain to me the thought process behind deciding if this is CCA secure or not? The answer seems to be obviously not but why?

• I do not understand how decryption could be done, or what $\bigoplus0^n$ is supposed to achieve. Is there a typo somewhere?
– fgrieu
May 16, 2015 at 16:52
• nope this is actually the exercise... you can view the image of it here i58.tinypic.com/5n0nrc.png May 16, 2015 at 16:53

As fgrieu already said, the question is a bit weird. The encryption scheme is not complete in a very strong sense, as there exists no efficient algorithm that can recover $m$ from a ciphertext.
First, we note that indeed $\oplus 0^n$ changes nothing about the ciphertext and can be disregarded and since $r$ is part of the ciphertext, it is possible to recover $F_k(m)$, which is deterministic, since $F$ is a PRF and thereby deterministic. Thus, we get an easy attack as follows:
Choose two random messages $m_0, m_1 \in \{0,1\}^n$ with $m_0 \neq m_1$ and output them as the challenge messages and receive back the challenge ciphertext $c^*=r^*\Vert x^*$. Now query the encryption oracle with $m_0$ and get back the ciphertext $c_0=r_0\Vert x_0$. If it holds that $x^*\oplus r^* = x_0 \oplus r_0$, then output $0$, otherwise output $1$. It is trivial to see that this attack is successful with probability $1$.
This all being said, it seems reasonable to assume that there is a typo in the problem statement and the encryption scheme is supposed to be $Enc{_k}(m) = r || (F{_k}(r) \oplus m)$.