# Second pre-image imply pre-image resistance

I am study hash functions. I get understand colision resistance imply second pre-image resistance, but I can't get, yet, Why Second pre-image imply pre-image resistance?. Anybody Could be help me with this proof please?

This is due to the fact that if it is possible to invert y and find an $x^\prime$ such that $H^s (x^\prime ) = y$ then it is possible to take $x$, compute $y = H^s (x)$ and invert it again obtaining $x^\prime$ . Since the domain of $H$ is infinite, it follows that with good probability $x \neq x^\prime$ . We conclude that the above three security requirements form a hierarchy with each definition implying the one below it

-
It doesn't. So where did you find that claim? –  CodesInChaos Sep 27 at 18:57
For example consider the pathological 512 hashfunction that concatenates the first 256 bits of the input with the output of a a secure 256 bit hashfunction. This isn't first pre-image resistant, but has 256 bits of second pre-image resistance. –  CodesInChaos Sep 27 at 19:00
@CodesInChaos I found this claim in the page 130 of the book of Jonathan Katz and Yehude Lindell (Introduction to Modern Cryptography) –  juaninf Sep 27 at 19:09
hmm I can't think of a way that gives an n bit hashfunction n bit second pre-image resistance without giving it n bit first pre-image resistance. Perhaps their definition has some additional constraints. –  CodesInChaos Sep 27 at 19:15
I wrote a pretty detailed answer about this here. –  Reid Sep 27 at 19:25
show 2 more comments

Let me try to elaborate on their proof. Suppose you had a hash function $H$ that was second-preimage resistant but not first-preimage resistant. By showing that this leads to a contradiction, we will be showing that with second-preimage resistance, you must have first-preimage resistance. Namely, we will show that the lack of first-preimage resistance is enough to break second-preimage resistance.

So, when breaking second-preimage resistance, we are given a random $x$ and the goal is to find another $x' \ne x$ such that $H(x') = H(x)$. So suppose we were given a random $x$. Then we can compute $H(x)$ and then use our preimage-finding algorithm (since this hash function isn't first-preimage resistant, remember?) to find an input $x'$ such that $H(x') = H(x)$.

The question becomes whether or not $x' = x$. For a hash function with an infinite domain, there are infinitely many inputs that $H$ maps to the same output. That is, there exist infinitely many second-preimages for any particular $x$; the question is whether or not we can find one.

Intuitively, then, the preimage-finding algorithm "should" give back an $x' \ne x$. After all, there are infinitely many inputs that map to the same output as $x$, so the probability that we find the exact $x$ we were given "should be" low, right? This is not a formal proof: just an intuitive argument.

So we should have an $x' \ne x$ such that $H(x') = H(x)$. But this is a second preimage! Thus, assuming that $x'$ indeed does not equal $x$, we cannot have a hash function that has second-preimage resistance but not first-preimage resistance. Thus, second-preimage resistance must imply first-preimage resistance. Again, this is by no means a formal argument, but I think it makes sense.

Now, the crucial thing in this proof is that the domain is infinite. If it were not infinite, then all bets are off. In that case, the output size of the hash function needs to be sufficiently small relative to the input size for this argument to hold. I've written about that idea in great detail on my answer on the question "Pre-image resistant but not 2nd pre-image resistant?", so I refer you to that for more technical details.

-
very thanks, wonderful explanation –  juaninf Oct 2 at 12:12