Why are the Davies-Meyer and Miyaguchi-Preneel constructions secure?

Question

The Davies-Meyer compression function $h(H, m) = E_m(H) \oplus H$ is said to be secure. So too is the Miyaguchi-Preneel compression function $h(H, m) = E_m(H) \oplus m \oplus H$. Why are these secure? How do we know that they are secure?

(Here $E$ is a block cipher with $n$-bit key and $n$-bit plaintext; $E_k(x)$ denotes encryption of plaintext $x$ under key $k$. This question is based upon one originally asked by yanglifu90.)

Answer 1

The detailed technical analysis is given in the following research paper:

• Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. John Black, Philip Rogaway, Tom Shrimpton. CRYPTO 2002.

They show that Davies-Meyer and Miyaguchi-Preneel are secure, assuming the block ciphers can be modelled as "ideal ciphers" (that have no regularities or patterns beyond that implicit in the very definition of a block cipher).

In a nutshell, an ideal cipher assumes that, for each key $k$, the function $E_k(\cdot)$ can be treated as a totally random permutation on the set of all $2^n$ possible texts, and these permutations for different keys $k$ are independent.

In other words, you can think of an "ideal cipher" as a black box where you send it a key $k$ and a plaintext $x$ and it responds with a ciphertext $c$. It behaves in a very special way. When you feed it a key $k$ and plaintext $x$, it picks a totally random ciphertext $c$ uniformly at random and gives you $c$, subject only to the following two consistency restrictions:

1. if you've previously queried the black box on the same key $k$ and the same plaintext $x$, then it will respond the same way it previously did, and
2. if you've previously queried the black box on the same key $k$ and a different plaintext $x'$ (where $x'\ne x$) and got back the response $y'$, then this time the black box won't respond with $y'$ again (it'll respond with some $y$ such that $y \ne y'$)--in short, it'll never give the same response to two different queries with the same key but different plaintexts.

That gives the flavor of the model, but it's not quite sufficient, because it only models encryption, but not decryption. In actuality, we model this with two black boxes: one that emulates $E_k(\cdot)$, and one that emulates $E_k^{-1}(\cdot)$. It's a bit tricky to describe how they work, but it goes like this:

1. If you query $E_k(x)$ and you've previously queried the $E_\cdot(\cdot)$ black box with the same key $k$ and the same input $x$, then it will respond with the same value it previously did;

2. If you query $E_k^{-1}(x)$ and you've previously queried the $E_\cdot^{-1}(\cdot)$ black box with the same key $k$ and the same input $x$, then it will respond with the same value it previously did;

3. If you query $E_k(x)$ and there was some prior query to the $E_\cdot^{-1}(\cdot)$ black box with key $k$ and some input $y$ and it responded with the output $x$, then this query will respond with $y$;

4. If you query $E_k^{-1}(x)$ and there was some prior query to the $E_\cdot(\cdot)$ black box with key $k$ and some input $x$ and it responded with the output $y$, then this query will respond with $x$;

5. If you query $E_k(x)$ and none of the above conditions hold, then the box will randomly pick a value $y$ that is different from the responses from all prior responses to queries of the form $E_k(x')$ (i.e., same key but different input) and that is different from all the inputs $y$ that were submitted to the $E_\cdot^{-1}(\cdot)$ box with key $k$.

6. If you query $E_k^{-1}(y)$ and none of the above conditions hold, then do something similar.

That's the definition of an ideal cipher. It turns out that this is equivalent to picking $2^{n'}$ different, independent random permutations on $2^n$ texts (one permutation per key).

It is possible to use various mathematical techniques to prove that if you apply the Davies-Meyer or Miyaguchi-Preneel construction to an ideal cipher, the result will be a secure compression function. Therefore, if our block cipher acts like an ideal cipher, then we can expect that Davies-Meyer and Miyaguchi-Preneel ought to be secure.

That's the basic idea. You'll need to read the research literature to get the full details.