Collision vs Pre-image Resistance: The Core Hash Security Properties
A cryptographic hash function relies on three distinct mathematical barriers: Pre-image resistance (you cannot reverse a hash), Second pre-image resistance (you cannot duplicate a specific target hash), and Collision resistance (you cannot find any two inputs that match). Because of the Birthday Paradox, finding any collision requires only the square root of operations compared to reversing a targeted hash.
Pre-image resistance means you cannot work backwards from a hash to the original input (takes 2n work). Second pre-image resistance means an attacker cannot craft a forged document that matches an existing target hash (takes 2n work). Collision resistance means an attacker cannot find any two arbitrary files with the same hash—which takes only 2n/2 work because pairwise combinations grow exponentially.
01. The Plain-Language Analogy: The Birthday Party
Imagine walking into an auditorium trying to find someone who shares your exact birthday (say, July 14th). Because there are 365 possible days, you would need to interview roughly 365 people to have a reasonable chance of success. That is Pre-image Resistance: matching a specific, predetermined target.
Now change the game: find any two people in the room who share the same birthday, regardless of what date it is. You no longer need 365 people—you only need 23 people for a 50.7% probability! Why? Because 23 people form 253 pairwise comparisons. That is Collision Resistance: finding a match between any two elements in the set is exponentially easier than matching a specific target.
02. Step-by-Step Mechanics: The Three Pillars
Given a hash value y, it is computationally infeasible to find any message x such that H(x) = y.
Given a specific input x₁, it is computationally infeasible to find another distinct input x₂ ≠ x₁ such that H(x₁) = H(x₂). This protects against an attacker swapping a legitimate legal contract with a fraudulent contract that produces the exact same hash.
It is computationally infeasible to find any two distinct inputs x₁ ≠ x₂ such that H(x₁) = H(x₂). The attacker is free to choose both messages simultaneously.
// Calculate the number of samples needed for a 50% chance of a collision
// Formula: k ≈ 1.1774 * sqrt(2^n)
function calculateCollisionEffort(bitLength: number): {
bits: number;
preimageAttempts: string;
collisionAttempts: string;
} {
// Pre-image effort: 2^n
// Collision effort: 2^(n / 2)
return {
bits: bitLength,
preimageAttempts: `2^${bitLength}`,
collisionAttempts: `2^${bitLength / 2}`
};
}
console.log('Cryptographic Strength by Bit Length:');
console.log('MD5 (128-bit):', calculateCollisionEffort(128));
// Collision effort: 2^64 (broken in practice via cryptanalysis to 2^18)
console.log('SHA-1 (160-bit):', calculateCollisionEffort(160));
// Collision effort: 2^80 (broken in practice by SHAttered to 2^63)
console.log('SHA-256 (256-bit):', calculateCollisionEffort(256));
// Pre-image: 2^256 | Collision: 2^128 (completely secure)03. Worked Example: The Historic SHAttered Collision (Live Data)
In 2017, Google and CWI Amsterdam produced the world's first real-world collision on SHA-1 (known as the SHAttered attack). They created two distinct PDF documents with different visual contents that produce the identical SHA-1 digest:
38762cf7f55934b34d179ae6a4c80cadccbb7f0a 38762cf7f55934b34d179ae6a4c80cadccbb7f0a 2bb6087af303e313c544d44a0280f4ee3f592f80980043cb9a613e77616f709c d4488775d29bfe66657da6d87c68f973887ea572496cacb09f51a884e102dac3 The two files generated the exact same SHA-1 hash, yet when hashed with SHA-256, their digests were completely different. This proved conclusively that SHA-1's collision resistance was broken, forcing the global web to retire SHA-1 certificates.
04. Common Misconceptions Corrected
Reality: Collision resistance and pre-image resistance are completely different properties. Finding two arbitrary files that match (collision) requires only 2¹⁸ operations in MD5, but reversing an existing password hash to uncover the user's password (pre-image) still requires ~2¹²⁸ brute force attempts. (However, fast GPU cracking makes unsalted MD5 passwords trivially crackable anyway).
Reality: A 256-bit hash provides 256 bits of security against pre-image attacks, but only 128 bits of security against collision attacks. 128 bits is still cryptographically unbreakable (3.4 × 10³⁸ operations), but it is half the nominal bit length.
Reality: Because the input space is infinite and the output space is strictly 256 bits, the Pigeonhole Principle guarantees that an infinite number of collisions exist mathematically. The security of a hash function does not mean collisions don't exist; it means they are computationally impossible for human beings to discover.
05. Cryptographic Hash Strength Comparison
| Algorithm | Digest Bits | Pre-image Strength | Collision Strength | Security Status |
|---|---|---|---|---|
| MD5 | 128 bits | 2¹²⁸ | Broken (< 2¹⁸ in practice) | Insecure ✗ |
| SHA-1 | 160 bits | 2¹⁶⁰ | Broken (SHAttered, 2⁶³) | Deprecated ✗ |
| SHA-256 | 256 bits | 2²⁵⁶ | 2¹²⁸ operations | Standard ✓ |
| SHA-512 | 512 bits | 2⁵¹² | 2²⁵⁶ operations | High Security ✓ |