4
$\begingroup$

I understand the need for the hash function to be collision resistant and second pre-image resistant. For what reason, exactly, does a hash function need to be pre-image resistant?

If this property is not useful for signatures, what is the origin of this requirement, maybe privacy?

$\endgroup$
  • $\begingroup$ Imagine that $H$ is easy to invert, pick an input $s$ somewhat randomly and compute $h = H(s), s' = H^{-1}(h)$. If $s \neq s'$ then you have a collision. But $H^{-1}$ doesn't know which $s$ you picked, so if there are many preimages (which there are as soon as $H$ compresses), you have a good chance of finding a collision using a preimage oracle. $\endgroup$ – Bristol Jul 28 '15 at 10:38
  • $\begingroup$ @Bristol Thank you for your comment. That means that the pre-image resistance is closely linked to collision resistance. But if there are three properties, this means that we could satisfy a subset of them ? $\endgroup$ – Dingo13 Jul 28 '15 at 11:12
  • $\begingroup$ My example needed $H$ to have collisions in the first place. If $P$ is a permutation on some finite set then it is trivially collision resistant but may or may not be preimage resistant; conversely if $H$ is preimage resistant then $H'$ that throws away the first bit of its input and evaluates $H$ on the rest is obviously not collision resistant, but may still be preimage resistant. So collision and preimage resistance are incomparable in general. $\endgroup$ – Bristol Jul 28 '15 at 15:51
4
$\begingroup$

The question "why is preimage resistance needed for hash functions" is not really relevant. This is because collision resistance implies preimage resistance. Thus, it is just a fact that if you have collision resistance then you must have preimage resistance.

So, instead, I will relate to what preimage resistance is good for at all. In more technical cryptographic terms, a preimage resistant function is called a one-way function. One-way functions are the most basic cryptographic primitive and you can construct all of symmetric crypto from them (i.e., you can construct pseudorandom generators, functions, symmetric encryption, message authentication codes, and so on). [Note: you cannot construct collision-resistant hash functions from them in a black-box way.] Thus, from a theoretical perspective, these functions are very interesting; I say "theoretical" since the above constructions are all theoretical and not practical.

Note that preimage resistance is a necessary condition almost everywhere in cryptography, but it is usually not sufficient. This is because it does not mean that it's impossible to obtain half of the preimage, and it is also only meaningful for very high entropy - if not random - inputs. The use of preimage resistance in hashing passwords is used in practice, but is only heuristic. In order to analyze this properly, you actually need to model the function as a random oracle.

So, preimage resistance or one-wayness is a fact of cryptography. It is the minimal property that you need to do almost anything interesting in crypto (apart from all of the information theoretic crypto work which I won't discuss here). However, it is not a security notion that is usually of interest in and by itself.

A proof sketch that collision resistance implies one-wayness

Assume that there exists an adversary $A$ who can invert a function $H:\{0,1\}^*\rightarrow\{0,1\}^n$ with probability $\epsilon$ on a random input of length $2n$. We construct an adversary $A'$ who finds a collision in $H$. Adversary $A'$ chooses a random $r\in\{0,1\}^{2n}$, computes $y=H(r)$ and invokes $A$ on input $y$. If $A$ returns $s$ such that $H(s)=y$ and $s\neq r$ then $A'$ outputs $s$. Otherwise it outputs $\bot$. We now analyze the probability that $A'$ succeeds. We have that $A'$ succeeds if $A$ succeeds and $s\neq r$. Since the input is of length $2n$ and the output is of length $n$, we have that each output has on average $2^n$ premiages. Thus, the probability that $s=r$ is negligible. [This part of the proof needs some work, but I'll leave that to the readers as an exercise.] We therefore conclude that $A'$ succeeds with probability $\epsilon - neg(n)$ where $neg$ is a negligible function. Thus, if $\epsilon$ is non-negligible then the function $H$ is not collision resistant. We conclude that if $H$ is collision resistant, then $A$ could only succeed with negligible probability and so $H$ is one-way.

$\endgroup$
  • $\begingroup$ "collision resistance implies preimage resistance" only in the sense that second-preimage resistance also implies preimage resistance. $\;$ $\endgroup$ – user991 Jul 28 '15 at 17:36
  • $\begingroup$ I'm not sure what you mean by this. The bottom line is that any function that is collision resistant is also preimage resistant. Of course it's also true that collision resistance implies second-preimage resistance, but this isn't really the question here. $\endgroup$ – Yehuda Lindell Jul 28 '15 at 18:05
  • $\begingroup$ What definitions are you using if "collision resistance implies preimage resistance"? E.g. what makes it so that $h(m) = SHA256(m)||h'(m)$ for any non-preimage resistant hash $h'$ does not show the converse? $\endgroup$ – otus Jul 28 '15 at 18:28
  • $\begingroup$ Preimage resistance is always defined relative to random inputs. Regarding your question, we are always talking about functions that COMPRESS. Therefore, there are always many preimages. Thus, finding a preimage for h' does not necessarily mean that this is a valid preimage for SHA256. $\endgroup$ – Yehuda Lindell Jul 28 '15 at 18:50
  • $\begingroup$ @otus I have added a proof sketch to the main answer. $\endgroup$ – Yehuda Lindell Jul 28 '15 at 18:58
1
$\begingroup$

There are a lot of other uses for hash functions than signature algorithms.

For example, when used as a MAC – whether directly or in HMAC – a preimage attack would recover the key and allow forgery for arbitrary messages.

Even specifically in signature algorithms there's the Lamport signature which requires preimage resistance.

$\endgroup$
  • $\begingroup$ Thanks for youer answer. "Without preimage resistance you would also be unable to build hash trees." Why ? You speak about hash trees in terms of hash functions based on it, or you speak about an other application ? $\endgroup$ – Dingo13 Jul 28 '15 at 11:28
  • $\begingroup$ @Dingo13 I meant Merkle trees, edited. $\endgroup$ – otus Jul 28 '15 at 11:30
  • 1
    $\begingroup$ Thanks but why does Merkle trees need a preimage resistant hash function? $\endgroup$ – Dingo13 Jul 28 '15 at 11:33
  • $\begingroup$ @Dingo13, yeah, Merkle trees are actually a bad example. They have many uses that don't require preimage resistance. I'll edit that part out. $\endgroup$ – otus Jul 28 '15 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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