Two Different Files, One Identical Fingerprint. That Is a Serious Problem
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
Squeezing any amount of data into a fixed length summary guarantees that different inputs will sometimes produce the same output, and how hard that is to arrange decides whether it matters.
Why collisions are unavoidable
A hash function takes an input of any length and produces an output of fixed length. There are infinitely many possible inputs and a finite number of possible outputs, so different inputs must share outputs, which follows from counting rather than from any weakness in the design. The question is never whether collisions exist. The question is whether anybody can find one, which depends on how many possible outputs there are and on whether the function has a structural flaw that shortcuts the search.
Where they cause trouble
The consequences vary enormously with the use:
- •In a lookup table, a collision is routine and handled by design
- •In deduplication, a collision silently discards different data
- •In a digital signature, a collision lets one document substitute for another
- •In file verification, it lets altered content pass as unmodified
- •In password storage, a collision means a wrong password is accepted
- •Only the first of these is supposed to happen
The birthday problem
The search is far easier than the number of possible outputs suggests, and the reason is the same arithmetic behind a well known party puzzle. Finding a collision with one specific value requires searching a number of candidates comparable to the whole output space. Finding any two values that collide with each other requires only about the square root of that, because every new candidate is compared against everything already tried. A function producing outputs of a given length therefore offers only half that length in practical security against this kind of attack, which is why output lengths are chosen with a large margin.
The properties a good one needs
Three separate requirements are usually stated and they are not the same thing. Given an output, it should be impractical to find any input producing it, which protects a stored password. Given an input, it should be impractical to find a second input producing the same output, which protects a signed document against substitution. And it should be impractical to find any two inputs producing the same output, which is the weakest requirement to state and the easiest to break. A function can satisfy the first two and fail the third, which is exactly what happened to the functions that were broken.
The functions that fell
Two widely used functions were broken by exactly this route and the timeline is instructive. Weaknesses in one were published in the 1990s, practical collisions followed in 2004, and by 2008 researchers had used it to forge a certificate that browsers would accept. The other held longer, with theoretical attacks from 2005 and a practical demonstration in 2017 producing two different documents sharing a value. Both remain in use in places where nobody has audited what they are for, which is the real lesson, since a broken function used for verification is worse than no verification at all.
The takeaway
Fixed length outputs from unlimited inputs guarantee that different data shares a summary, so the question is only how hard a collision is to find. Searching for any colliding pair takes about the square root of the output space, which halves the effective security. Two widely used functions were broken this way and were used to forge a certificate browsers accepted.