12
$\begingroup$

The only Miyaguchi–Preneel MD hash I know is Whirlpool. I suppose there are likely others.

Miyaguchi-Preneel

Why do most MD hashes choose Davies–Meyer?

Davies-Meyer

If anything, Davies–Meyer relies on related-key resistance while Miyaguchi–Preneel relies on chosen-plaintext resistance. The former ought to be far more difficult to achieve.

So I'm curious about the rationale.

Edit:

After some further research all I could find was the fact that Davies-Meyer is more efficient because it allows you to stretch the message block based on how the key schedule of the underlying block cipher works. Whereas Miyaguchi–Preneel forces you have

length(key) = length(message block) = length(output)

and deviating from that while possible (with padding) complicates security. So I guess the question is whether that the only reason? Performance? Flexibility? SHA2 may not be able to have variants (eg: 256, 512) as easily with Miyaguchi-Preneel.

$\endgroup$
  • 1
    $\begingroup$ I don't know the answer, but I do know that Whirlpool uses a AES-like cipher, making the choice of Davies-Meyer with related-key resistance probably a no-go. That's just trying to answer the reverse question though :) $\endgroup$ – Maarten Bodewes Nov 17 '18 at 13:52
  • $\begingroup$ Note that (in theory) Davies-Meyer allows you to compute the key schedules only depending on the data input and can thus (in theory) be done in parallel with encryption eg the previous block, this could be nice for hardware implementations. $\endgroup$ – SEJPM Nov 18 '18 at 7:01
  • 1
    $\begingroup$ @MaartenBodewes I don't think that's true, because the Whirlpool compression function is more resistant against related-key attacks (it reuses the round function for the key-schedule). $\endgroup$ – Aleph Nov 18 '18 at 19:06
  • $\begingroup$ @Aleph Yeah, that would probably rule out related key attacks. Hmm. The problem with these why questions is that the reason for choosing one or the other is usually not documented. $\endgroup$ – Maarten Bodewes Nov 18 '18 at 21:34
  • 1
    $\begingroup$ These days, both designs, which involve keyed permutations, have been left by the wayside in favor of fixed permutations, like Keccak, like ChaCha (of which a variant appears in BLAKE and BLAKE2), like Gimli. $\endgroup$ – Squeamish Ossifrage Feb 27 at 20:12
4
$\begingroup$

Some ideas (not a definitive answer):

  1. Davies–Meyer is one of the two simplest among the 12 secure methods by which a block cipher and XOR can be turned into an iterative hash with one encryption per block, per the analysis of Bart Preneel, René Govaerts, Joos Vandewalle's Hash functions based on block ciphers: a synthetic approach, in proceedings of Crypto 1993.

    table 3
    Note: in the above table, the block cipher $E$ uses its first argument as key.
  2. Davies–Meyer (method 5) is the only of the 12 that works with a block cipher having a key of width different of its block without needing an adapter (the g in the first drawing of the question).
  3. When the key is wider than the block, that characteristic 2 makes Davies–Meyer use less encryptions for large messages, and that can translate into a speed advantage.
  4. MD4, which was influential on MD5, then SHA, SHA-1 and SHA-2, essentially used Davies–Meyer (except for replacement of XOR with modular addition on a word).
$\endgroup$
  • 2
    $\begingroup$ Davies–Meyer is not method 1 in that table. It's 5. $\endgroup$ – MikeDav77741 Nov 20 '18 at 19:15
  • $\begingroup$ @MikeDav77741 Indeed, method 1 is Matyas-Meyer-Oseas. $\endgroup$ – Aleph Nov 20 '18 at 19:54
1
$\begingroup$

The paper “The Maelstrom-0 hash function” [Filho D., Barreto P., Rijmen V.] presents Maelstrom-0 (as “an evolution of the Whirlpool hash function”). This paper contains the following information (see section 3):

Davies-Meyer is likely the most widely employed compression function in any concrete hash proposal. But more importantly, it is the only compression function among the 12 secure constructions analysed (in the context of a single-chain iterated hash function) by Black et al. [Black et al. 2002] that naturally allows the underlying block cipher to accept a key size different from the block size; all the remaining 11 functions XOR the key and the data block, thus forcing either truncation or padding to cope with the different sizes, and it is unclear to what extent truncation or padding might adversely affect the security analysis.

Quantitatively, the Miyaguchi-Preneel scheme is slightly more secure (by a roughly constant factor) than Davies-Meyer, but this difference is offset by the extra flexibility in the choice of the block cipher structure, which allows for faster hashing with the use of double-length keys.

$\endgroup$
  • $\begingroup$ Miyaguchi-Preneel is more secure? Under the ideal cipher model at least, I thought they were identical. $\endgroup$ – forest Mar 21 at 21:05

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.