Preimage, second preimage and collision resistance

The three formal resistance properties a cryptographic hash function must satisfy, how they relate to each other, and which one each application actually needs.

State preimage, second preimage and collision resistance in the lecture's own formal wording.
Explain why collision resistance implies second preimage resistance but preimage resistance stands apart from both.
Read the application-to-property table and say which resistance property a given use case needs.
Explain why pseudo-randomness is an implied, not formally listed, requirement.

18 min read

Intuition

The previous page established what a hash function does and why an unprotected one fails to authenticate a sender. Knowing what a hash function is for is not the same as knowing what it is safe against. Three formal properties define exactly what an attacker should not be able to do, and different applications need different subsets of them.

Mechanism

Two terms first. For a hash value $h = H(x)$ , $x$ is called a preimage of $h$ . A collision is any pair of distinct inputs that hash to the same output: $H(a) = H(b)$ with $a \neq b$ .

Mechanism

Preimage resistance. Given a randomly chosen $y$ from $H$ ‘s range of output values, it should be computationally infeasible to find an $x$ such that $H(x) = y$ . This does not mean it is impossible, brute force always works in principle, only that it must be too expensive to be practical. Preimage resistance matters whenever the confidentiality of the original message depends on the hash not being invertible: if it is violated, an attacker can recover the message just by observing its hash.

Formula

Preimage resistance

\forall y \in \text{range}(H):\ \text{finding } x \text{ such that } H(x) = y \text{ is computationally infeasible}

$y$: a hash value, chosen at random from H's range of possible outputs
$x$: the preimage being searched for

Mechanism

Second preimage resistance. Given a randomly chosen $x$ , it should be computationally infeasible to find a different $x' \neq x$ with $H(x') = H(x)$ . This is the property an attacker needs to break in order to substitute a forged message that hashes to the same value as a specific message that has already been fixed.

Formula

Second preimage resistance

\text{given a random } x:\ \text{finding } x' \neq x \text{ such that } H(x') = H(x) \text{ is computationally infeasible}

$x$: a given, already-known input
$x'$: a different input the attacker searches for

Mechanism

Collision resistance. It should be computationally infeasible to find any pair $(x, x')$ , $x \neq x'$ , such that $H(x) = H(x')$ . Unlike second preimage resistance, neither input is fixed in advance, the attacker just needs any two inputs anywhere in the space that happen to collide.

Formula

Collision resistance

\text{finding any pair } (x, x'),\ x \neq x',\ \text{with } H(x) = H(x') \text{ is computationally infeasible}

$x, x'$: any two distinct inputs, neither fixed in advance

Collision resistance implies second preimage resistance: a successful second-preimage attack is itself a valid collision. The reverse implication does not hold.

Compare

The attacker is constrained: given a specific $x$ , they must find a matching $x'$ for that exact input. There is one fixed target.

The attacker has maximum freedom: any two distinct inputs anywhere that collide are enough, with no target fixed in advance. This freedom is exactly why collision resistance is harder to satisfy than second preimage resistance, and why an attacker searching for a collision needs far fewer attempts than one searching for a preimage, the subject of the next topic.

Pitfall

Do not assume the three properties form a strict ladder where the strongest implies the other two. Only one implication holds: collision resistance implies second preimage resistance. Preimage resistance stands apart entirely, a function can be collision resistant without being preimage resistant, and preimage resistant without being collision or second preimage resistant, in either direction.

Exam detail

Which property an application needs, exactly as the lecture states it:

Application	Preimage resistant	Second preimage resistant	Collision resistant
Hash + digital signature	Yes	Yes	Yes
Intrusion detection and virus detection	Yes	Yes	Yes
Hash + symmetric encryption	Yes	Yes	Yes, if a chosen message attack is possible
One-way password file		Yes
MAC	Yes	Yes	Yes, if a chosen message attack is possible

The one-way password file row is the exception worth remembering: it needs second preimage resistance only, not the full set. A chosen message attack means the attacker can get the hash function (or a keyed variant of it) to process messages of their choosing, which is what upgrades the collision-resistance requirement from optional to necessary for hash + symmetric encryption and for MAC.

Mechanism

Pseudo-randomness is not formally listed as one of the three requirements, but it is implied by them. Cryptographic hash functions are used for key derivation and pseudorandom number generation, and the three resistance properties above only hold in practice if the output looks statistically random. It is worth directly checking that a candidate hash function’s output behaves this way. Hashing the same short string with two different algorithms already shows how unrelated the outputs look, even for near-identical input:

echo "CYBERSECURITY ENGINEERING" | sha256sum
605d08ba60312b5e8b79105bc4f31ee8c269b956cada4821c9e22876bab917e5

echo "CYBERSECURITY ENGINEERING" | md5sum
ca00a2f980e354eb1ff97c4305aaed2e

Recall

A hash function is proven collision resistant. Can you conclude it is also preimage resistant?

No. Collision resistance only guarantees second preimage resistance as well, since a second-preimage attack is itself a collision. Preimage resistance is a separate property with no strict implication running to or from it, a function can be collision resistant while still leaking the message from its hash.

Source

Week 6 Notes PDF