Content deleted Content added
ReiniUrban (talk | contribs) →Davies–Meyer: Typo Tags: Mobile edit Mobile web edit Advanced mobile edit |
|||
Line 93:
A notable property of the Davies–Meyer construction is that even if the underlying block cipher is totally secure, it is possible to compute [[Fixed point (mathematics)|fixed points]] for the construction: for any {{mvar|m}}, one can find a value of {{mvar|h}} such that <math>E_m(h) \oplus h = h</math>: one just has to set <math>h = E_m^{-1}(0)</math>.<ref>Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 375.</ref> This is a property that [[random function]]s certainly do not have. So far, no practical attack has been based on this property, but one should be aware of this "feature". The fixed-points can be used in a second preimage attack (given a message m1, attacker finds another message m2 to satisfy hash(m1) = hash(m2)) of Kelsey and Schneier <ref name="ks05"/> for a 2<sup>k</sup>-message-block message in time 3 × 2<sup>n/2+1</sup>+2<sup>n-k+1</sup> . If the construction does not allow easy creation of fixed points (like Matyas–Meyer–Oseas or Miyaguchi–Preneel) then this attack can be done in k × 2<sup>n/2+1</sup>+2<sup>n-k+1</sup> time. Note that in both cases the complexity is above 2<sup>n/2</sup> but below 2<sup>n</sup> when messages are long and that when messages get shorter the complexity of the attack approaches 2<sup>n</sup>.
The security of the Davies–Meyer construction in the Ideal Cipher Model was first
{{clear}}
| |||