Content deleted Content added
No edit summary |
→Davies–Meyer: Remove "Most widely used hash functions, including MD5, SHA-1 and SHA-2 use this construction.". They use Merkle-Damgaard, not Davies-Meyer. |
||
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 <math>m</math>, one can find a value of <math>h</math> 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 x 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 x 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 proved by R. Winternitz.<ref>R. Winternitz. ''A secure one-way hash function built from DES.'' In Proceedings of the IEEE Symposium on Information Security and Privacy, p. 88-90. IEEE Press, 1984.</ref>
| |||