Preimage, second preimage, and collision resistance

The tell is what the attacker is given

These three properties are the single most examined discrimination in this course, and learners lose marks on them not because the definitions are hard but because they sound the same when skimmed. They do not sound the same when you write them in the form “given X, find Y” and name X exactly. Do that once, properly, and the confusion never comes back.

Preimage resistance. Given a digest h, find any message M with H(M) = h. The attacker holds a hash and nothing else. They are free to return any message at all — it need not be meaningful, it need not resemble anything. This is the one-way property: easy in the forward direction, infeasible in reverse.

Second preimage resistance. Given a specific message M, find a different message M' with H(M') = H(M). The attacker holds a message somebody else chose. One of the two colliding messages is fixed for them and they cannot touch it; only the second one is theirs to construct.

Collision resistance. Find any pair M, M' with M ≠ M' and H(M) = H(M'). The attacker holds nothing. Both messages are theirs to choose, which is a far weaker demand than either of the other two, and the freedom is worth an enormous amount.

Read the three X's in a column — a digest, a message, nothing — and the properties stop being confusable.

Why the costs differ, and why that is the point

Suppose H has an n-bit digest and behaves like a random function. To find a preimage you must keep hashing candidates until one lands on the single target value out of $2^n$ possibilities: expected effort about $2^n$. Second preimage is the same arithmetic — you are still aiming at one fixed target — so it is also about $2^n$.

Collision is not. You are not aiming at a target; you are waiting for any two of your candidates to agree. After hashing k messages you hold about $k^2/2$ pairs, and you expect a match once $k^2/2$ approaches $2^n$ — that is, once k reaches roughly $2^{n/2}$. This is the birthday bound, named for the fact that 23 people in a room suffice for a shared birthday even though there are 365 days. It halves the exponent.

So: preimage $2^n$ · second preimage $2^n$ · collision $2^{n/2}$. The practical consequence, and the sentence to write in an exam, is security equals digest size divided by two. SHA-1's 160-bit digest gives 80-bit security. A 128-bit digest gives 64-bit security, which is why 128-bit hashes died: a purpose-built collision search machine costed at ten million US dollars in the mid-1990s was estimated to find an MD5 collision in 24 days, while the same machine set against a 160-bit hash would have needed over four thousand years.

Here is the part learners get backwards. Collision resistance is the strongest requirement — it implies second preimage resistance — and simultaneously the cheapest to break. There is no contradiction: it is strongest as a demand on the designer and cheapest as a target for the attacker, precisely because the attacker gets to choose both messages. MD5 and SHA-1 died to collision attacks and to nothing else. Nobody has ever inverted either one.

Worked example — matching the property to the application

The question to ask of any application is always the same: what does the attacker already hold?

• Stored password digests. The system stores H(password) and compares digests at login. An attacker who steals the file holds digests only. To log in they must produce some string that hashes to a stored value — any string will do, since the login check only hashes what you typed. That is preimage resistance.
• File-integrity monitoring. A host-based intrusion detector records H(F) for every system binary on write-once media and recompares later. An attacker who wants to substitute a trojaned login binary holds the original file and must produce a different file with the same digest. That is second preimage resistance.
• Signing a certificate or a contract. A CA signs a digest of the certificate's contents; the signature is over the digest, not the bytes. An attacker who can construct two certificates with the same digest — one innocuous, one naming them as a code-signing authority — submits the innocuous one for signature and keeps the signature for the other. They chose both. That is collision resistance.

The third case is the classic trap, usually told as an IOU: the forger prepares an IOU for a trivial amount and an IOU for a large one that hash alike, gets the small one signed, and presents the large one. Learners label this second preimage resistance because “there is an original message”. There is not — the forger wrote both. It is collision resistance, every time.