Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

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?

share|improve this question
1  
Did you mix up the two sides of your comparison? And what definition of "break" do you use? – CodesInChaos Nov 19 '12 at 13:20
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). – Paŭlo Ebermann♦ Nov 19 '12 at 13:33
@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) – curious Nov 19 '12 at 13:45
1  
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$. – CodesInChaos Nov 19 '12 at 13:50

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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