![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||
|
Ok, the merge of several other articles into this one is done, sort of. There is some more information in the old Davies-Meyer article about an attack that I did not merge since I did not understand it. If I just cut and paste that paragraph it will make even less sense since it depends on the notification established further up in the old article and I have changed that notification in this article. So for now I left the old Davies-Meyer article as it is (not turned it into a redirect). I left a note about it and link to it in the Davies-Meyer section of this article. I hope some one can make sense to it and rewrite it properly and merge it some day. -- David Göthberg 06:05, 28 January 2006 (UTC)
My earlier statement (which I now have removed from this discussion) that the finding of a fixed point requires “exponential time” was not correct: fixed point can be easily found for a Davies-Meyer construction. The correct way is to say that fixed points do not enable the attacker to go below the birthday paradox bound (2n/2 time) when Merkle-Damgård (MD) strengthening (bitlength of the message is appended at its end) is used. However the fixed points enable a slightly more efficient second preimage attack than a Merkle-Damgård construction whose f-function does not provide easy calculation of fixed points. The Kelsey and Schneier attack applies to every Merkle-Damgård construction, not just the Davies-Meyer. For Davies-Meyer (using fixed points) to attack a 2k-message-block message the attack requires 3 x 2n/2+1+2n-k+1 time which does not go below the birthday paradox (2n/2) limit. If fixed points are not used i.e. the construction is other than Davies-Meyer (e.g Matyas-Meyer-Oseas, Miyaguchi-Preneel) then this attack can be done in k x 2n/2+1+2n-k+1 time. Note that when messages get shorter the complexity of the attack approaches 2n. Atwater ( talk) 16:24, 19 February 2009 (UTC)
I'm curious if one of these methods is preferred to another in general, or under certain circumstances. Are there certain applications where one method is more appropriate than another? 150.135.65.20 19:05, 30 January 2006 (UTC)
The Skein (hash function) designers specifically chose "Matyas-Meyer-Oseas" over "Davies-Meyer". Page 44 of "The Skein Hash Function Family" briefly gives a couple of reasons. Do any of those reasons apply to the "Miyaguchi-Preneel" arrangement? Could someone explain those reasons in this article? -- 68.0.124.33 ( talk) 15:02, 1 December 2008 (UTC)
I took the liberty to revert to the first image. (The colourful one made by me but which really is only a slight extension of Matt_Crypto's old version.) Note that the other pictures on this page on purpose is colourmatched with this image (yellow boxes) to make it clearer where they fit in the Merkle-Damgård structure. I have tested the different images on the chatters in #crypto on irc.freenode.net and they prefered the colourful version. -- David Göthberg 08:10, 6 March 2006 (UTC)
"The resulting hash size is big enough. 64-bit is too small, 128-bit might be enough."
What does this mean? What are the criteria? If your 128-bit key is secure, shouldn't it require 2^64 operations to find even a collision? Why isn't that big enough? Or is there something being left unsaid about how secure the block based ciphers are?
-- 72.18.229.146 00:21, 29 August 2006
I see a function E() in the equations, but I can't figure out from the context what this function is. Could someone fill it in more completely? User:mbset 13:50, 9 June 2007
I moved this article from Hash functions based on block ciphers to One-way compression function since that is what this article really is about. The Merkle-Damgård hash function article takes care of the rest of the description of how compression functions are used to build hashes. -- David Göthberg 04:52, 26 July 2007 (UTC)
What in the world does this statement mean? It makes the entire article rather confusing. Do we mean "If the block cipher is ideal"? I'm not even sure that statement holds w.r.t. all of these constructions. This needs to be fixed, removed, elaborated on. Any suggestions?
Might be useful to note that block ciphers with expensive key setup (e.g. Twofish) do not interact well with any of these constructions because the key setup must be done once for every message block. Aragorn2 ( talk) 11:31, 12 June 2019 (UTC)
![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||
|
Ok, the merge of several other articles into this one is done, sort of. There is some more information in the old Davies-Meyer article about an attack that I did not merge since I did not understand it. If I just cut and paste that paragraph it will make even less sense since it depends on the notification established further up in the old article and I have changed that notification in this article. So for now I left the old Davies-Meyer article as it is (not turned it into a redirect). I left a note about it and link to it in the Davies-Meyer section of this article. I hope some one can make sense to it and rewrite it properly and merge it some day. -- David Göthberg 06:05, 28 January 2006 (UTC)
My earlier statement (which I now have removed from this discussion) that the finding of a fixed point requires “exponential time” was not correct: fixed point can be easily found for a Davies-Meyer construction. The correct way is to say that fixed points do not enable the attacker to go below the birthday paradox bound (2n/2 time) when Merkle-Damgård (MD) strengthening (bitlength of the message is appended at its end) is used. However the fixed points enable a slightly more efficient second preimage attack than a Merkle-Damgård construction whose f-function does not provide easy calculation of fixed points. The Kelsey and Schneier attack applies to every Merkle-Damgård construction, not just the Davies-Meyer. For Davies-Meyer (using fixed points) to attack a 2k-message-block message the attack requires 3 x 2n/2+1+2n-k+1 time which does not go below the birthday paradox (2n/2) limit. If fixed points are not used i.e. the construction is other than Davies-Meyer (e.g Matyas-Meyer-Oseas, Miyaguchi-Preneel) then this attack can be done in k x 2n/2+1+2n-k+1 time. Note that when messages get shorter the complexity of the attack approaches 2n. Atwater ( talk) 16:24, 19 February 2009 (UTC)
I'm curious if one of these methods is preferred to another in general, or under certain circumstances. Are there certain applications where one method is more appropriate than another? 150.135.65.20 19:05, 30 January 2006 (UTC)
The Skein (hash function) designers specifically chose "Matyas-Meyer-Oseas" over "Davies-Meyer". Page 44 of "The Skein Hash Function Family" briefly gives a couple of reasons. Do any of those reasons apply to the "Miyaguchi-Preneel" arrangement? Could someone explain those reasons in this article? -- 68.0.124.33 ( talk) 15:02, 1 December 2008 (UTC)
I took the liberty to revert to the first image. (The colourful one made by me but which really is only a slight extension of Matt_Crypto's old version.) Note that the other pictures on this page on purpose is colourmatched with this image (yellow boxes) to make it clearer where they fit in the Merkle-Damgård structure. I have tested the different images on the chatters in #crypto on irc.freenode.net and they prefered the colourful version. -- David Göthberg 08:10, 6 March 2006 (UTC)
"The resulting hash size is big enough. 64-bit is too small, 128-bit might be enough."
What does this mean? What are the criteria? If your 128-bit key is secure, shouldn't it require 2^64 operations to find even a collision? Why isn't that big enough? Or is there something being left unsaid about how secure the block based ciphers are?
-- 72.18.229.146 00:21, 29 August 2006
I see a function E() in the equations, but I can't figure out from the context what this function is. Could someone fill it in more completely? User:mbset 13:50, 9 June 2007
I moved this article from Hash functions based on block ciphers to One-way compression function since that is what this article really is about. The Merkle-Damgård hash function article takes care of the rest of the description of how compression functions are used to build hashes. -- David Göthberg 04:52, 26 July 2007 (UTC)
What in the world does this statement mean? It makes the entire article rather confusing. Do we mean "If the block cipher is ideal"? I'm not even sure that statement holds w.r.t. all of these constructions. This needs to be fixed, removed, elaborated on. Any suggestions?
Might be useful to note that block ciphers with expensive key setup (e.g. Twofish) do not interact well with any of these constructions because the key setup must be done once for every message block. Aragorn2 ( talk) 11:31, 12 June 2019 (UTC)