# Real Hash Functions

Learn real hash functions in this lesson.

## Classification of hash functions

According to

**Block cipher-based hash functions:**Hash functions are constructed from block ciphers, such as AES.**Modular arithmetic-based hash functions:**Hash functions that “reduce the security to the hardness of number theoretic problems”, such as the discrete logarithm problem, e.g., the hash function designed by .Chaum, van Heijst, and Pfitzmann (1992) David Chaum, Eugene van Heijst, and Birgit Pfitzmann. Cryptographically strong undeniable signatures, unconditionally secure for the signer (extended abstract), pages 470-84. Berlin, Heidelberg, 1992. Springer-Verlag. **Dedicated hash functions:**Algorithms specifically designed to provide efficient hash computations.

We only consider dedicated hash functions since these are the most commonly used ones in practice. Most of them are based on `MD4`

, a message digest algorithm developed by `MD5`

, the SHA family (including `SHA-0`

, `SHA-1`

, and `SHA-2`

), or RIPEMD follow the iterative method, which relies on the Merkle-Damgard construction.

## The Merkle-Damgård construction

We’ve only discussed the requirements and security aspects for hash functions so far. We now introduce how they’re designed inherently.

The most popular design of hash functions is the Merkle-Damgård construction, which was independently invented in 1989 by

### Definition:

The concatenation of two-bit strings $a$ and $b$ is denoted by $a \| b$.

The Merkle-Damgård construction relies on a collision-resistant compression function $g$, which is used iteratively in order to build a hash function.

### Compression function

A collision-free function $g:\{0,1\}^{m}$ $\rightarrow\{0,1\}^{n}$ with $r=m-n$ is called a **compression function**.

Get hands-on with 1200+ tech skills courses.