4
$\begingroup$

I am taking a cryptography class on Coursera. I learned that the compression function $h(H, m) = E_m(H) \oplus m$ is insecure (even though other variants like Davies­-Meyer or Miyaguchi-Preneel are secure). Why is this compression function insecure? What is the attack?

(See also Why are the Davies-Meyer and Miyaguchi-Preneel constructions secure? for a related question.)

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What exactly is the definition of $H$ and $E$? I guess $H$ is the IV or chaining value, and $E$ some form of encryption, but which? In particular which parameter is the key, and which the message? And is it AES, a PRP, or an ideal blockcipher? $\endgroup$ – CodesInChaos Apr 17 '13 at 21:04
  • $\begingroup$ Are you looking for an explanation of why the first one is insecure, or an explanation of why the latter ones are secure? Those are two different questions, and should be broken up into two separate questions here. For information on Davies-Meyer and Miyaguchi-Preneel, you might start with this page on Wikipedia. $\endgroup$ – D.W. Apr 17 '13 at 21:25
  • $\begingroup$ OK, I edited the question to match the title and focus on why this one construction is insecure. I moved the question about why D-M and M-P are secure to a different question; see the link. $\endgroup$ – D.W. Apr 17 '13 at 21:32
6
$\begingroup$

Well, the problem with $h(H,m) = E_m(H) \oplus m$ is that it makes the preimage attack easier than we'd expect; with a 128 bit hash, we'd hope that it'd take around $2^{128}$ attempts to find a preimage; with this compression function, we can find a preimage with only around $2^{64}$ effort.

This happens because this compression function is reversible; with a fixed m and a target value J, as one can efficiently find the H with $h(H,m)=J$, namely, $H = D_m(J \oplus m)$ (where $D_m$ is the decryption operation using $m$ as a key).

Here is how we use this property to find a message that hashes to $J$:

  • We select $2^{64}$ distinct initial blocks $m_1, m_2, ..., m_{2^{64}}$, and compute the $2^{64}$ values $h(H_0, m_i)$, where $H_0$ is the fixed IV of this hash function

  • We select $2^{64}$ distinct final blocks $n_1, n_2, ..., n_{2^{64}}$ and compute the $2^{64}$ values $h^{-1}(J, n_i)$, where $h^{-1}$ is the compression function run backwards.

Search the two lists for a common value; assuming a 128 bit hash, a collision is likely. If we find a pair with $h(H_0, m_i) = h^{-1}(J, n_j)$, when we have found a message $m_i || n_j$ which hashes to $J$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is true if E is 128 bit, but in the lecture slide [homework][1] the instructor did not specify encryption bits, consider a previous slide [example][2], is possible to construct a $H'$ that is not collision resistant to any random $m'$? [1]: i.imgur.com/NSuGUk3.jpg [2]: i.imgur.com/bX7mp2T.jpg $\endgroup$ – hgajshb Apr 17 '13 at 22:57
1
$\begingroup$

We can choose random $(H,m,m′)$ and construct $H′$ as follows: $$H' = D(m', E(m, H) \oplus m \oplus m')$$ Why is $E(m, H) \oplus H$ secure? Because you can't find a random $H'$ where $$H' = D(H', E(m, H) \oplus H \oplus H')$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ On the first half of your answer: The attack is a free-start attack on the scheme, and it requires the ability to freely choose the initial chaining value. It is not clear whether such an attack has any negative implications for the full hash function. poncho's answer is better, as it attacks the full hash function. On the second half of your answer: first, it belongs on the separate question. Second, it is not a correct description of why Davies-Meyer is secure. Just because one attack fails does not mean that other attacks will fail too. $\endgroup$ – D.W. Apr 18 '13 at 10:20
  • $\begingroup$ I think you are right on the latter part, there do have various attacks on encryption algorithms. $\endgroup$ – hgajshb Apr 18 '13 at 14:41

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.