# Why is this PRF not secure? [closed] So, I'm taking Cryptography I by Dan Boneh on Coursera and I was reviewing the definition of security for a PRF while solving exercises, and I stumbled upon this question from a homework Dan Boneh gave for a winter class of 2020. Where it's cleared stated that F1 is not a secure PRF, but I can't get my head over it.

If $$k_1$$ and $$k_2$$ are from the same Keyspace, I'm assuming they are chosen independently, why is this PRF not secure? Is that because we can assume that $$k_1$$ might be equal to $$k_2$$? And then query $$x = y = 0^n$$, that way we could argue the following:

• Receive $$z = G((k_1,k_2),(x,y))$$, where $$G$$ is either $$F_1$$ or a random function.
• Output $$b = 1$$ if $$z = 0^n$$ and $$0$$ otherwise, then

$$F_1((k_1,k_2),(0^n,0^n)) = F(k_1, 0^n) ⊕ F(k_2,0^n) = 0^n$$

Which would return a non-negligible advantage $$(1-2^{-n})$$?

Sorry if it doesn't make sense, it's a concept I'm still trying to understand.

• have you searched this site with the string "PRF"? There are many questions answered on this topic Aug 21, 2022 at 6:25

Here is the attack: You query:

• $$F_1((k_1,k_2),a,b)$$ and get $$y1$$
• $$F_1((k_1,k_2),c,b)$$ and get $$y2$$
• $$F_1((k_1,k_2),a,d)$$ and get $$y3$$

Now you can compute

• $$F_1((k_1,k_2),c,d) = y_1 \oplus y_2 \oplus y_3$$

But this value should be unpredictable if the PRF was secure:

Proof:

• $$y_1 \oplus y_2 \oplus y_3= (F(k_1,a)\oplus F(k_2,b))\oplus( F(k_1,c)\oplus F(k_2,b))\oplus( F(k_1,d)\oplus F(k_2,b))= F(k_1,c)\oplus F(k_2,d)=F_1((k_1,k_2),c,d)$$

x1 and x2 don't get mixed together properly you can predict the output of combinations. In particular we get this (with only 2 queries)

$$F_1((0,0),(0,1)) = F_1((0,0),(1,0))$$

But if you use different random Ks it still won't help much, you still have a problem can query a few related points and predict a new point, which is the 4 points in the hint, I will stop short from full solution.