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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Did you mix up the two sides of your comparison? And what definition of "break" do you use? $\endgroup$– CodesInChaosNov 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$– Paŭlo EbermannNov 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$– curiousNov 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$– CodesInChaosNov 19, 2012 at 13:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Nov 19, 2012 at 14:42