The expected properties

A hash function transforms data of arbitrary size into a fixed-size digest. But not every function that does this is cryptographic: that status is earned by satisfying precise properties.

The basic properties

Three properties are expected of any useful hash function:

• Deterministic: the same input always produces the same digest. Without this, verifying anything would be impossible.
• Fixed-size output: whether the input is 3 bytes or 3 gigabytes, the digest has the same length (256 bits for SHA-256).
• Fast to compute: hashing a file must take a negligible amount of time.

"a"                          -> 3f2c8b...      (256 bits)
"Bonjour tout le monde"      -> a91e7d...      (256 bits)
un fichier de 4 Go           -> 0c4f19...      (256 bits)
      entrée quelconque             empreinte de taille fixe

The three resistances

This is where the cryptographic qualifier is decided. A cryptographic hash function must resist three types of search:

• Preimage resistance: given a digest h, it is impossible to recover a message m such that H(m) = h. This is the one-way property.
• Second preimage resistance: given a message m1, it is impossible to find another, different message m2 such that H(m1) = H(m2).
• Collision resistance: it is impossible to find any two distinct messages m1 and m2 having the same digest.

The distinction between the last two is subtle but crucial: in the second preimage, m1 is imposed; in the collision, the attacker is free to choose both messages. This freedom makes collisions easier to obtain, as we will see in the next chapter.

Property	What is given	What we look for	Protected use
Preimage	the digest h	an m such that H(m)=h	stored passwords
Second preimage	a message m1	an m2 != m1, same digest	integrity of a specific document
Collision	nothing imposed	two m with the same digest	signatures, certificates

The avalanche effect

A good hash function has the avalanche effect: changing a single bit of the input must alter roughly half of the output bits, in an unpredictable way.

H("chat")  = 1a3f...0b   (empreinte A)
H("chats") = e7c2...94   (empreinte B, sans rapport visible)

Without this effect, similar inputs would produce similar digests, and an attacker could reconstruct the input by successive approximations. The avalanche effect guarantees that no information about the input "leaks" into the digest.

In summary

A cryptographic hash function is deterministic, fixed-output and fast, but above all it resists preimage, second preimage and collisions, while exhibiting a strong avalanche effect. These resistances are not equivalent: the collision, where the attacker chooses both messages, is the hardest to guarantee.