If we have the following block cipher, $E(k,m)$, which is a permutation, why is $f_2 (x,y)$ not collision resistant?
$$f_2(x, y) = E(x, x \oplus y)$$
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
First since E is an encryption algorithm, it has a Decryption counterpart, lets name it D.
From the correcntess equation we get that $E(x,D(x,c)) = c$ for every $x$. Then we can easily see that if
$$y= x \oplus D(x,c)$$ then $$f_2(x,y) = E(x, y \oplus x) = E(x, x \oplus D(x,c) \oplus x) = E(x,D(x,c)) = c$$
Again this holds for every $x$. So we have just shown that a collision exists for all pairs of the form $\langle x, x \oplus D(x,c) \rangle$