Hash Collision

What Is a Hash Collision?

A hash collision occurs when two different inputs, x and y, produce the same hash output: H(x) = H(y). Because a hash function maps an arbitrarily large input space to a fixed-size output, collisions are guaranteed to exist by the pigeonhole principle. If you have more possible inputs than possible outputs, some inputs must share an output.

The security of cryptographic systems does not depend on collisions being impossible. It depends on collisions being unfindable. A well-designed hash function like SHA-256 makes collision discovery so computationally expensive that no attacker can succeed with current or foreseeable technology. When a hash function loses this property, as MD5 and SHA-1 both did, every system that relies on it becomes vulnerable.

How It Works

To understand why collisions matter, you need to distinguish three security properties of hash functions:

• Preimage resistance: given a hash output h, you cannot find any input m such that H(m) = h. For an n-bit hash, this requires 2^n operations.
• Second preimage resistance: given an input m1, you cannot find a different input m2 such that H(m1) = H(m2). This also requires 2^n operations because one input is fixed.
• Collision resistance: you cannot find any two distinct inputs m1 and m2 such that H(m1) = H(m2). The attacker has total freedom over both inputs, which dramatically reduces the work required.

Collision resistance is the weakest of these properties. If an attacker can find collisions, they can potentially forge documents, certificates, or transactions that appear legitimate under a hash-based verification scheme.

The Birthday Paradox

The birthday paradox is the mathematical principle behind collision attacks. In a room of just 23 people, there is a greater than 50% chance that two share the same birthday. This is counterintuitive because most people think about the odds of someone sharing their specific birthday, but the actual question is whether any pair matches.

Applied to hash functions: for an n-bit hash with 2^n possible outputs, you only need approximately 2^(n/2) random inputs before a collision becomes likely. This square-root relationship means collision resistance is always half the output length in bits:

A birthday attack systematically exploits this bound by generating large numbers of candidate inputs, hashing each, and checking for matches. It is a generic attack that works against any hash function regardless of its internal design.

Why Differential Cryptanalysis Beats the Birthday Bound

The birthday bound represents the best a generic attack can do. Specialized techniques like differential cryptanalysis can find collisions faster by exploiting the internal structure of a specific hash algorithm. This is how real-world collision attacks have succeeded against MD5 and SHA-1: not by brute force, but by finding mathematical shortcuts within the algorithm itself.

Historical Collision Attacks

MD5: From Standard to Broken

MD5, a 128-bit hash published by Ronald Rivest in 1991, illustrates how collision resistance degrades over time. In 1996, Hans Dobbertin found collisions in MD5's compression function. In 2004, Xiaoyun Wang and colleagues demonstrated practical full MD5 collisions requiring only about 2^39 operations, executable in under an hour.

By 2006, MD5 collisions could be generated in under a minute on a standard laptop. In 2008, researchers used a chosen-prefix collision attack to forge a Certificate Authority (CA) certificate, enabling man-in-the-middle attacks against HTTPS. In 2012, the Flame malware used a novel MD5 collision technique to forge a Microsoft code-signing certificate, distributing malware disguised as a legitimate Windows Update. Today, MD5 collisions can be produced in seconds on commodity hardware.

SHA-1: The SHAttered Attack

SHA-1 (160-bit) was the dominant cryptographic hash for over a decade. In February 2017, researchers from CWI Amsterdam and Google published the SHAttered attack, producing two visually distinct PDF files with the same SHA-1 hash. The attack required approximately 2^63.1 SHA-1 computations: well below the theoretical birthday bound of 2^80, using differential cryptanalysis to find shortcuts.

The computational cost was approximately 6,500 CPU-years and 110 GPU-years, estimated at around $110,000 on cloud infrastructure. While expensive, this was more than 100,000 times faster than a brute-force birthday attack. The demonstration confirmed that SHA-1 was no longer safe for any application requiring collision resistance.

Why Bitcoin Uses Double-SHA-256

Bitcoin hashes block headers, transaction IDs, and Merkle tree nodes using double-SHA-256: applying SHA-256 twice as SHA-256(SHA-256(data)). A common misconception is that this doubles collision resistance. It does not. Double hashing still provides 128-bit collision security, the same as single SHA-256.

The actual purpose is protection against length extension attacks. SHA-256 uses the Merkle-Damgård construction, which has a structural vulnerability: an attacker who knows H(message) can compute H(message || padding || extra_data) without knowing the original message. By applying a second round of SHA-256, the internal state is reset, eliminating this attack vector entirely.

This defense was proposed by Ferguson and Schneier in their book "Practical Cryptography" years before Bitcoin's genesis block in 2009. They named the construction SHA-256d, which Satoshi Nakamoto adopted throughout the Bitcoin protocol.

What Happens If SHA-256 Collision Resistance Breaks

If practical SHA-256 collisions were ever discovered, the implications for Bitcoin would be severe:

• Merkle tree forgery: an attacker could craft two different transactions with the same TXID, potentially substituting a malicious transaction within a block's Merkle tree without changing the Merkle root
• Transaction ID conflicts: because TXIDs are double-SHA-256 hashes, collisions could create conflicting transactions that appear identical to the network
• Block header manipulation: block headers reference the previous block hash and Merkle root, both computed with SHA-256d. Collisions could theoretically enable alternative chain histories

Satoshi Nakamoto addressed this scenario directly, writing that Bitcoin could transition to a new hash function after a specified block height if SHA-256 were ever compromised. All nodes would need to upgrade before that block, and old block hashes could be hardcoded to prevent retroactive substitution attacks. Such a change would require BIPs and a hard fork.

Current State of SHA-256 Security

Full SHA-256 (64 rounds) remains unbroken. No practical collision or preimage attack exists against the complete algorithm.

The most significant cryptanalytic progress came at ASIACRYPT 2024, where researchers demonstrated the first practical collision for 31-step SHA-256 (out of 64 total steps), computed in 1.2 hours using 64 threads. This improved the previous best practical collision attack by three steps, jumping from the 28-step result published at EUROCRYPT 2013.

Reaching 31 of 64 steps is notable progress, but each additional step increases difficulty dramatically. The gap between 31 and 64 steps represents an enormous security margin. SHA-256 remains the foundation of Bitcoin's cryptographic security with no foreseeable practical threat from classical computing.

Quantum Computing Implications

Quantum computers introduce new attack vectors against hash functions through specialized algorithms. For collision resistance specifically, the Brassard-Hoyer-Tapp (BHT) algorithm from 1997 offers a cube-root speedup:

Grover's algorithm halves the bit security of preimage attacks, reducing SHA-256 from 2^256 to 2^128, which remains computationally secure. The BHT algorithm reduces collision resistance from 2^128 to approximately 2^85. While this is a meaningful reduction, 2^85 operations with quantum hardware remains far beyond current or near-term capabilities.

A critical practical constraint is that the BHT algorithm requires enormous quantum random-access memory (QRAM): finding SHA-256 collisions would need approximately 2^85 hash outputs stored in QRAM, which is astronomically beyond any foreseeable quantum hardware. Research into post-quantum cryptography continues, but NIST considers SHA-256 and longer hash functions secure for the foreseeable future. For further analysis, see post-quantum threats to Bitcoin.

Use Cases for Collision Resistance

Collision resistance is not an abstract concern. It underpins the security of systems that billions of people rely on:

• Digital certificates: TLS/SSL certificates use hash functions to bind a public key to a domain. Collision attacks on MD5 enabled forged CA certificates in 2008.
• Software integrity: code-signing certificates verify that software has not been tampered with. The Flame malware exploited MD5 collisions to forge Microsoft signatures.
• Blockchain integrity: Merkle trees, block headers, and transaction IDs all depend on collision-resistant hashing to prevent forgery
• Digital signatures: many signature schemes hash the message before signing. If the hash collides, two different messages produce the same signature.
• Commitment schemes: protocols that rely on committing to a value by publishing its hash (as in HTLCs) break down if an attacker can find two values with the same hash

Risks and Considerations

Gradual Degradation, Not Sudden Failure

Hash function security does not break overnight. MD5 took 13 years from its first compression-function weakness (1996) to weaponized real-world exploitation (Flame malware, 2012). SHA-1 took over a decade from theoretical weaknesses to the SHAttered demonstration in 2017. This pattern suggests that reduced-round attacks on SHA-256 (currently at 31 of 64 steps) are an early warning signal worth monitoring, not an imminent threat.

Cryptographic Agility

Systems that hardcode a single hash function face upgrade risks if that function weakens. Cryptographic agility, the ability to swap algorithms without redesigning the entire system, is a design principle that provides insurance against future breakthroughs. Bitcoin's reliance on SHA-256 throughout its protocol stack makes a hash migration particularly complex, requiring coordinated network-wide upgrades via a hard fork.

Collision vs. Preimage Attacks in Practice

Not every application that uses a hash function requires collision resistance. Proof-of-work mining, for example, requires preimage-like properties (finding an input below a target), not collision resistance. An attacker who can find SHA-256 collisions cannot mine blocks any faster because mining is a different computational problem. Proof of work remains secure against collision attacks specifically, though it faces separate considerations from quantum preimage speedups via Grover's algorithm.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.