One-way compression function: Difference between revisions

Revision as of 16:39, 23 May 2024

Latest revision as of 11:37, 24 March 2025

(3 intermediate revisions by 3 users not shown)

Line 42:

When length padding (also called MD-strengthening) is applied, attacks cannot find collisions faster than the birthday paradox (<math>2^{n/2}</math>, <math>n</math> being the block size in bits) if the used function <math>f</math> is collision-resistant.<ref name="damgard89">Ivan Damgård. [https://link.springer.com/content/pdf/10.1007%2F0-387-34805-0_39.pdf A design principle for hash functions]. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 416–427. Springer, 1989.</ref><ref name="merkle89">Ralph Merkle. [https://link.springer.com/content/pdf/10.1007%2F0-387-34805-0_40.pdf One way hash functions and DES]. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 428–446. Springer, 1989.</ref> Hence, the Merkle–Damgård hash construction reduces the problem of finding a proper hash function to finding a proper compression function.

A second preimage attack (given a message <math>m_1</math> an attacker finds another message <math>m_2</math> to satisfy <math>\operatorname{hash}(m_1) = \operatorname{hash}(m_2)</math> can be done according to Kelsey and Schneier<ref name="ks05">John Kelsey and Bruce Schneier. [https://www.schneier.com/academic/paperfiles/paper-preimages.pdf Second preimages on ''n''-bit hash functions for much less than 2^''n'' work]. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 474–490. Springer, 2005.</ref> for a <math>2^k</math>-message-block message in time <math>k \times 2^{n/2+1} + 2^{n-k+1}</math>. Note that theThe complexity of this attack reaches a minimum of <math>2^{3n/4+2}</math> for long messages when <math>k = 2^{n/4}</math> and approaches <math>2^n</math> when messages are short.

{{clear}}

Line 80:

[[Image:Davies-Meyer hash.svg|thumb|230px|right|The Davies–Meyer one-way compression function]]

The Davies–Meyer single-block-length compression function feeds each block of the message (<math>m_i</math>) as the key to a block cipher. It feeds the previous hash value (<math>H_{i-1}</math>) as the plaintext to be encrypted. The output ciphertext is then also [[exclusive-or|XORed]] (⊕) with the previous hash value (<math>H_{i-1}</math>) to produce the next hash value (<math>H_i</math>). In the first round when there is no previous hash value it uses a constant pre-specified initial value (<math>H_0</math>).

In [[mathematical notation]] Davies–Meyer can be described as:

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 inIn 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>

Line 116:

:<math>R_{MMO} = \frac{n}{1\cdot n} = 1</math>

A second preimage attack (given a message <math>m_1</math> an attacker finds another message <math>m_2</math> to satisfy <math>\operatorname{hash}(m_1) = \operatorname{hash}(m_2)</math>) can be done according to Kelsey and Schneier<ref name="ks05"/> for a <math>2^k</math>-message-block message in time <math>k \times 2^{n/2+1} + 2^{n-k+1}</math>. Note that theThe 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>.

== Miyaguchi–Preneel ==

Line 138:

{{clear}}

A second preimage attack (given a message <math>m_1</math> an attacker finds another message <math>m_2</math> to satisfy <math>\operatorname{hash}(m_1) = \operatorname{hash}(m_2)</math>) can be done according to Kelsey and Schneier<ref name="ks05"/> for a <math>2^k</math>-message-block message in time <math>k \times 2^{n/2+1} + 2^{n-k+1}</math>. Note that theThe 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>.

== Hirose ==