AES-128 as compression function in Merkle-Damgard construction

Question

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.

Answer 1

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).

Answer 2

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.