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 …

Continue reading