# Prove that the following private-key encryption scheme is not CPA-secure

Consider the following private-key encryption scheme : The shared key is k $\in$ {0,1}n. To encrypt the message m $\in$ {0,1}n, choose random r $\in$ {0,1}n and output $(r, F_r(k)\oplus \overline{m})$, where $F$ is a block cipher and $\overline{m}$ is the bit-wise compliment of m. Is this scheme CPA secure?

What is the importance of bit-wise compliment in this question?

Also, it does seem that the scheme is CPA secure because one is performing a $\oplus$ of a message string and a random string (it would change for every message as we pick a random r for each m)

## 2 Answers

As aventurin pointed out, the scheme as written is not CPA secure.

As poncho's comment pointes out, it is not even secure against known plaintext attacks:

Knowing any pair $(m,c)$ with $c = (c_1,c_2) = (r,F_r(k)\oplus \bar{m})$ gives the attacker $k$ directly:

$$k = F^{-1}_{c_1}(c_2 \oplus \bar{m})$$

What is the importance of bit-wise compliment in this question?

Nothing. Bitwise complement is a fixed bijective mapping, which everyone can evaluate on every input and in either direction. With regards to security, (in this context) this is as useful as the identity function.

In the comments you wrote:

.. $F$ being an OWF ... PRF, apologies ...

In the original question $F$ was a block cipher. If we consider $F$ as a PRP (common model for block ciphers), the above still holds: An attacker on a PRP usually gets an oracle for both $F(x)$ and $F^{-1}(x)$.

However, if we assume a PRF the attacker does not get the oracle for $F^{-1}$, so the above attack doesn't work any more. But the construction can not be reduced to the security definition of a PRF either: Usually you would assume an attacker for your scheme and then show that this attacker could also break the PRF property. But:

• In the PRF game, the attacker is allowed to query the function on arbitrary input $x$ for $F(x)$. The answer is always either from a truly random function or $F_k(x)$ for a fixed $k$.
• In your scheme the attacker could request multiple ciphertexts for the same $k$, but that would result in multiple queries of the form of $F_r(x)$ with $x = k$ fixed.

That just does not fit, and it's unlikely we could prove or disprove the claim - without making further assumptions.

If we consider $k$ and $x$ as two inputs to the function and the random function just doesn't use $k$, then the stanard PRF only allows queries on the second input. What you need in your case would be a dual PRF, where the attacker is given oracle access to changes in both inputs. You can find more information about this:

• Thank You for the detailed explanation. I asked the Professor and it turns out that it was indeed a block cipher - which is a PRP. I had wrongly assumed that a block cipher is based on a PRF, as in his lecture, he'd taught modes of operation just right after PRFs. Mar 13 '17 at 20:45

If you choose $m = (1, \ldots, 1)_n$ then

$$(r, F_r(k) \oplus \overline{m}) = (r, F_r(k) \oplus (0, \ldots, 0)_n) = (r, F_r(k))$$

what reveals $k$.

• Actually, this works as a known plaintext attack Feb 8 '17 at 23:35
• Does this mean that we have to try all possible combinations of n bit strings and see which one gives $F_r(k)$ (and since n is small, this is possible)? Feb 9 '17 at 7:07
• If I understand the formula in your question right, we have $r$ and $F_r(k)$ in the output, whereby $F_r(k)$ is the shared key encrypted with the random value $r$. Therefore you can use $r$ to decrypt $F_r(k)$ and get $k$. Feb 9 '17 at 16:31
• 'r to decrypt $F_r(k)$' - We know r, We know $F_r(.)$ - i.e. whatever input we give to the function $F$ with the key $r$, we'll get the output. And $F$ being an OWF, need not be invertible. So to get the shared key $k$, the only way is to perform $F_r(({0,1})^n)$ and see which of these is equal to $F_r(k)$. But isn't this exponential in $n$ - There would be $2^n$ combinations to try out. Or is there any other way? Feb 10 '17 at 5:04
• You wrote that $F$ is a block cipher. So I assumed that it could be inverted. Feb 10 '17 at 21:34