6.7: Exercises
- Page ID
- 86461
In this problem, you will show that it is hard to determine the key of a PRF by querying the PRF.
Let \(F\) be a candidate PRF, and suppose there exists a program \(\mathcal{A}\) such that: \[\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {prf-real }}^{F} \text { outputs } k\right] \text { is non-negligible }\] In the above expression, \(k\) refers to the private variable within \(\mathcal{L}_{\text {prf-real }}\).
Prove that if such an \(\mathcal{A}\) exists, then \(F\) is not a secure PRF. Use \(\mathcal{A}\) to construct a distinguisher that violates the PRF security definition.
Let \(F\) be a secure PRF.
(a) Let \(m \in\{0,1\}^{\text {out }}\) be a fixed (public, hard-coded, known to the adversary) string. Define: \[F_{m}(k, x)=F(k, x) \oplus m .\] Prove that for every \(m, F_{m}\) is a secure PRF.
(b) Define \[F^{\prime}(k, x)=F(k, x) \oplus x\] Prove that \(F^{\prime}\) is a secure \(\mathrm{PRF}\).
Let \(F\) be a secure PRF with \(\lambda\)-bit outputs, and let \(G\) be a PRG with stretch \(\ell\). Define \[F^{\prime}(k, r)=G(F(k, r))\] So \(F^{\prime}\) has outputs of length \(\lambda+\ell\). Prove that \(F^{\prime}\) is a secure PRF.
Let \(F\) be a secure PRF with in \(=2 \lambda\), and let \(G\) be a length-doubling PRG. Define \[F^{\prime}(k, x)=F(k, G(x))\] We will see that \(F^{\prime}\) is not necessarily a PRF.
(a) Prove that if \(G\) is injective then \(F^{\prime}\) is a secure PRF.
Hint:
\(\star\) (b) Exercise 5.9(b) constructs a secure length-doubling PRG that ignores half of its input. Show that \(F^{\prime}\) is insecure when instantiated with such a PRG. Give a distinguisher and compute its advantage.
Note: You are not attacking the PRF security of \(F\), nor the PRG security of \(G\). You are attacking the invalid way in which they have been combined.
Let \(F\) be a secure PRF, and let \(m \in\{0,1\}^{i n}\) be a fixed (therefore known to the adversary) string. Define the new function \[F_{m}(k, x)=F(k, x) \oplus F(k, m)\] Show that \(F_{m}\) is not a secure PRF. Describe a distinguisher and compute its advantage.
In the previous problem, what happens when \(m\) is secret and part of the PRF seed? Let \(F\) be a secure PRF, and define the new function: Define the new function \[F^{\prime}((k, m), x)=F(k, x) \oplus F(k, m) .\] The seed of \(F^{\prime}\) is \((k, m)\), which you can think of as a \(\lambda+i n\) bit string. Show that \(F^{\prime}\) is indeed a secure PRF.
Let \(F\) be a secure PRF. Let \(\bar{x}\) denote the bitwise complement of the string \(x\). Define the new function: \[F^{\prime}(k, x)=F(k, x) \| F(k, \bar{x})\] Show that \(F^{\prime}\) is not a secure PRF. Describe a distinguisher and compute its advantage.
Suppose \(F\) is a secure PRF with input length in, but we want to use it to construct a PRF with longer input length. Below are some approaches that don’t work. For each one, describe a successful distinguishing attack and compute its advantage: (a) \(F^{\prime}\left(k, x \| x^{\prime}\right)=F(k, x) \| F\left(k, x^{\prime}\right)\), where \(x\) and \(x^{\prime}\) are each in bits long.
(b) \(F^{\prime}\left(k, x \| x^{\prime}\right)=F(k, x) \oplus F\left(k, x^{\prime}\right)\), where \(x\) and \(x^{\prime}\) are each in bits long.
(c) \(F^{\prime}\left(k, x \| x^{\prime}\right)=F(k, x) \oplus F\left(k, x \oplus x^{\prime}\right)\), where \(x\) and \(x^{\prime}\) are each in bits long.
(d) \(F^{\prime}\left(k, x \| x^{\prime}\right)=F(k, \vartheta \| x) \oplus F\left(k, 1 \| x^{\prime}\right)\), where \(x\) and \(x^{\prime}\) are each in \(-1\) bits long.
Define a PRF \(F\) whose key \(k\) we write as \(\left(k_{1}, \ldots, k_{i n}\right)\), where each \(k_{i}\) is a string of length out. Then \(F\) is defined as: \[F(k, x)=\bigoplus_{i: x_{i}=1} k_{i}\] Show that \(F\) is not a secure PRF. Describe a distinguisher and compute its advantage.
Define a PRF \(F\) whose key \(k\) is an in \(\times 2\) array of out-bit strings, whose entries we refer to as \(k[i, b]\). Then \(F\) is defined as: \[F(k, x)=\bigoplus_{i=1}^{i n} k\left[i, x_{i}\right]\] Show that \(F\) is not a secure PRF. Describe a distinguisher and compute its advantage.
A function \(\{0,1\}^{n} \rightarrow\{0,1\}^{n}\) is chosen uniformly at random. What is the probability that the function is invertible?
Let \(F\) be a secure PRP with blocklength blen \(=128\). Then for each \(k\), the function \(F(k, \cdot)\) is a permutation on \(\{0,1\}^{128}\). Suppose I choose a permutation on \(\{0,1\}^{128}\) uniformly at random. What is the probability that the permutation I chose agrees with a permutation of the form \(F(k, \cdot)\) ? Compute the probability as an actual number \(-\) is it a reasonable probability or a tiny one?
Suppose \(R:\{0,1\}^{n} \rightarrow\{0,1\}^{n}\) is chosen uniformly among all such functions. What is the probability that there exists an \(x \in\{0,1\}^{n}\) such that \(R(x)=x ?\)
Hint:
\(\mathrm{~ t r o t f e u m x o r d d e ~ ว น t ~ 8 u s n ~ f a m s u r ~}\)
In this problem, you will show that the PRP switching lemma holds only for large domains. Let \(\mathcal{L}_{\text {prf-rand }}\) and \(\mathcal{L}_{\text {prp-rand }}\) be as in Lemma 6.7. Choose any small value of blen \(=\) in \(=\) out that you like, and show that \(\mathcal{L}_{\text {prf-rand }} \neq \mathcal{L}_{\text {prp-rand }}\) with those parameters. Describe a distinguisher and compute its advantage.
Let \(F:\{0,1\}^{i n} \rightarrow\{0,1\}^{\text {out }}\) be a (not necessarily invertible) function. We showed how to use \(F\) as a round function in the Feistel construction ony when in =out.
Describe a modification of the Feistel construction that works even when the round function satisfies in \(\neq\) out. The result should be an invertible with input/output length in \(+\) out. Be sure to show that your proposed transform is invertible! You are not being asked to show any security properties of the Feistel construction.
Show that a 1-round keyed Feistel cipher cannot be a secure PRP, no matter what its round functions are. That is, construct a distinguisher that successfully distinguishes \(\mathcal{L}_{\text {prp-real }}^{F}\) and \(\mathcal{L}_{\text {prp-rand }}^{F}\), knowing only that \(F\) is a 1-round Feistel cipher. In particular, the purpose is to attack the Feistel transform and not its round function, so your attack should work no matter what the round function is.
Show that a 2-round keyed Feistel cipher cannot be a secure PRP, no matter what its round functions are. Your attack should work without knowing the round keys, and it should work even with different (independent) round keys.
Hint:
\(\mathrm{~ s ә п . т ว ก b ~ о м า ~ s ә п ! n b ә л ~ у}\)
Show that any function \(F\) that is a 3-round keyed Feistel cipher cannot be a secure strong PRP. As above, your distinguisher should work without knowing what the round functions are, and the attack should work with different (independent) round functions.
In this problem you will show that PRPs are hard to invert without the key (if the blocklength is large enough). Let \(F\) be a candidate PRP with blocklength blen \(\geqslant \lambda\). Suppose there is a program \(\mathcal{A}\) where: \[\operatorname{Pr}_{y \leftarrow\{0,1\}^{b l e n}}\left[\mathcal{A}(y) \diamond \mathcal{L}_{\text {prf-real }}^{F} \text { outputs } F^{-1}(k, y)\right] \text { is non-negligible. }\] The notation means that \(\mathcal{A}\) receives a random block \(y\) as an input (and is also linked to \(\left.\mathcal{L}_{\text {prf-real }}\right) . k\) refers to the private variable within \(\mathcal{L}_{\text {prf-real. So, when given the ability to }}\) evaluate \(F\) in the forward direction only (via \(\mathcal{L}_{\text {prf-real }}\) ), \(\mathcal{A}\) can invert a uniformly chosen block \(y\).
Prove that if such an \(\mathcal{A}\) exists, then \(F\) is not a secure PRP. Use \(\mathcal{A}\) to construct a distinguisher that violates the PRP security definition. Where do you use the fact that blen \(\geqslant \lambda\) ? How do you deal with the fact that \(\mathcal{A}\) may give the wrong answer with high probability?
Let \(F\) be a secure PRP with blocklength \(b\) len \(=\lambda\), and consider \(\widehat{F}(k, x)=F(k, k) \oplus F(k, x)\).
(a) Show that \(\widehat{F}\) is not a strong PRP (even if \(F\) is).
\(\star(b)\) Show that \(\widehat{F}\) is a secure (normal) PRP.