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

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

-
I try to help keep the site clean, by separating separate questions into separate pages, and the question gets downvoted? Hmm.... I'm not seeing what is wrong with the question. – D.W. Apr 18 '13 at 10:27

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

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's the definition of an ideal cipher.

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.

-
I want to thank the description of an ideal cipher. I have been looking for one and they are all overly complicated. This is perfect – bubblebath May 2 '14 at 13:21