# Block cipher not resistant to collisions

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)$$

• @RickyDemer Ι have tried to use as y something with Decrypt in it as D(x,...) in order for the encryption to go away though have not be able to find the appropriate after a serious amount of time – J.S Feb 3 '16 at 9:28
• Solve f2(x,y) = z ​ ​ – user991 Feb 3 '16 at 9:48
• I don't think you need to use the decryption algorithm. It seems you just have to play with the XOR operation to find two pairs of values $(x_0, y_0)$ and $(x_1, y_1)$ such that $f_2(x_0, y_0) = f_2(x_1, y_1)$. Remember the XOR's properties... – Hilder Vitor Lima Pereira Feb 3 '16 at 11:50
• Collision resistant with respect to what, exactly? For a given key $x$, the value of $x \oplus y$ will be unique for each value of $y$, so $E(x,x \oplus y)$ will be collision-free if $E$ is a permutation. But if $x$ is allowed to vary, then presumably $k$ can vary too, in which case $E$ is not collision-resistant because it would be simple to find $(k_1, k_2, m_1, m_2)$ such that $E(k_1,m_1) = E(k_2,m_2)$. (Or perhaps I just misunderstood the question.) – r3mainer Feb 3 '16 at 13:33
• @CodesInChaos The block size is obviously the same size as the key size. – Maarten Bodewes Feb 3 '16 at 22:27

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$