# AES-128 as compression function in Merkle-Damgard construction

Using a compression function $$f : A × A → A$$. A basic version given by:

$$W_0 = IV$$
$$W_1 = f(W_0, m_1)$$
$$W_2 = f(W_1, m_2)$$
...
$$W_n = f(W_{n-1}, m_n)$$

$$W_n$$ is the output of the hash function, $$m_1,m_2 . . . m_n$$ is the message and $$IV$$ is a constant.

What would be the simplest way to implement AES-128 as the compression function? And would it be one way?

Excuse my ignorance, I am very new to the topic. My very wild stab in the dark is that AES-128 can be used in a way that feeds its own produced ciphertext blocks back into itself as the key.

• This question is basically covered by this more general question Sep 27 '18 at 16:24
• @rmalayter Not sure that addresses the main issue of AES being a random permutation rather than a random function. What is expected of a truly compressive function? Perhaps crypto.stackexchange.com/q/15579/23115? Sep 27 '18 at 19:30
• You can use Merkle-Damgård as stated. However, keep in mind that the block size of AES is too small for secure hash sizes. Sep 30 '18 at 21:47

This short thesis describes some of the basic ways in which to use the Merkle-Damgård construction based on block ciphers. The construction that is commonly used in MD5 and related constructions is in fact an instance of the Davies-Meyer construction. This could be directly applied to your construction (you have to add length padding and a length field to get a secure hash function of course) as follows: let $$E_k(m)$$ be a block cipher (like AES) with key $$k$$ and message block $$m$$, then we take $$f(W_i) = E_{m_i}(W_{i-1}) \oplus W_{i-1}$$ for $$i=1,\ldots n$$. This way we get a secure hash function, provided $$E$$ is a secure block cipher in the appropriate sense (essentially indistinguishable from a random permutation).

• Two caveats if doing what's suggested: a) AES has a 128-bit block, thus the construct will end with a 128-bit hash function, which can only give 64-bit collision resistance. b) AES is designed with a secret random key in mind, its resistance to related-key attack is less than perfect (especially for AES-256), and this could be an issue in this construction -or not-.
– fgrieu
Sep 30 '18 at 10:12

Constructing a compression function from a block cipher is a well-studied problem. There are some classical ways to do it, including Davies-Meyer, Miyaguchi-Preneel, Matyas-Meyer-Oseas, to name a few.

Preneel, Govaerts, & Vandewalle (Hash functions based on block ciphers: a synthetic approach) were the first to systematically look at all the ways to use a block cipher as compression function. They found 12 ways that are secure.

Later, Black, Rogaway, & Shrimpton (Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV) extended the analysis to include security proofs with quantitative bounds.

All of these constructions rely on treating the block cipher as an ideal cipher (like the random oracle model for block ciphers). As far as I know, there is no way to easily get a hash function from a block cipher using only its standard-model security.