One-way compression function: Difference between revisions

Revision as of 20:05, 8 March 2021

Latest revision as of 11:37, 24 March 2025

(17 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Cryptographic primitive}}

In [[cryptography]], a '''one-way compression function''' is a function that transforms two fixed-length inputs into a fixed-length output.<ref name=":0">Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 328.</ref> The transformation is [[one-way function|"one-way"]], meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional [[data compression]] algorithms, which instead can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data.

[[Image:One-way compression.svg|thumb|upright=0.8|right|A one-way compression function]]

Line 7 ⟶ 8:

One-way compression functions are often built from [[block cipher]]s.

Some methods to turn any normal block cipher into a one-way compression function are '''Davies–Meyer''', '''Matyas–Meyer–Oseas''', '''Miyaguchi–Preneel''' (single-block-length compression functions) and '''MDC-2/Meyer–Schilling''', '''MDC-4''', '''Hirose''' (double-block-length compression functions). These methods are described in detail further down. ([[MDC-2]] is also the name of a hash function patented by [[IBM]].)

Another method is '''2BOW''' (or '''NBOW''' in general), which is a "high-rate multi-block-length hash function based on block ciphers"<ref name=":0" /> and typically achieves (asymptotic) rates between 1 and 2 independent of the hash size (only with small constant overhead). This method has not yet seen any serious security analysis, so should be handled with care.

== Compression ==

Line 24 ⟶ 27:

* Easy to compute: If you have some input(s), it is easy to calculate the output.

* Preimage-resistance: If an attacker only knows the output it should be infeasible to calculate an input. In other words, given an output <math>h</math>, it should be unfeasible to calculate an input <math>m</math> such that <math>\operatorname{hash}(m)=h</math>.

* Second preimage-resistance: Given an input <math>m_1</math> whose output is <math>h</math>, it should be infeasible to find another input <math>m_2</math> that has the same output <math>h</math>, i.e. <math>\operatorname{hash}(m_1) \ne= \operatorname{hash}(m_2)</math>.

* [[Collision resistance|Collision-resistance:]] It should be hard to find any two different inputs that compress to the same output i.e. an attacker should not be able to find a pair of messages <math>m_1 \ne m_2</math> such that <math>\operatorname{hash}(m_1) = \operatorname{hash}(m_2)</math>. Due to the [[Birthday problem|birthday paradox]] (see also [[birthday attack]]) there is a 50% chance a collision can be found in time of about <math>2^{n/2}</math> where <math>n</math> is the number of bits in the hash function's output. An attack on the hash function thus should not be able to find a collision with less than about <math>2^{n/2}</math> work.

Line 35 ⟶ 38:

A common use of one-way compression functions is in the Merkle–Damgård construction inside cryptographic hash functions. Most widely used hash functions, including [[MD5]], [[SHA-1]] (which is deprecated<ref>{{Cite web|url=https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html| title=Announcing the first SHA1 collision|website=Google Online Security Blog| language=en|access-date=2020-01-12}}</ref>) and [[SHA-2]] use this construction.

A hash function must be able to process an arbitrary-length message into a fixed-length output. This can be achieved by breaking the input up into a series of equal-sized blocks, and operating on them in sequence using a one-way compression function. The compression function can either be specially designed for hashing or be built from a block cipher. The last block processed should also be [[Padding (cryptography)|length padded]], which is crucial to the security of this construction.

The last block processed should also be [[Padding (cryptography)|length padded]], this is crucial to the security of this construction. This construction is called the [[Merkle–Damgård construction]]. Most widely used hash functions, including [[SHA-1]] and [[MD5]], take this form.

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 93 ⟶ 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 115 ⟶ 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 137 ⟶ 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 ==