::''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” iswas not correct: itfixed point can be easily found for a blockDavies-Meyer cipherconstruction. The correct way is to say that fixed points do not enable the attacker to go below the birthday paradox bound (2<sup>n/2</sup> time) when Merkle-Damgård (MD) strengthening (bitlength of the message is appended at its end) is used. - howeverHowever 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 2<sup>k</sup>-message-block message the attack requires 3 x 2<sup>n/2+1</sup>+2<sup>n-k+1</sup> time which does not go below the morebeautifulbirthday paradox (2<sup>n/2</sup>) limit. asIf describedfixed inpoints 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 2<sup>n/2+1</sup>+2<sup>n-k+1</sup> time. Note that when messages get shorter the complexity of Kelseythe andattack Schneierapproaches 2<sup>n</sup>.[[User:Atwater|Atwater]] ([[User talk:Atwater|talk]]) 1016:3924, 19 February 2009 (UTC)
One should also note that 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 2<sup>k</sup>-message-block message the attack requires 3 x 2<sup>n/2+1</sup>+2<sup>n-k+1</sup> time which does not go below the birthday paradox (2<sup>n/2</sup>) limit but goes below the more beautiful 2<sup>n</sup> 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 2<sup>n/2+1</sup>+2<sup>n-k+1</sup> time. Note that when messages get shorter the complexity of the attack approaches 2<sup>n</sup>.[[User:Atwater|Atwater]] ([[User talk:Atwater|talk]]) 12:38, 19 February 2009 (UTC)
