DI Management Home > Cryptography > SPHINCS+ > Properties of a cryptographic hash function

# 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 >>