Recall that the Luby-Rackoff theorem discussed in The Data Encryption Standard lecture states that applying a three round Feistel network to a secure PRF gives a secure block cipher. Let's see what goes wrong if we only use a two round Feistel.
Let F:K×{0,1}32→{0,1}32 be a secure PRF.
Recall that a 2-round Feistel defines the following PRP
F2:K2×{0,1}64→{0,1}64:
Here R0 is the right 32 bits of the 64-bit input and L0 is the left 32 bits.
One of the following lines is the output of this PRP F2 using a random key, while the other three are the output of a truly random permutation f:{0,1}64→{0,1}64. All 64-bit outputs are encoded as 16 hex characters.
Can you say which is the output of the PRP? Note that since you are able to distinguish the output of F2 from random, F2 is not a secure block cipher, which is what we wanted to show.
Hint: First argue that there is a detectable pattern in the xor of F2(⋅, 064) and F2(⋅, 132032). Then try to detect this pattern in the given outputs.