One-way compression function: Difference between revisions

Revision as of 04:21, 29 October 2017

Revision as of 08:46, 23 November 2017

Line 42:

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 x&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}}

Line 78:

[[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_i) as the key to a block cipher. It feeds the previous hash value (H_i-1) as the plaintext to be encrypted. The output ciphertext is then also [[exclusive-or|XORed]] (<math>\oplus</math>⊕) with the previous hash value (H_i-1) to produce the next hash value (H_i). In the first round when there is no previous hash value it uses a constant pre-specified initial value (H₀).

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

Line 92:

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>{{mvar|m</math>}}, one can find a value of <math>{{mvar|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^k-message-block message in time 3 x&times; 2^n/2+1+2^n-k+1 . 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&times; 2^n/2+1+2^n-k+1 time. Note that in both cases 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ⁿ.

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>

Line 102:

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_i) as the plaintext to be encrypted. The output ciphertext is then also XORed (<math>\oplus</math>⊕) with the same message block (m_i) to produce the next hash value (H_i). The previous hash value (H_i-1) 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₀).

If the block cipher has different block and key sizes the hash value (H_i-1) 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 g( ) to be converted/padded to fit as key for the cipher.

Line 114:

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

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"/> for a 2^k-message-block message in time k x&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ⁿ.

== Miyaguchi–Preneel ==

Line 121:

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_i) as the plaintext to be encrypted. The output ciphertext is then XORed (<math>\oplus</math>⊕) with the same message block (m_i) and then also XORed with the previous hash value (H_i-1) to produce the next hash value (H_i). The previous hash value (H_i-1) 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₀).

If the block cipher has different block and key sizes the hash value (H_i-1) 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 g( ) to be converted/padded to fit as key for the cipher.

Line 136:

{{clear}}

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"/> for a 2^k-message-block message in time k x&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ⁿ.

== Hirose ==