1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Review the statement. XOR requires 2 parameters at least. $\endgroup$ – Robert NACIRI Feb 18 '15 at 0:25
  • $\begingroup$ 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 $\endgroup$ – Anon Feb 18 '15 at 0:27
  • $\begingroup$ 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. $\endgroup$ – Robert NACIRI Feb 18 '15 at 0:29
  • $\begingroup$ How does knowing the parity bit help the attacker? $\endgroup$ – Anon Feb 18 '15 at 1:21
  • 3
    $\begingroup$ @Anon What have you tried so far? Are you familiar with the definitions involved? $\endgroup$ – yyyyyyy Feb 18 '15 at 1:38
2
$\begingroup$

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)]=??$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\;\;\;\;$ $\endgroup$ – user991 Feb 21 '15 at 19:01
  • $\begingroup$ you right, I just noticed that parity bit is different thing. Will edit. Thanks $\endgroup$ – Bush Feb 21 '15 at 19:02
  • $\begingroup$ btw,setting 010 wouldn't change it. $\endgroup$ – Bush Feb 21 '15 at 19:15
  • $\begingroup$ 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. $\;$ $\endgroup$ – user991 Feb 21 '15 at 19:22
  • $\begingroup$ 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. $\endgroup$ – Bush Feb 21 '15 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.