One-way compression function: Difference between revisions

Revision as of 22:42, 5 January 2018

Latest revision as of 11:37, 24 March 2025

(40 intermediate revisions by 29 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|200pxupright=0.8|right|A one-way compression function]]

One-way compression functions are for instance used in the [[Merkle–Damgård construction]] inside [[cryptographic hash function]]s.

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 13 ⟶ 16:

For instance, ''input A'' might be 128 bits, ''input B'' 128 bits and they are compressed together to a single output of 128 bits. This is equivalent to having a single 256-bit input compressed to a single output of 128 bits.

Some compression functions do not compress by half, but instead by some other factor. For example, ''input A'' might be 256 bits, and '''input B''' 128 bits, which are compressed to a single output of 128 bits. That is, a total of 384 input bits are compressed together to 128 output bits.

The mixing is done in such a way that full [[avalanche effect]] is achieved. That is, every output bit depends on every input bit.

Line 23 ⟶ 26:

* 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 unfeasibleinfeasible 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 ''m1''<math>m_1</math> whose output is ''<math>h''</math>, it should be unfeasibleinfeasible to find another input ''m2''<math>m_2</math> that has the same output ''<math>h''</math>, i.e. ''<math>\operatorname{hash''}(''m1''m_1) ='' \operatorname{hash''}(''m2''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 m1<math>m_1 ≠\ne m2m_2</math> such that ''<math>\operatorname{hash''}(''m1''m_1) = ''\operatorname{hash''}(''m2''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 2<supmath>2^{n/2}</supmath> 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 2<supmath>2^{n/2}</supmath> work.

Ideally one would like the "unfeasibilityinfeasibility" in preimage-resistance and second preimage-resistance to mean a work of about 2<supmath>2^n</supmath> where <math>n</math> is the number of bits in the hash function's output. However, particularly for second preimage-resistance this is a difficult problem.{{Citation needed|date=October 2013}}

== The Merkle–Damgård construction ==

Line 33 ⟶ 36:

[[Image:Merkle-Damgard hash big.svg|thumb|400px|right|The Merkle–Damgård hash construction. The boxes labeled [f] are a one-way compression function.]]

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.

When length padding (also called MD-strengthening) is applied, attacks cannot find collisions faster than the birthday paradox (2<supmath>2^{n/2}</supmath>, <math>n</math> isbeing the block size in bits) if the used f-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.

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.

A second preimage attack (given a message m1<math>m_1</math> an attacker finds another message m2<math>m_2</math> to satisfy <math>\operatorname{hash}(m1m_1) = \operatorname{hash}(m2)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 2<supmath>2^k</supmath>-message-block message in time <math>k &\times; 2^{^{n/2+1}} + 2<sup>^{n-k+1}</supmath>. NoteThe thatcomplexity theof complexitythis isattack abovereaches a minimum of 2<supmath>n2^{3n/4+2}</supmath> butfor belowlong messages when 2<supmath>k = 2^{n/4}</supmath> when messages are long and that when messages get shorter the complexity of the attack approaches 2<supmath>2^n</supmath> when messages are short.

When length padding (also called MD-strengthening) is applied, attacks cannot find collisions faster than the birthday paradox (2^n/2, n is the block size in bits) if the used f-function is collision-resistant.<ref name="damgard89">Ivan Damgård. 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. 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 m1 an attacker finds another message m2 to satisfy hash(m1) = hash(m2)) can be done according to Kelsey and Schneier<ref name="ks05">John Kelsey and Bruce Schneier. Second preimages on n-bit hash functions for much less than 2ⁿ work. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 474–490. Springer, 2005.</ref> for a 2^k-message-block message in time k &times; 2^n/2+1+2^n-k+1. Note that the complexity is above 2^n/2 but below 2ⁿ when messages are long and that when messages get shorter the complexity of the attack approaches 2ⁿ.

{{clear}}

== Construction from block ciphers ==

[[Image:Block cipher.svg|thumb|200pxupright=0.8|right|A typical modern block cipher]]

One-way compression functions are often built from block ciphers.

Line 59 ⟶ 60:

If a block cipher has a [[Block size (cryptography)|block size]] of say 128 bits single-block-length methods create a hash function that has the block size of 128 bits and produces a hash of 128 bits. Double-block-length methods make hashes with double the hash size compared to the block size of the block cipher used. So a 128-bit block cipher can be turned into a 256-bit hash function.

These methods are then used inside the Merkle-DamgårdMerkle–Damgård construction to build the actual hash function. These methods are described in detail further down.

Using a block cipher to build the one-way compression function for a hash function is usually somewhat slower than using a specially designed one-way compression function in the hash function. This is because all known secure constructions do the [[Key schedule|key scheduling]] for each block of the message. Black, Cochran and Shrimpton have shown that it is impossible to construct a one-way compression function that makes only one call to a block cipher with a fixed key.<ref>John Black, Martin Cochran, and Thomas Shrimpton. ''On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions.'' Advances in Cryptology – EUROCRYPT '05, Aarhus, Denmark, 2005. The authors define a hash function "highly efficient if its compression function uses exactly one call to a block cipher whose key is fixed".</ref> In practice reasonable speeds are achieved provided the key scheduling of the selected block cipher is not a too heavy operation.

But, in some cases it is easier because a single implementation of a block cipher can be used for both a block cipher and a hash function. It can also save [[machine code|code]] space in very tiny [[embedded system]]s like for instance [[smart card]]s or [[Electronic control unit|nodes in cars]] or other machines.

Therefore, the hash-rate or rate gives a glimpse of the efficiency of a hash function based on a certain compression function. The rate of an iterated hash function outlines the ratio between the number of block cipher operations and the output. More precisely, if n denotes the output bit-length of the block cipher the rate represents the ratio between the number of processed bits of input <math>m</math>, nthe output bitsbit-length <math>n</math> of the block cipher, and the necessary block cipher operations <math>s</math> to produce these <math>n</math> output bits. Generally, the usage of fewer block cipher operations could resultresults in a better overall performance of the entire hash function, but it also leads to a smaller hash-value which could be undesirable. The rate is expressed by the formula :

<math>R_h=\frac{\left|m_i\right|}{s\cdot n}</math>.

The hash function can only be considered secure if at least the following conditions are met:

* The block cipher has no special properties that distinguish it from ideal ciphers, such as for example weak keys or keys that lead to identical or related encryptions (fixed points or key-collisions).

* The resulting hash size is big enough. According to the [[birthday attack]] a [[security level]] of 2⁸⁰ (generally assumed to be infeasible to compute today){{Citation needed|date=October 2015}} is desirable thus the hash size should be at least 160 bits.

* The last block is properly length padded prior to the hashing. (See [[Merkle–Damgård construction]].) Length padding is normally implemented and handled internally in specialised hash functions like [[SHA-1]] etc.

Line 77 ⟶ 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 (m<submath>im_i</submath>) as the key to a block cipher. It feeds the previous hash value (H<submath>H_{i-1}</submath>) as the plaintext to be encrypted. The output ciphertext is then also [[exclusive-or|XORed]] (⊕) with the previous hash value (H<submath>H_{i-1}</submath>) to produce the next hash value (H<submath>iH_i</submath>). In the first round when there is no previous hash value it uses a constant pre-specified initial value (H<submath>0H_0</submath>).

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

:<math>H_i = E_{m_i}{(H_{i-1})} \oplus {H_{i-1}}.</math>

The scheme has the rate (k is the keysize):

:<math>R_{DM}=\frac{k}{1\cdot n} = \frac{k}{n}.</math>

If the block cipher uses for instance 256-bit keys then each message block (m<submath>im_i</submath>) is a 256-bit chunk of the message. If the same block cipher uses a block size of 128 bits then the input and output hash values in each round is 128 bits.

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 {{mvar|<math>m}}</math>, one can find a value of {{mvar|<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<math>m_1</math>, attacker finds another message m2<math>m_2</math> to satisfy <math>\operatorname{hash}(m1m_1) = \operatorname{hash}(m2m_2) </math>) of Kelsey and Schneier <ref name="ks05"/> for a 2<supmath>2^k</supmath>-message-block message in time <math>3 &\times; 2^{^{n/2+1}} + 2<sup>^{n-k+1}</supmath> . 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<sup>^{n-k+1}</supmath> time. Note that inIn both cases the complexity is above 2<supmath>2^{n/2}</supmath> but below 2<supmath>2^n</supmath> when messages are long and that when messages get shorter the complexity of the attack approaches 2<supmath>2^n</supmath>.

The security of the Davies–Meyer construction in the Ideal Cipher Model was first provedproven 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>

{{clear}}

Line 101 ⟶ 104:

The Matyas–Meyer–Oseas single-block-length one-way compression function can be considered the dual (the opposite) of Davies–Meyer.

It feeds each block of the message (m<submath>im_i</submath>) as the plaintext to be encrypted. The output ciphertext is then also XORed (⊕) with the same message block (m<submath>im_i</submath>) to produce the next hash value (H<submath>iH_i</submath>). The previous hash value (H<submath>H_{i-1}</submath>) is fed as the key to the block cipher. In the first round when there is no previous hash value it uses a constant pre-specified initial value (H<submath>0H_0</submath>).

If the block cipher has different block and key sizes the hash value (H<submath>H_{i-1}</submath>) will have the wrong size for use as the key. The cipher might also have other special requirements on the key. Then the hash value is first fed through the function <math>g( )</math> to be converted/padded to fit as key for the cipher.

In mathematical notation Matyas–Meyer–Oseas can be described as:

:<math>H_i = E_{g(H_{i-1})}(m_i)\oplus m_i.</math>

The scheme has the rate:

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

A second preimage attack (given a message m1<math>m_1</math> an attacker finds another message m2<math>m_2</math> to satisfy <math>\operatorname{hash}(m1m_1) = \operatorname{hash}(m2m_2) </math>) can be done according to Kelsey and Schneier<ref name="ks05"/> for a 2<supmath>2^k</supmath>-message-block message in time <math>k &\times; 2^{^{n/2+1}} + 2<sup>^{n-k+1}</supmath>. Note that theThe complexity is above 2<supmath>2^{n/2}</supmath> but below 2<supmath>2^n</supmath> when messages are long, and that when messages get shorter the complexity of the attack approaches 2<supmath>2^n</supmath>.

== Miyaguchi–Preneel ==

Line 120 ⟶ 123:

The Miyaguchi–Preneel single-block-length one-way compression function is an extended variant of Matyas–Meyer–Oseas. It was independently proposed by [[Shoji Miyaguchi]] and [[Bart Preneel]].

It feeds each block of the message (m<submath>im_i</submath>) as the plaintext to be encrypted. The output ciphertext is then XORed (⊕) with the same message block (m<submath>im_i</submath>) and then also XORed with the previous hash value (H<submath>H_{i-1}</submath>) to produce the next hash value (H<submath>iH_i</submath>). The previous hash value (H<submath>H_{i-1}</submath>) is fed as the key to the block cipher. In the first round when there is no previous hash value it uses a constant pre-specified initial value (H<submath>0H_0</submath>).

If the block cipher has different block and key sizes the hash value (H<submath>H_{i-1}</submath>) will have the wrong size for use as the key. The cipher might also have other special requirements on the key. Then the hash value is first fed through the function <math>g( )</math> to be converted/padded to fit as key for the cipher.

In mathematical notation Miyaguchi–Preneel can be described as:

:<math>H_i = E_{g(H_{i-1})}(m_i)\oplus H_{i-1}\oplus m_i.</math>

The scheme has the rate:

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

The roles of m<submath>im_i</submath> and H<submath>H_{i-1}</submath> may be switched, so that H<submath>H_{i-1}</submath> is encrypted under the key m<submath>im_i</submath>., Thusthus making this method an extension of Davies–Meyer instead.

{{clear}}

A second preimage attack (given a message m1<math>m_1</math> an attacker finds another message m2<math>m_2</math> to satisfy <math>\operatorname{hash}(m1m_1) = \operatorname{hash}(m2m_2) </math>) can be done according to Kelsey and Schneier<ref name="ks05"/> for a 2<supmath>2^k</supmath>-message-block message in time <math>k &\times; 2^{^{n/2+1}} + 2<sup>^{n-k+1}</supmath>. Note that theThe complexity is above 2<supmath>2^{n/2}</supmath> but below 2<supmath>2^n</supmath> when messages are long, and that when messages get shorter the complexity of the attack approaches 2<supmath>2^n</supmath>.

== Hirose ==

[[Image:Hirose.png|thumb|230px|right|The Hirose double-block-length compression function]]

The Hirose<ref name="Hirose06"/> double-block-length one-way compression function consists of a block cipher plus a permutation <math>p</math>.&nbsp; It was proposed by Shoichi Hirose in 2006 and is based on a work<ref>M. Nandi, ''Towards optimal double-length hash functions'', In: Proceedings of the 6th International Conference on Cryptology in India (INDOCRYPT 2005), Lecture Notes in Computer Science 3797, pages 77–89, 2005.</ref> by [[Mridul Nandi]].

It uses a block cipher whose key length ''<math>k''</math> is larger than the block length ''<math>n''</math>, and produces a hash of size 2''n''<math>2n</math>. For example, any of the [[Advanced Encryption Standard process|AES candidates]] with a 192- or 256-bit key (and 128-bit block).

Each round accepts a portion of the message ''m''<submath>''i''m_i</submath> that is ''<math>k''−''-n''</math> bits long, and uses it to update two ''<math>n''</math>-bit state values ''<math>G''</math> and ''<math>H''</math>.

First, ''m''<submath>''i''m_i</submath> is concatenated with ''H''<submath>''H_{i''−1-1}</submath> to produce a key ''K''<submath>''i''K_i</submath>. Then the two feedback values are updated according to:

* <math>G_i = E_{K_i}(G_{i-1}) \oplus G_{i-1}</math>

* ''G''_''i'' = E_{''K''_''i''}(G_''i''−1) ⊕ G_''i''−1

* <math>H_i = E_{K_i}(p(G_{i-1})) \oplus p(G_{i-1})</math>

* ''H''_''i'' = E_{''K''_''i''}(''p''(G_''i''−1)) ⊕ ''p''(G_''i''−1).

''p''(G<submath>''p(G_{i''−1-1})</submath>) is an arbitrary fixed-point-free permutation on an ''<math>n''</math>-bit value, typically defined as <math>p(x) = x \oplus c</math> for an arbitrary non-zero constant <math>c</math> (all ones may be a convenient choice).

* ''p''(''x'') = ''x'' ⊕ ''c''

for an arbitrary non-zero constant ''c''. (All-ones may be a convenient choice.)

Each encryption resembles the standard Davies–Meyer construction. The advantage of this scheme over other proposed double-block-length schemes is that both encryptions use the same key, and thus key scheduling effort may be shared.

The final output is ''H''<sub>''t''</submath>H_t ||''G''_{''t'' G_t</submath>. The scheme has the rate ''R''<submath display="inline">R_{Hirose}} = (''\frac{k''−''-n'')}{2n}</2·''n''math> relative to encrypting the message with the cipher.

Hirose also provides a proof in the Ideal Cipher Model.

Line 163 ⟶ 164:

== See also ==

* [[Whirlpool (cryptography)|Whirlpool]] –{{emdash}} A cryptographic hash function built using the Miyaguchi–Preneel construction and a block cipher similar to [[Square (cipher)|Square]] and [[Advanced Encryption Standard|AES]].

* [[CBC-MAC]], [[One-key MAC|OMAC]], and [[PMAC (cryptography)|PMAC]] –{{emdash}} Methods to turn block ciphers into [[message authentication code]]s (MACs).

== References ==

=== Citations ===

{{Reflist}}

* {{cite book |url=http://cacr.uwaterloo.ca/hac/ |title=Handbook of Applied Cryptography |last=Menezes |last2=van Oorschot |last3=Vanstone |year=2001 |chapter=Hash Functions and Data Integrity |chapterurl=http://cacr.uwaterloo.ca/hac/about/chap9.pdf }}

=== Sources ===

{{refbegin}}

* {{cite book |url=http://cacr.uwaterloo.ca/hac/ |title=Handbook of Applied Cryptography |last=Menezes |last2=van Oorschot |last3=Vanstone |year=2001 |chapter=Hash Functions and Data Integrity |chapterurlchapter-url=http://cacr.uwaterloo.ca/hac/about/chap9.pdf }}

{{refend}}

{{Cryptography navbox|hash}}