Collisionresistant

Collision resistance is a property of a cryptographic hash function indicating that it is hard to find two distinct inputs that produce the same output. In practice, a hash function used for digital signatures, integrity checks, or password storage should not reveal easily any pair of inputs with identical hashes.

Formally, a hash function H is collision-resistant if, for any probabilistic polynomial-time algorithm, the probability of finding distinct inputs x and y with H(x) = H(y) is negligible relative to the security parameter. For an ideal hash function with an n-bit output, the birthday bound implies about 2^(n/2) evaluations are needed to find a collision with non-negligible probability, rather than 2^n for a preimage search. This distinction highlights the different costs of breaking collision resistance versus other security properties like preimage resistance.

There are two related notions: weak (or second-preimage) resistance and strong collision resistance. Weak collision resistance means it is hard to find a different input y given a known input x such that H(x) = H(y). Strong collision resistance requires it is hard to find any two distinct inputs that collide, without conditioning on a starting value.

In practice, collision resistance underpins the security of many systems. If collisions become feasible to find, attackers could forge digital signatures, tamper with data, or impersonate authors. Hash functions historically considered collision-resistant, such as MD5 and SHA-1, have been deprecated after practical collision attacks were demonstrated; currently recommended hash functions include SHA-256 and SHA-3, which are believed to be collision-resistant for the foreseeable future, though ongoing analysis continues.