A cryptographic hash function \(H: \{0,1\}^* \rightarrow \{0,1\}^n\) is collision-resistant if finding two distinct inputs \(x_1 \neq x_2\) such that \(H(x_1) = H(x_2)\) requires \(\Omega(2^{n/2})\) operations (birthday bound).
Birthday Attack Complexity:
\[\text{Attempts} \approx \sqrt{\frac{\pi \cdot 2^n}{2}} = 1.25 \times 2^{n/2}\]
Working through an example:
Given: Password database stores SHA-256 hashes (256-bit output). Attacker attempts birthday attack to find collision.
Step 1: Birthday bound for SHA-256 \[n = 256 \text{ bits}\]
\[\text{Attempts} = 1.25 \times 2^{128} = 4.25 \times 10^{38} \text{ hash operations}\]
Step 2: Attack cost at 10 billion hashes/second \[\text{Time} = \frac{4.25 \times 10^{38}}{10^{10} \times 86400 \times 365.25} = 1.35 \times 10^{21} \text{ years}\]
Comparison: MD5 (128-bit) vs SHA-256 (256-bit)
MD5 birthday bound: \[\text{Attempts}_{MD5} = 2^{64} = 1.84 \times 10^{19}\]
With GPU cluster (\(10^{12}\) hashes/sec): \[\text{Time}_{MD5} = \frac{1.84 \times 10^{19}}{10^{12}} = 1.84 \times 10^7 \text{ seconds} \approx 213 \text{ days}\]
Result: SHA-256 collision requires \(10^{21}\) years (infeasible). MD5 collision feasible in about 213 days with a GPU cluster—which is why MD5 is deprecated for security.
In practice: Password databases must resist preimage attacks where an attacker finds input \(x\) such that \(H(x)\) matches a stored hash (\(2^n\) complexity), as well as collision attacks where an attacker finds two inputs with the same hash (\(2^{n/2}\) complexity). SHA-256’s 128-bit collision resistance exceeds foreseeable computing power. MD5’s 64-bit resistance was broken in 2004—avoid MD5 for any security application.