Content deleted Content added
m →Attack on Davies-Meyer: Signed my change. |
→Attack on Davies-Meyer: Clarified that the Kelsey, Schneier attack applies to every Merkle-Damgård construction. |
||
Line 7:
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<sup>n/2</sup> 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<sup>n</sup> limit as described in the attack of Kelsey and Schneier.[[User:Atwater|Atwater]] ([[User talk:Atwater|talk]]) 10:39, 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)
== Comparisons? ==
| |||