2
$\begingroup$

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

$\endgroup$
5
  • $\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
    Commented Feb 3, 2016 at 9:28
  • 2
    $\begingroup$ Solve f2(x,y) = z ​ ​ $\endgroup$
    – user991
    Commented Feb 3, 2016 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$ Commented Feb 3, 2016 at 11:50
  • 2
    $\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
    Commented Feb 3, 2016 at 13:33
  • $\begingroup$ @CodesInChaos The block size is obviously the same size as the key size. $\endgroup$
    – Maarten Bodewes
    Commented Feb 3, 2016 at 22:27

1 Answer 1

2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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