Content deleted Content added
Bjoern.fay (talk | contribs) Added short description of new method NBOW. |
→Davies–Meyer: Close unclosed bracket Tags: Mobile edit Mobile web edit |
||
Line 94:
Variations of this method replace XOR with any other group operation, such as addition on 32-bit unsigned integers.
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 <math>m_1</math>, attacker finds another message <math>m_2</math> to satisfy <math>\operatorname{hash}(m_1) = \operatorname{hash}(m_2)</math>) of Kelsey and Schneier <ref name="ks05"/> for a <math>2^k</math>-message-block message in time <math>3 \times 2^{n/2+1} + 2^{n-k+1}</math>. 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 <math>k \times 2^{n/2+1} + 2^{n-k+1}</math> time. Note that in both cases the complexity is above <math>2^{n/2}</math> but below <math>2^n</math> when messages are long and that when messages get shorter the complexity of the attack approaches <math>2^n</math>.
The security of the Davies–Meyer construction in the Ideal Cipher Model was first proven 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>
| |||