Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
    
@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 at 9:28
2  
Solve f2(x,y) = z ​ ​ – Ricky Demer Feb 3 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... – Vitor Feb 3 at 11:50
1  
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.) – squeamish ossifrage Feb 3 at 13:33
    
@CodesInChaos The block size is obviously the same size as the key size. – Maarten Bodewes Feb 3 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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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