What is a collision attack, and how does it differ from a pre-image attack?

A collision attack finds ANY two different messages with the same hash (attacker controls both), while a pre-image attack must match a specific given hash.

* The attacker crafts both messages; the birthday paradox cuts the work to ~2^(n/2). *

Collision attack: Find $m_1 \neq m_2$ such that:

$$h(m_1) = h(m_2)$$

The attacker is free to choose both messages.

Pre-image attack: Given a specific $h(m)$, find $m' \neq m$ such that $h(m') = h(m)$.

Why collisions are easier to find:

• Pre-image: ~$2^n$ attempts needed (brute force)
• Collision: ~$2^{n/2}$ attempts needed (birthday paradox!)

For SHA-256: pre-image needs $2^{256}$, but collision only needs $2^{128}$ attempts.

Collision attack scenario: Eve creates two documents — an innocent one ($m_1$) and a malicious one ($m_2$) — with the same hash. She gets Alice to sign the innocent one. The signature is equally valid for the malicious document.

Tip: The birthday paradox makes collisions much easier: in a room of just 23 people, there's a >50% chance two share a birthday. Similarly, hash collisions appear much sooner than you'd intuitively expect.

Go deeper:

• Collision attack — classical and chosen-prefix collisions.
• Birthday attack — why collisions need only 2^(n/2) work.