# 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 SPHINCS+ is not affected by a collision attack against the hash function.

<< previous: SPHINCS+ A stateless hash-based signature scheme | Contents | next: One-time signature (OTS) scheme >> |

## 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 3 September 2023.*