If I don't use XOR in Davies–Meyer construction like in picture 2, does the function remain collision resistant?
$\begingroup$
$\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
$\begingroup$
$\endgroup$
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.
-
$\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
