3
$\begingroup$

If I don't use XOR in Davies–Meyer construction like in picture 2, does the function remain collision resistant?

enter image description here

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Is Enc from a block cipher? ​ ​ $\endgroup$ – user991 May 31 '16 at 22:32
  • $\begingroup$ This reduces the pre-image resistance to $n/2$ bits via a meet-in-the-middle attack, but I don't see how it would weaken collision resistance. $\endgroup$ – CodesInChaos Jun 1 '16 at 9:00
3
$\begingroup$

Let $h=E_{x_i}(z_{i-1})$ in your suggestion. Let $z'=E^{-1}_{x'}(h)$. This gives a collision between between $(x_i,z_{i-1})$ and $(x',z').$

The XOR makes this attack difficult.

| improve this answer | |
$\endgroup$
  • $\begingroup$ How would the attacker reach the chaining state $z^\prime$? That sounds like a first pre-image attack to me, so your "attack" only works if you can pull of a much more difficult attack already. $\endgroup$ – CodesInChaos Jun 1 '16 at 8:59
  • 1
    $\begingroup$ What you describe is a freestart collision, not a proper collision. Freestart collisions aren't necessarily a problem, for example they're trivial to find for SHA-3 using essentially the same technique you describe. $\endgroup$ – CodesInChaos Jun 1 '16 at 9:24
  • $\begingroup$ @CodesInChaos, can you describe a proper collision in the context of this question? $\endgroup$ – kodlu Jun 1 '16 at 21:40

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.