Properties of a cryptographic hash function

A hash function $h(M)$ takes as input a message $M$ of any length and outputs a message digest or hash value of a fixed length, $n$. For a given message $M$, the output is always the same.

In mathematical notation, we write

$h: \{0,1\}^{*} \rightarrow \{0,1\}^n$, where $\{0,1\}^n$ represents a bitstring of length $n$.

A cryptographic hash function has the following three properties

Preimage resistance

Given $h(M) = x$ it is computationally infeasible to compute $M$.

Second preimage resistance

Given $h(M) = x$ it is computationally infeasible to find a message $M' \ne M$ such that $h(M') = x$.

Collision resistance

It is computationally infeasible to find two messages $M_1$ and $M_2$ such that $h(M_1) = h(M_2)$.

If the message digest length is $n$ bits, the time complexity of a preimage or second preimage attack is $2^n$. But the time complexity of a collision attack is only $2^{n/2}$ (using a birthday attack).

Therefore resistance against a collision attack (strong collision resistance) requires a hash value at least twice as long as that required for preimage resistance (weak collision resistance).

Note that SLH-DSA is not affected by a collision attack against the hash function.

Chinese translation

Zhanglu Wang has kindly translated this page to Chinese on the CSDN site 密码学哈希函数的性质. Thank you Wang.

Contact us

To comment on this page or to contact us, please send us a message.

This page first published 17 March 2023. Last updated 30 August 2026.