# How to show that a function is not a PRP?

So I have to answer these questions, but I honestly have no idea what I am doing or where to begin. Can I get some advice on how to tackle these?

Consider a PRP candidate function $f$ on $K = X = \{0, 1\}^n$ which is a permutation on $X$ for every key in $K$, but for all $k, x \in \{0, 1\}^n$, it satisfies $\operatorname{parity}(f_k(x)) = \operatorname{parity}(x)$.

1. Show that $f$ is not secure as a PRP.
2. Show that the CBC encryption mode with block cipher $f$ is not indistinguishable.
3. Show that the CTR encryption mode with block cipher $f$ is not indistinguishable.
• Review the statement. XOR requires 2 parameters at least. – Robert NACIRI Feb 18 '15 at 0:25
• I was told the following "XOR(x) stands for a function which takes an argument bitstring x and returns a bit which is a result of xor'ing all the bits of x.", but thought the same thing that XOR needs 2 parameters – Anon Feb 18 '15 at 0:27
• Yeah, It's more clear now. XORING all the bits gives in fact the parity bit. Then knowing the parity bit gives an advantage to an attacker. – Robert NACIRI Feb 18 '15 at 0:29
• How does knowing the parity bit help the attacker? – Anon Feb 18 '15 at 1:21
• @Anon What have you tried so far? Are you familiar with the definitions involved? – yyyyyyy Feb 18 '15 at 1:38

To show that a family of functions is not a PRP, you have to either show that the functions are not permutations or that they do not behave pseudo-randomly. As it is already established that the functions are in fact permutation you need to show the latter.

For a family of permutations to be a PRP means that it is computationally infeasible to distinguish a random member of the family (i.e. the function with a randmly chosen key) from a truly random permutation with non-negligible probability. So what you need to do is present an efficient distinguisher. I.e., describe an algorithm that can in fact decide whether it is given access to a member of the family or to a random permutation. To do that, you should consider the property that the parity of $f_k(x)$ is always equal to the parity of $x$. So for any fixed $x$ $$\Pr[\operatorname{parity}(f_k(x)) = \operatorname{parity}(x)]=1.$$ Now consider what the same probability is for a truly random permutation $g$. $$\Pr[\operatorname{parity}(g(x)) = \operatorname{parity}(x)]=??$$

Well, the definition of a PRP says that given an oracle access to either PRP or a truly random permutation the adversary cannot tell which permutation is behind it (i.e. random or pseudorandom). Formally, for every adversary $A$, for every positive polynomial $p$ and for the sufficiently large $n$'s ($n$ is the security parameter) it holds that: $| Pr[A^{f(\cdot)}(1^n)=1] - Pr[A^{F_k(\cdot)}(1^n)=1] | \leq \frac{1}{p(n)}$ ($F$ is the candidate PRP).

For the first question: Consider the following adversary $A$:

• $A$ set the flag $PSEUDO$ to true
• $A$ is given an oracle $O$ which is either $f(\cdot)$ or $F_k(\cdot)$
• $A$ asks its oracle $n$ queries, in each of them $A$ choose random bitstring $r$ of length $n$, and receive the oracle answer $a$.
• For each of the $n$ queries: $A$ knows $w_r=parity(r)$, and compute $w_a=parity(a)$. If $w_r\neq w_a$ then $A$ knows that this is not the pseudorandom permutation candidate and turn off the flag (i.e. $PSEUDO$=false).
• The attacker $A$ outputs its conclusion $1$ (i.e. that it deals with $F_k$ if $PSEUDO=true$, otherwise it outputs $0$ (i.e. $PSEUDO=false$).

Success analysis for $A$: first we can see that $Pr[A^{f(\cdot)}(1^n)=1]=\frac{1}{2^n}$ since if $A$ deals with a truly random permutation, the probability that in every answer, for different random queries, the parities $w_r$ and $w_a$ equal converges to $\frac{1}{2^n}$ (see note below). Also we can see that $Pr[A^{F_k(\cdot)}(1^n)=1]=1$ since it is obvious from the property of $F_k$ that the answer's parity is always as the query's parity ($w_r=w_a$), thus the adversary $A$ always outputs $1$. We conclude that: $| Pr[A^{f(\cdot)}(1^n)=1] - Pr[A^{F_k(\cdot)}(1^n)=1] |=1-2^{-n}$ which is obviously not negligible and thus the candidate is not a PRP.

note: If a truly random permutation is behind the oracle then for the $i$-th query the probability that $wr=wa$ is at most $\frac{2n−1}{2n−i+1}$ which asymptotically converges to $\frac{1}{2}$ and thus the probability for $n$ queries converges to $2^{−n}$.

For the second and third question, just take two messages with length of one block ($n$ bits), such that the first message's parity is 0 and the second's is 1, this way, when you receive an encrption of one of them you should know, by the parity of the ciphertext, which messsage has been encrypted.

• Choosing a "random bitstring of length $n$ and" setting its LSB to zero" will not necessarily $\hspace{.94 in}$ result in a string whose parity is zero. $\:$ (Consider 010.) $\;\;\;\;$ – user991 Feb 21 '15 at 19:01
• you right, I just noticed that parity bit is different thing. Will edit. Thanks – Bush Feb 21 '15 at 19:02
• btw,setting 010 wouldn't change it. – Bush Feb 21 '15 at 19:15
• If "$A$ deals with a truly ransom permutation, the probability that in every answer, for different random queries, the parities $w_r$ and $w_a$ equal is" not $\frac1{2^n}$, since a truly random permutation's answers for queries are not independent. $\;$ – user991 Feb 21 '15 at 19:22
• If a truly random permutation is behind the oracle then for the $i$-th query the probability that $w_r=w_a$ is at most $\frac{2^{n-1}}{2^n-i+1}$ which asymptotically converges to $\frac{1}{2}$ and thus the probability for $n$ queries converges to $2^{-n}$. If you agree I'll edit my answer. – Bush Feb 21 '15 at 22:32