2
$\begingroup$

Is there a formal security proof in the shape of reduction that states that if an attacker manages to break the collision resistance property of a cryptographic hash function (a random oracle) he will break the pre-image attack as well? To rephrase it: is first pre-image resistance as hard as collision resistance s.t if you break collision resistance you break first pre-image attack?

$\endgroup$
4
  • 1
    $\begingroup$ Did you mix up the two sides of your comparison? And what definition of "break" do you use? $\endgroup$ Nov 19, 2012 at 13:20
  • $\begingroup$ It looks like the answer is no - MD5's collision resistance is pretty broken, but there isn't yet a known attack against its preimage resistance (other than brute force). $\endgroup$ Nov 19, 2012 at 13:33
  • $\begingroup$ @CodesInChaos break collision resistance means to find two messages m1,m2 which are not equal s.t: h(m1)=h(m2). Break first preimage resistance means break the one-wayness, recover m1 from h(m1) $\endgroup$
    – curious
    Nov 19, 2012 at 13:45
  • 1
    $\begingroup$ I was asking about your definition of "break", if it means faster-than-bruteforce or fast enough for an attacker with a certain computational bound? In the second case, an ideal hashfunction obviously doesn't have your property, since finding a collision takes $2^{n/2}$ operations, finding a first pre-image takes $2^n$. $\endgroup$ Nov 19, 2012 at 13:50

1 Answer 1

8
$\begingroup$

This relation obviously doesn't hold.

If you define "break" as faster than what's expected of an ideal hash function

Define TrivialCollisionHash = GoodHash(input.Skip(1 bit)). Finding pre-images for this is just as hard as for GoodHash, i.e. $2^n$. Finding a collision is trivial, just flip the first bit.

If you define "break" as faster than a certain computation bound

Use an ideal hash function. It has collision resistance of $2^{n/2}$ and first pre-image resistance of $2^n$. So an attacker with a computational bound between $2^{n/2}$ and $2^n$ can find collisions but not pre-images. For example an attacker who can perform $2^{160}$ oracle queries on a 256 bit hash function will most likely find a collision, but he probably won't find a pre-image.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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