Why do we say that collision-resistance is a "harder" property than second pre-image for hash functions whereas if you have an attack on the second pre-image then you find a collision ? Moreover, a collision has a good probability to be found in $O(\sqrt{N})$ where $N$ is the size of the hash function outputs, whereas second pre-image needs $O(N)$ ...
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
It's harder for the designer to make a hash function collision-resistant than second-preimage-resistant, because it's harder for the adversary to find a second preimage than to find a collision.
answered May 16, 2018 at 14:12
$\begingroup$
$\endgroup$
Collision-resistance is a stronger requirement because it directly implies second-preimage resistance. This is because a second-preimage attack is essentially a collision attack in which one of the collision pair's hash values is fixed and a corresponding input is known, and could have well been chosen by the attacker itself.
The more intuitive explanation is collision-resistance refers to the general case, whereas second-preimage resistance considers specific input values. It could be, for instance, that the hash values of a particular subset of inputs are easier to invert than others; with collision-resistance, they are hard to invert in general.
