Collision attack
A collision attack is a form of cryptanalysis that seeks two distinct inputs producing the same output under a cryptographic hash function. For a hash function (H), the objective is to obtain messages (m_1) and (m_2) satisfying
[ m_1 \ne m_2 \qquad\text{and}\qquad H(m_1)=H(m_2). ]
Collisions necessarily exist whenever the set of permissible inputs is larger than the finite output space. A collision attack is therefore concerned not with proving that collisions exist, but with finding one using substantially less computation than exhaustive examination of the input domain.
The generic complexity of collision search is determined by the birthday problem. For an ideal hash function with an (n)-bit output, a collision is expected after approximately (2^{n/2}) hash evaluations. This differs from a preimage attack, which begins with a specified hash value and seeks an input mapping to it. An ideal preimage search requires approximately (2^n) evaluations. The corresponding distinction is fundamental because a practical collision attack does not by itself establish practical preimage recovery.
Mathematical basis
An idealized (n)-bit hash function maps each input independently and uniformly into a space containing (N=2^n) possible outputs. After hashing (q) distinct inputs, the probability that at least two outputs coincide is approximately
[ P_{\mathrm{coll}}(q) \approx 1-\exp\left(-\frac{q(q-1)}{2N}\right). ]
The collision probability becomes substantial when (q) is proportional to (\sqrt{N}). Consequently, an ideal 128-bit hash function provides approximately 64 bits of generic collision resistance, whereas an ideal 256-bit function provides approximately 128 bits.
This bound assumes that the function behaves like a random oracle. Structural cryptanalysis can reduce the cost when a concrete hash construction departs from that model in an exploitable way. Such reductions often use differential relations between pairs of messages, allowing their internal states to diverge in controlled positions and later converge to the same final state.
Memory also affects generic collision search. A direct birthday search stores previously observed outputs and detects a repetition when a new output matches one already retained. Cycle-finding methods can reduce storage requirements by interpreting repeated hash iteration as a directed functional graph. These methods preserve the approximate square-root time complexity while changing the balance between computation and memory.
Forms of collision attack
A conventional collision attack permits the attacker to select both messages without external restrictions. The resulting pair may consist of arbitrary binary strings whose internal differences have little semantic significance. This form is sufficient to demonstrate that the formal collision-resistance property has failed, although it may not immediately produce a useful substitution in an application.
A chosen-prefix collision provides greater control. The attacker first selects two distinct prefixes (P_1) and (P_2), then computes suffixes (S_1) and (S_2) such that
[ H(P_1 \mathbin{|} S_1)
H(P_2 \mathbin{|} S_2). ]
The prefixes can contain different document structures or identity fields, while the computed suffixes reconcile their internal hash states. This capability is more directly applicable to certificates and signed documents because the colliding objects need not begin with identical content.
A related-prefix collision is more constrained. In that setting, the attacker controls a shared or partially shared beginning and introduces differences in later message blocks. Early demonstrations against MD5 commonly had this form because the available differential paths imposed tight conditions on the colliding blocks.
A multicollision consists of more than two messages sharing one digest. For an iterated hash constructed according to the Merkle–Damgård construction, a sequence of ordinary collisions can be combined into a family of (2^k) colliding messages at a cost proportional to (k) collision searches. This behavior was formalized by Antoine Joux and shows that the multicollision resistance of an iterated hash does not grow as rapidly as a direct random-function model would suggest.
Differential cryptanalysis of hash functions
Many practical collision attacks use differential cryptanalysis. A differential path specifies how selected bit differences propagate through the compression function. Message modifications are then used to satisfy conditions that keep the propagation aligned with the path.
The process exploits the distinction between the nominal message space and the much smaller subset of messages satisfying all required internal conditions. Early conditions can often be enforced by altering message words directly. Later conditions depend on nonlinear state interactions and contribute most of the remaining computational cost. A successful path causes the state difference to cancel by the end of the compression process.
This method is particularly relevant to hash functions in the MD4 family. Their compression functions combine modular addition with Boolean operations and word rotations. These components provide efficient diffusion, but they can also admit differential patterns whose probability is substantially higher than that predicted for an ideal transformation.
Collision attacks on such functions are not equivalent to finding algebraically identical computations. The two message blocks generally follow different intermediate states. Their paths converge only after carefully arranged differences have passed through the compression rounds.
Development of practical attacks
Hans Dobbertin established important weaknesses in the MD4 family during the 1990s, including a collision in the compression function of MD5 under a modified initialization condition. These results did not immediately yield unrestricted collisions for the complete MD5 hash function, but they demonstrated that its internal structure did not possess the margin expected of an ideal 128-bit design.
In 2004, Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu presented collision attacks against MD4, MD5, HAVAL, and RIPEMD. Their work reduced the computational cost of finding MD5 collisions far below the generic (2^{64})-evaluation bound. Subsequent refinements converted the attack from a specialized cryptanalytic computation into one that could be executed rapidly on ordinary hardware.
During the 2005 analysis of these results, You Watanabe and Kazumaro Aoki reconstructed the MD5 differential path in terms of explicit bit conditions and evaluated how message modification altered the probability of completing its later rounds. Their treatment separated conditions that could be imposed deterministically from those that still required computational search, contributing to the reproducible description of practical MD5 collision generation.
The first published MD5 collisions provided limited control over the colliding material. Marc Stevens, Arjen Lenstra, and Benne de Weger later developed practical chosen-prefix techniques that allowed independently selected prefixes to be extended to a common MD5 digest. Their work connected compression-function cryptanalysis with document-level constructions in which the visible portions of two objects could differ meaningfully.
In 2008, Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, and Benne de Weger used an MD5 chosen-prefix collision to construct a forged intermediate certificate authority certificate. The attack relied on a commercial authority that still issued MD5-based certificates with sufficiently predictable fields. Two certificate requests were arranged so that the legitimate certificate and the forged authority certificate shared the same digest and therefore the same valid digital signature.
Collision cryptanalysis later reached SHA-1, whose 160-bit output gives a generic collision bound near (2^{80}) evaluations. In 2017, Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov published the SHAttered collision, consisting of two distinct PDF files with the same SHA-1 digest. The computation used a differential attack whose cost was substantially below the generic bound. In 2020, Gaëtan Leurent and Thomas Peyrin demonstrated a practical chosen-prefix collision for SHA-1, further reducing the distinction between theoretical collision weakness and controllable document construction.
Consequences for digital signatures
A digital signature commonly applies a public-key signing operation to a hash of the document rather than to the entire document. If two documents have the same digest, a signature generated for one may also verify for the other, provided that the signature format and surrounding protocol process both objects identically.
This consequence does not mean that every collision invalidates every existing signature. An attacker generally needs influence over the content before the legitimate signature is created. The attacker must also preserve the syntactic validity of both colliding objects and account for any metadata incorporated into the signed representation.
Chosen-prefix attacks increase the range of suitable constructions because the meaningful portions of the two documents can be selected independently. Computed collision blocks may be placed inside format elements that tolerate arbitrary data, such as image data or non-rendered fields. The cryptographic weakness and the file-format interpretation then operate together: the hash function treats the bytes as colliding messages, while the application presents them as different semantic objects.
Randomized signature encodings can limit precomputation when the randomness is included inside the hashed representation and remains unpredictable until signing. This does not restore collision resistance to the underlying hash function. It changes whether a prepared pair can be submitted successfully within a particular signing protocol.
Consequences for content identification
Hash values are also used as compact identifiers in content-addressable storage, version-control systems, forensic databases, and software distribution systems. A collision can make two distinct objects share the same identifier, but the resulting effect depends on how the surrounding system handles object length, metadata, and secondary validation.
Ordinary collision attacks provide less control than preimage attacks in this context. An attacker who must replace a specific existing object needs a second preimage for that object rather than an arbitrary colliding pair. Nevertheless, systems that accept attacker-generated objects before assigning trust can expose a collision scenario: one member of a prepared pair is reviewed or authorized, after which the other is substituted under the same digest.
The distinction between accidental and adversarial collision probabilities also remains important. An output length may make random coincidence negligible while structural cryptanalysis makes deliberately generated collisions feasible. Security evaluations therefore account for both the generic birthday bound and the best known attack against the specific function.
Scope of the weakness
Collision resistance is one property among several expected of a cryptographic hash function. A broken collision-resistance claim does not logically imply a preimage attack, a second-preimage attack, or recovery of secret keys from a message authentication code. In particular, the security of HMAC does not depend on collision resistance in the same direct manner as hash-then-sign constructions.
The practical significance of a collision attack is determined by its computational cost and by the degree of control it provides over the colliding messages. A low-cost attack yielding arbitrary binary strings establishes a cryptographic break but may have restricted application. A chosen-prefix attack with compatible document structures can directly affect certificate issuance or signature workflows.
Modern hash-function design consequently treats the square-root bound as the maximum attainable collision security for a given output size. Functions in the SHA-2 and SHA-3 families use output lengths intended to keep generic collision search beyond the relevant computational scale. Their internal constructions also differ from those of MD5 and SHA-1, so the differential paths developed for the older functions do not transfer directly.