Collision resistance

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Collision resistance" – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message)

In cryptography, collision resistance is a property of cryptographic hash functions: a hash function H is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b where a ≠ b but H(a) = H(b).^[1]: 136 The pigeonhole principle means that any hash function with more inputs than outputs will necessarily have such collisions;^[1]: 136 the harder they are to find, the more cryptographically secure the hash function is.

The "birthday paradox" places an upper bound on collision resistance: if a hash function produces N bits of output, an attacker who computes only 2^N/2 (or ${\displaystyle \scriptstyle {\sqrt {2^{N}}}}$) hash operations on random input is likely to find two matching outputs. If there is an easier method to do this than brute-force attack, it is typically considered a flaw in the hash function.^[2]

Cryptographic hash functions are usually designed to be collision resistant. However, many hash functions that were once thought to be collision resistant were later broken. MD5 and SHA-1 in particular both have published techniques more efficient than brute force for finding collisions.^[3][4] However, some hash functions have a proof that finding collisions is at least as difficult as some hard mathematical problem (such as integer factorization or discrete logarithm). Those functions are called provably secure.^[2]