15
$\begingroup$

I am studying hash functions. I can understand why collision resistance implies second preimage resistance, but I don't get why second preimage resistance should imply first preimage resistance.

Could anybody be help me with this argument from Introduction to Modern Cryptography by Katz & Lindell, please?

  1. Collision resistance: This is the strongest notion and the one we have considered so far.

  2. Second pre-image resistance: Informally speaking, a hash function is second pre-image resistant if given $s$ and $x$ it is infeasible for a probabilistic polynomial-time adversary to find $x' \ne x$ such that $H^s(x') = H^s(s)$.

  3. Pre-image resistance: Informally, a hash function is pre-image resistant if given $s$ and $y = H^s(x)$ (but not $x$ itself) for a randomly chosen $x$, it is infeasible for a probabilistic polynomial-time adversary to find a value $x'$ such that $H^s(x') = y$. (Looking ahead to later chapters in the book, this essentially means that $H^s$ is one-way.)

[...] Likewise, any hash function that is second pre-image resistant is also pre-image resistant. 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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ It doesn't. So where did you find that claim? $\endgroup$
    – CodesInChaos
    Sep 27, 2013 at 18:57
  • $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Sep 27, 2013 at 19:00
  • 2
    $\begingroup$ @CodesInChaos I found this claim in the page 130 of the book of Jonathan Katz and Yehude Lindell (Introduction to Modern Cryptography) $\endgroup$
    – juaninf
    Sep 27, 2013 at 19:09
  • 3
    $\begingroup$ The identity function has infinite second-preimage resistance and 0 bits of pre-image resistance. $\hspace{.53 in}$ $\endgroup$
    – user991
    Sep 27, 2013 at 19:19
  • 4
    $\begingroup$ I wrote a pretty detailed answer about this here. $\endgroup$
    – Reid
    Sep 27, 2013 at 19:25

3 Answers 3

Reset to default
16
$\begingroup$

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.

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)$. Suppose we are 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, 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?

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. This is not a formal proof: just an intuitive argument.

The crucial assumption 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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

Consider this hash: $$H(m) = m$$ Where we define it's domain to be messages of some arbitrary fixed-length.

It is completely second pre-image resistant.

It is not at all first pre-image resistant.

Therefore:

Second pre-image resistance does not imply first pre-image resistance.

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ I gave that example over a year ago. $\;$ $\endgroup$
    – user991
    Apr 22, 2015 at 23:28
  • 2
    $\begingroup$ @Ricky Didn't see it as an answer. Not sure what you're trying to accomplish with this comment. $\endgroup$
    – dameshgarm
    Apr 22, 2015 at 23:59
  • 2
    $\begingroup$ I don't think what @scampos has done necessarily deserves a deletion. See this question on meta.SE. We have also discussed this sort of thing on our Meta. At the very least, the answer expands slightly (add some mathematical notation, etc) to Ricky's comment. $\endgroup$
    – mikeazo
    Apr 23, 2015 at 12:28
  • 5
    $\begingroup$ I don't really agree with this answer, because to me, the identity function is not a hash function. Look at the definitions of hash function and cryptographic hash function on Wikipedia. I see problems with the identity function with relation to both of those definitions. $\endgroup$
    – mikeazo
    Apr 23, 2015 at 12:31
  • $\begingroup$ @mikeazo Thank you for the vote of confidence, and I agree with you taking issue about this deviating from some of the accepted definitions of a hash. I've edited the answer to fix some of those issues. Although I wouldn't go so far as to hold it up against the definition of a cryptographic hash, since that includes collision resistance and both image resistances. $\endgroup$
    – dameshgarm
    Apr 24, 2015 at 11:11
0
$\begingroup$

I know this post is old, sorry for bump, but I came across an interesting example that might invalidate the accepted answer.

Consider the following hash: H(m) = SHA1(m) | {first 10 bits of m, padded with 0 if len(m) < 10 bits} (clamped concatenation with SHA1).

This function is clearly not first pre-image resistant, as for any m such that len(m) < 10 bits we can find the pre-image easily by taking the last 10 bits (and remove the padding) of H(m).

However, I think that it is actually second pre-image resistant, as we cannot easily find another m' != m such that H(m) = H(m').

Therefore, it would mean that second pre-image resistance does not imply first pre-image resistance ?

I am curious to have an "expert's opinion" on this curious hash.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Your hash function violates the assumptions in the question in a trivial way. The hashes are assumed to be drawn from the random oracle model (uniformly drawn from all functions mapping to the assumed range, say $\{0,1\}^{512}$. Otherwise the analysis does not hold. So it is not a counterexample $\endgroup$
    – kodlu
    Jan 31 at 14:33
  • 1
    $\begingroup$ On the other hand, if we make the reasonable assumption that most messages that are hashed are much longer than your 10 bit constraint, this hash does obey the theorem! So its disagreement with the theorem is artificial in some sense. Your function is actually first image resistant in practically all of its codomain. $\endgroup$
    – kodlu
    Jan 31 at 14:34
  • 1
    $\begingroup$ @kodlu ok thx, very interesting insight. We can't pick a particular subset for disproving first pre-image resistance. $\endgroup$
    – gruvw
    Jan 31 at 19:26

Your Answer

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

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