3
$\begingroup$

I am learning the construction of Davies-Meyer to construct a hash function from block ciphers. The definition that I found is

$$H_i=E_{m_i}(H_{i-1})\oplus H_{i-1}.$$

where $E_k$ is a block cipher with key $k$.

My questions are:

1) Who is $H_0$, is the Initial Value (IV) as any hash function, that is Is that value public?

2) Suppose the follow case: the key size is 64 and the block size is 32, What happens if I need to evaluate the hash of the message $1$?

With respect to the question 2), I think that is necessary to complete with zeros until complete 64 bits the message $m_0 = 1$, then

$$H_1=E_{0000..00001}(IV)\oplus IV$$

but In this case it is easy to retrieve $m_0$ because the plaintext and the ciphertext are know. Where I am make mistake?


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

$\endgroup$
2
  • $\begingroup$ In this case it is easy to retrieve $m_0$ because the plaintext and the ciphertext are know. AES is a block cipher, but given a plain text and cipher text, it is still not possible to get the key. Moreover Differential/Linear cryptanalysis attacks are based on this knowledge and require far more than one pair plain text, cipher text to be efficient. $\endgroup$
    – Biv
    Dec 31, 2015 at 12:16
  • $\begingroup$ ok, then In this case the Davies-Mayer construction doesn't work? $\endgroup$
    – juaninf
    Dec 31, 2015 at 12:51

1 Answer 1

4
$\begingroup$

Is that value $H_0$ public?

Well, one property that a hash function has is that anyone can evaluate it. To evaluate a Davies-Mayer hash, you need the value $H_0$, and so yes, it needs to be public.

I think that is necessary to complete with zeros until complete 64 bits...

Minor correction there: while Davies-Mayer requires us to pad the message so that it is an even multiple of block sizes long (64 bits in your toy example), we wouldn't want to append zeros. The reason is that we hope that the hash function is collision-resistant (that is, someone couldn't find two different messages that hash to the same value); with the pad-by-appending-0's method, what someone could do is take a message, and append a 0 bit; as long as the original message wasn't a multiple of 64 bits, then the post-padded versions of the two messages would be identical, and so the hashes would be identical. What we could do instead is either append a '10000...000' pattern, or append a pattern that includes the original text length. Actually, common hash functions that are based on Davies-Mayer (SHA-1, SHA-2) do both.

In this case it is easy to retrieve $m_0$ because the plaintext and the ciphertext are known

First, a minor correction: the concern is not that we keep the message secret, but instead that it should be infeasible to find preimages; that is, given a hash value, it should be infeasible to find a message that hashes to that hash value (and it doesn't matter if the message that the attacker finds is the same message that was originally hashed).

In any case, no, it is not easy to find a value $m_0$, if we assume that $E$ is a strong block cipher. With strong block ciphers, we make the assumption that, given a plaintext/ciphertext pair, we cannot recover the key. This implies that there isn't a direct way to immediately recover $m_0$.

Of course, with the parameters that you give (32 bit block size), what an attacker could do is try $2^{32}$ different $m_0$ candidates; if he hashes all those values, he is likely to find one that hashes to the $H_1$ value. Because of this, Davies-Mayer requires us to use block ciphers with much larger block sizes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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