What are preimage resistance and collision resistance, and how can the lack thereof be exploited?

Question

What is "preimage resistance", and how can the lack thereof be exploited? How is this different from collision resistance, and are there any known preimage attacks that would be considered feasible?

Answer 1

Preimage resistance is about the most basic property of a hash function which can be thought. It means:

For a given $h$ in the output space of the hash function, it is hard to find any message $x$ with $H(x) = h$.

(Note that the it is hard here and in the next definitions is not formally defined, but can be formalized by looking at families of hash functions with a security parameter $n$ (often the hash output size), and saying »hard = there is no polynomial $P$ so this can be done in time $P(n)$ for all functions of the family«. For practical uses, we are often only looking at a single hash function, and are content with »hard = takes more time/costs than any hypothetical attacker can invest«, preferably with some estimation of the work to be done.)

A function with this property is also called one-way function (though this term is also used for non-hash functions with this property, like asymmetric encryption primitives).

A related property is the second preimage resistance:

For a given message $x_1$ it is hard to find a second message $x_2 \neq x_1$ with $H(x_1) = H(x_2)$.

A function without preimage resistance is usually also not second preimage resistant: Given a message $x_1$, calculate $h := H(x_1)$ and then get a preimage $x_2$ from $h$, then we usually have $x_1 \neq x_2$ and $H(x_1) = H(x_2)$. (The exception to the "usually" would be when the function is (for the space of interesting messages) essentially injective, and the preimage finder would always return the only interesting preimage. Such a function would be second-preimage and collision resistant, but still a quite bad hash function. As normally the space of interesting messages is much larger than the hash space, this doesn't arise in practice.)

Collision resistance is an even harder property, which we still want for most usages of hash functions:

It is hard to find a pair of messages $x_1 \neq x_2$ with $H(x_1) = H(x_2)$.

Of course, from a (second) preimage attack we also get a collision attack. The other direction doesn't work as easily, though some collision attacks on broken hash functions seem to be extensible to be almost as useful as second preimage attacks (i.e. we find collisions where most parts of the message can be arbitrarily fixed by the attacker).

Also, there is the generic birthday attack on hash functions (which even works for random oracles), which needs $O(\sqrt N)$ tries to have a good probability to hit a duplicate, where $N$ is the size of the output space of the function, where a similar generic brute-force attack on the second-preimage and preimage resistance needs about $O(N)$ queries (which is not feasible for the output sizes of all hash functions used in practice).

I know of no practical preimage attack for the usual hash functions (please add them in other answers, or as comments), while for example for MD5 the collision-resistance is about totally broken, and SHA-1 is starting to show cracks (in 2017, a research team from Google produced two colliding documents).

How can one exploit the lack? This strongly depends on the use of the hash function in a higher-level protocol (or algorithm build on top of it). In some protocols only the other properties are used directly, but as said, missing preimage resistance always also leads to missing second-preimage and collision resistance. For example, in signature schemes we usually hash the message first, and a (second) preimage attack allows to create a second message with the same hash as the first one, i.e. where the same signature fits.

An example where the preimage resistance itself is needed is the hashing of a password, or usually a password together with a salt known to the attacker. (Actually here the message space is often small that searching it becomes feasible to brute-force search it with a common fast hash function, which is why one uses slow hash functions for password hashing.)

Answer 2

A collision attack is the ability to find two inputs that produce the same result, but that result is not known ahead of time. In a typical case (e.g., the attack on MD5) only a relatively small number of specific inputs are known to produce collisions. Collision resistance obviously means that a collision attack is difficult (for some definition of "difficult" varying from "no attack better than brute force is known" to "the known attacks aren't really feasible").

A preimage attack gives the ability to create an input that produces a specified result. A feasible preimage attack basically means that (as a crypographic hash) an algorithm is almost completely broken. Essentially the only attack that [edit: might] break it more completely is a second preimage attack. Either, however, basically means that what you have isn't a cryptographic hash function at all any more -- the whole point of a cryptographic hash is that it's a one-way function, but either sort of preimage attack means it's now a two-way function.

A collision attack can be used in a relatively small number of specific scenarios (e.g., signed certificates) but isn't nearly as comprehensive as a preimage or second preimage attack.

I don't know of a feasible preimage attack on any of the currently-popular hashes (e.g., SHA-1, SHA-256). Then again, if there was a preimage attack that was even remotely feasible, they would (or certainly should anyway) lose popularity extremely quickly. For comparison, MD5 is generally considered obsolete due to a feasible collision attack, but not any preimage attack at all. Even though it's not really feasible, the collision attack that's known on SHA-1 is still enough that most people would advise against continuing to use it (2017 edit: and with good reason--the collision attack on SHA-1 is now entirely feasible).

There are preimage attacks against a number of older hash functions such as SNEFRU (e.g., there's a second preimage attack on three-pass SNEFRU with a complexity of 2³³ operations, which means that (for example) reading the original message in from disk probably takes longer than computing the second preimage. Attacks that good are fairly unusual though: once reasonably feasible attacks on a particular algorithm become known, most people (users and researchers alike) tend to move on to bigger and better things, so to speak.

Answer 3

Often the hash (iterated and salted mostly) of a password is saved in a database, instead of the password. If a user logs in, the hash is computed and compared against the stored hash value. This way a user that can see the database of hashes does not see the password directly, but this property depends crucially on the hash being resistant to a pre-image attack, as described by other replies. With an ideal hash, no information about the password leaks, except the fact that an attacker then try passwords himself in an offline way or consult tables of precomputed hashes, and to make attacks like that harder, the salting and iterating steps are done.

Also hashes can be used in coin flipping protocols: suppose player 1 and 2 want to flip a coin, without being in the same place, and assume they have some secure communication channel. One way to do it, is that player 1 picks a large number $n$ (from some prearranged fixed but large range) and sends player 2 the hash of it. Player 2 then guesses whether $n$ is odd or even, and if he's right he wins the coin flip. To verify correctness, player 1 sends him the number $n$ and player 2 can verify that the hash of it matches the hash he received earlier. Now, if the hash were not pre-image resistant, player 2 could maybe compute $n$ from the hash and know instead of guess. And if the hash were not collision resistant player 1 could find (maybe) an odd $n$ and an even $m$ in the right range, with the same hash, so that he can produce the other number at the reveal stage, depending on what the other chose, and so player 1 could cheat.

As mentioned by Paulo, the second preimage resistance is important when you consider digital signatures, e.g. So it will depend on the application of the hash what it will need to satisfy, but because hashes are so versatile, we want for a standard one that it has as many of them as possible. E.g. Because they are used in cryptographic randomness generators as well, the output should look as random as possible as well, and the output should have uniformly distributed ranges, as close as possible.