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

  • $\begingroup$ @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 $\endgroup$ – J.S Feb 3 '16 at 9:28
  • 2
    $\begingroup$ Solve f2(x,y) = z ​ ​ $\endgroup$ – user991 Feb 3 '16 at 9:48
  • $\begingroup$ 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... $\endgroup$ – Hilder Vitor Lima Pereira Feb 3 '16 at 11:50
  • 1
    $\begingroup$ 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.) $\endgroup$ – r3mainer Feb 3 '16 at 13:33
  • $\begingroup$ @CodesInChaos The block size is obviously the same size as the key size. $\endgroup$ – Maarten Bodewes Feb 3 '16 at 22:27

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$

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.