Understanding Hash Collisions

Problem

You want to understand hash collisions and why they matter for security-critical applications.

Prerequisites

• Understanding of hash functions
• Knowledge of the pigeonhole principle

Steps

1. 1. Understand the inevitability of collisions

   A hash maps an unlimited input space to a fixed output space (e.g., 256 bits for SHA-256). By the pigeonhole principle, collisions must exist. However, for a secure hash, finding one should be computationally infeasible — requiring about 2^128 attempts for SHA-256 (birthday bound).

   Input

   SHA-256: 2^256 outputs

   Output

   collision needs ~2^128 tries

2. 2. Learn about broken hash functions

   MD5 is fully broken: collisions can be found in seconds. SHA-1 is practically broken: the SHAttered attack found a real collision in 2017. SHA-256 and SHA-3 remain secure. Never use MD5 or SHA-1 for security purposes.

   Input

   MD5 collision

   Output

   found in <1 second

3. 3. Understand collision vs preimage attacks

   A collision attack finds any two inputs with the same hash. A preimage attack finds an input that hashes to a specific value. Collision attacks are easier (birthday bound). For password storage, preimage resistance matters; for digital signatures, collision resistance matters.

   Input

   collision: 2^(n/2) | preimage: 2^n

   Output

   different difficulty

Expected result

Understanding of why collision resistance matters and which hash functions are safe to use.

Common errors

Using MD5 for integrity checking

MD5 collisions are trivial to produce. Use SHA-256 or SHA-3 for any security-relevant integrity check.

Assuming collision resistance implies preimage resistance

They are distinct properties. A function can be collision-resistant but not preimage-resistant, though standard hash functions aim for both.

Troubleshooting

• If you see MD5 or SHA-1 in a legacy system, plan to migrate to SHA-256 or SHA-3.
• For digital signatures, collision resistance is the critical property; use SHA-256 or stronger.

Security limits

• MD5 and SHA-1 are broken and must not be used for security. SHA-256 and SHA-3 are currently secure.
• This is an educational tool; no data leaves your browser.