A collision-resistant hash function makes it computationally infeasible to find distinct inputs A and B such that H(A) = H(B). The matching digest is not fixed in advance; the attacker may search for any shared output. section 6.2
Why collisions must exist
A fixed-length digest maps unbounded inputs into bounded outputs, so collisions are mathematically unavoidable under the pigeonhole principle. The birthday paradox explains why finding one can require far fewer trials than examining every possible input. section 6.2
Collision resistance differs from preimage resistance and second preimage resistance: it protects against finding any matching pair, rather than recovering an input from a digest or matching a specified input’s digest. A hash is considered broken when collisions become easier to find than the naive birthday attack. section 6.2 section 6.5
In sponge-based designs, capacity supplies the collision-resistance limit: it is the minimum of half the output size or half the capacity size. Collision attacks can make logically different files share one digest, including differently rendered PDFs. section 6.3.2 section 6.5
Table 6.2 SHA-3 family of sponge-based hash functions
| Hash function | Output size \(d\) (bits) | Rate \(r\) (bits) | Capacity \(c\) (bits) | Collision resistance (bits) |
| SHA3-224 | 224 | 1152 | 448 | \(\frac{d}{2} = 112\) |
| SHA3-256 | 256 | 1088 | 512 | \(\frac{d}{2} = 128\) |
| SHA3-384 | 384 | 832 | 768 | \(\frac{d}{2} = 192\) |
| SHA3-512 | 512 | 576 | 1,024 | \(\frac{d}{2} = 256\) |
| SHAKE128 | \(d\) | 1,344 | 256 | \(min(\frac{d}{2}, \frac{c}{2}) = min(\frac{d}{2}, 128)\) |
| SHAKE256 | \(d\) | 1,088 | 512 | \(min(\frac{d}{2}, \frac{c}{2}) = min(\frac{d}{2}, 256)\) |
Compare SHA-3 and SHAKE output, capacity, and stated collision-resistance levels. section 6.3.2
