Introduction

This blog post will introduce cryptographic hash functions. We are going to discuss the Merkle-Damgård construction which underlies many hash functions that were and are used nowadays. The MD4, MD5, SHA-1 and SHA-2 hash families are all functions that built on top of the Merkle-Damgård construction. Then we will introduce an alternative construction that was popularized during the publication of Keccak (SHA-3): The Sponge construction.

But what are cryptographic hash functions good for?

The general idea is to apply a unique and stable fingerprint to each input data $x$. This fingerprint is computed with a hash function $h$ and the resulting value $y = h(x)$ is called a message digest. The size of $h(x)$ is fixed, even though the input data $x$ may have arbitrary length. The intended task for $h$ is to assign a unique identification code $h(x)$ for each input $x \in X$ where $X$ is the set of all possible inputs. The avid reader might realize that this task is impossible, since there is no bijective function that connects an infinite large input set $X$ with fixed sized output set $h(x)$. Thus there must be collisions: For some inputs $x_1 \neq x_2 \in …

Continue reading