Real Hash Functions

Classification of hash functions

According to Paar and Pelzl (2009)Christoph Paar and Jan Pelzl. Understanding Cryptography: A Textbook for Students and Practitioners. Springer Berlin Heidelberg, 2009. and Preenel (2003)Bart Preenel. Analysis and design of cryptographic hash functions. https://homes. esat.kuleuven.be/ preneel/phd_preneel_feb1993.pdf, 2003. Accessed: 2018-03-15., there are three general types of hash functions:

1. Block cipher-based hash functions: Hash functions are constructed from block ciphers, such as AES.
2. 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..
3. 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 Ronald Rivest in 1990Ronald L. Rivest. The MD4 message-digest algorithm. In Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO’90, pages 303-11, London, UK, 1991. Springer-Verlag. in order to only use bitwise Boolean operations such as logical AND, OR, XOR, negation, and bit rotation. The majority of real-life dedicated hash functions, such as 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 MerkleRalph C. Merkle. A certified digital signature. In Proceedings on Advances in Cryptology, CRYPTO '89, pages 218-38, New York, NY, USA, 1989. New York, Inc. SpringerVerlag. and DamgărdIvan Damgård. A design principle for hash functions. In Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO '89, pages 416-27, London, UK, 1990. Springer-Verlag..

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.