# Does a break in a collision resistance property of a hash function by definition implies an attack at the first pre-image attack?

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?

• 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
• 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

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.
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.