2
$\begingroup$

Is it possible keep the "one wayness property" of certain one way function in Merkle-Damgård construction? I'm asking this question because according to Collision-Resistant hashing: Towards making UOWHFs practical the target collision resistant property fail in Merkle-Damgård construction.

$\endgroup$
2
$\begingroup$

Yes, a Merkle–Damgård hash can be one-way. Even MD5 hasn't been broken in that way.

Target collision resistance (TCR) is a notion similar to second preimage resistance (but for keyed functions). Preimage resistance, i.e. one-wayness, does not imply second preimage resistance, so a hash function can be one-way without even having second preimage resistance.

Normal collision resistance, which Bellare and Rogaway call any collision resistance (ACR) in that paper implies target collision resistance, so if the function is collision resistant, it is also TCR. With Merkle–Damgård a collision resistant compression function gives you a collision resistant hash function. Likewise, a preimage resistant compression function gives a preimage resistant hash function.

So what's the point of their result?

They show that TCR of the compression function does not imply TCR of the keyed hash function, meaning that e.g. a 128-bit MD hash does not necessarily have 128-bit TCR.

$\endgroup$

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.