A birthday attack finds two distinct inputs with the same hash digest by exploiting the birthday paradox. For an ideal N-bit hash, about 2^(N/2) hashes give a collision probability above 50%. section 6.2
A naive birthday attack proceeds as follows:
- Generate roughly 2^(N/2) random messages. section 6.4.1
- Hash each message and store its digest with the original input in a sorted table. section 6.2
- Locate equal digests paired with different inputs; the large storage requirement is the practical constraint. section 6.4.1
MD5 and structured file collisions
A 128-bit MD5 digest would require about 2^64 steps for a generic collision, although advanced attacks reduce this dramatically. Collision blocks can also be embedded in formats such as PNG, JPG, or ZIP so two files share a digest while exposing different active data. section 6.2 section 6.4.1
Equation 6.1
\[\begin{aligned} \begin{aligned} H(A) &= H(B) \\ H(A || X) &= H(B || X) \end{aligned} \label{equation:extend-collision} \end{aligned}\]The collision-extension equation shows why H(A) = H(B) implies H(A || X) = H(B || X). section 6.4.1
