Talk:One-way compression function: Difference between revisions

Revision as of 15:02, 1 December 2008

Revision as of 10:35, 19 February 2009

Line 3:

== Attack on Davies-Meyer ==

Ok, the merge of several other articles into this one is done, sort of. There is some more information in the [[Davies-Meyer hash|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. --[[User:Davidgothberg|David Göthberg]] 06:05, 28 January 2006 (UTC)

:The fixed point attack that I removed from the old Davies-Meyer article keeps coming back. That attack is not at all “easy” as some claim but requires exponential time (2^block size). The fixed point can be found easily only if the used block cipher has been already broken - and is easily broken. If the block cipher is secure then the Davies-Meyer is secure. [[User:Atwater|Atwater]] 19:00, 21 July 2006 (UTC) Atwater

::''According to Bruce Schneier this "is not really worth worrying about"[4]'' He probably meant '''in practice''', this is not worth worrying about. In the Eurocrypt 2005 paper with Kelsey, Schneier DOES use the fixpoint attack to show that the MD construction is far from being a random oracle, and so in a sense more brittle than one would wish it to be. However their attack is completely impractical because to be effective, it requires gigantic messages. [[User:71.142.222.181|71.142.222.181]] 19:04, 9 March 2007 (UTC)

My earlier statement (which I now have removed from this discussion) that the finding of a fixed point requires “exponential time” is not correct: it can be easily found for a block cipher. The correct way is to say that fixed points do not enable the attacker to go below the birthday paradox bound (2^n/2 time) when Merkle-Damgård (MD) strengthening (bitlength of the message is appended at its end) is used - however the fixed points enable to go below the more beautiful 2ⁿ limit as described in the attack of Kelsey and Schneier.

== Comparisons? ==