Computational cryptography › Hashes and symmetric ciphers
Hardness assumption

Collision resistance

In plain words

Nobody can find any two different inputs with the same fingerprint.

The idea: Collision resistance means nobody can find any two inputs with the same fingerprint. That lets a short hash stand in for a big document: sign the hash, publish the hash or store the hash, and you've effectively fixed the whole document. Because the attacker chooses both inputs, the birthday effect helps them (in a room of 23 people, two probably share a birthday), so a 256-bit hash gives only 128-bit collision security.

Why it matters: Needed for certificates, git, blockchains and many signatures. It already broke for the old MD5 and SHA-1.

The birthday effect
0%50%100%11023405770people in the room
23 people: 50.7% chance of a shared birthday
With 365 possible birthdays, it takes only 23 people for a shared birthday to become more likely than not, because every pair of people is a chance. Hashes work the same way: with 2n possible outputs, a collision is likely after about 2n/2 tries. That is why a 256-bit hash gives 128-bit collision security.

The details

On the map: SHA-2, SHA-3, BLAKE2/3 (also every CRH-tagged signature) needs a bit more than one-way functions (Simon 1998)

Infeasible to find any two inputs with the same hash. The strongest of the three properties: the generic birthday attack needs only about 2^(n/2) work, so a 256-bit hash gives 128-bit collision security.

It fell for MD5 (2004)[1] and SHA-1 (SHAttered, 2017)[2]. SHA-2, SHA-3 and BLAKE2/3 stand. Unlike preimage resistance, it isn't known to follow from one-way functions alone (Simon 1998)[3]. Merkle trees, certificates and hash-then-sign signatures need it.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (2 boxes)

References

  1. Xiaoyun Wang and Hongbo Yu. How to Break MD5 and Other Hash Functions. Advances in Cryptology – EUROCRYPT 2005. doi:10.1007/11426639_2
  2. Marc Stevens, Elie Bursztein, Pierre Karpman et al. The First Collision for Full SHA-1. Advances in Cryptology – CRYPTO 2017. doi:10.1007/978-3-319-63688-7_19
  3. Daniel R. Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions?. Advances in Cryptology — EUROCRYPT'98, 1998. doi:10.1007/bfb0054137