8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 18 '13 at 10:27
9
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – bubblebath May 2 '14 at 13:21
  • $\begingroup$ The above definition of an ideal cipher is not the standard one used by Black, Rogaway, and Shrimpton. The definition they use also allows decryption queries, which is clearly essential for modelling actual block ciphers. In general, an efficient decryption oracle cannot be obtained directly from the encryption oracle. $\endgroup$ – Daira Hopwood Nov 24 '18 at 5:43
  • 1
    $\begingroup$ @DairaHopwood, oh gosh, you're right of course, thank you! I've updated my answer -- I hope I got it right now. $\endgroup$ – D.W. Nov 24 '18 at 7:55
  • $\begingroup$ Yes that looks correct now. You're welcome :-) $\endgroup$ – Daira Hopwood Dec 1 '18 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.