One-way compression function

From Wikipedia, the free encyclopedia

In cryptography, a one-way compression function is a function that transforms two fixed length inputs to an output of the same size as one of the inputs. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output.

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

One-way compression functions are often built from block ciphers. Some methods to turn any normal block cipher into a one-way compression function are Davies-Meyer, Matyas-Meyer-Oseas, Miyaguchi-Preneel, MDC-2/Meyer-Schilling and MDC-4. These methods are described in detail further down. (MDC-2 is also the name of a hash function patented by IBM.)

Contents 1 Compression 2 One-way 3 The Merkle-Damgård construction 4 Often built from block ciphers 5 Davies-Meyer 6 Matyas-Meyer-Oseas 7 Miyaguchi-Preneel 8 See also 9 References

[edit] Compression

A compression function mixes two fixed length inputs and produces a single fixed length output of the same size as one of the inputs. This can also be seen as that the compression function transforms one large fixed-length input into a shorter, fixed-length output.

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 the same thing as if one single 256-bit input is compressed together to a single output of 128 bits.

Some compression functions have different size of the two inputs but the output usually is the same size as one of the inputs. For instance, input A might be 256 bits, input B 128 bits and they are compressed together 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.

[edit] One-way

Main article: one-way function

A one-way function is a function that is easy to compute but hard to invert. One-way compression functions are one-way in the following ways:

• If you know both inputs it is easy to calculate the output.

• If an attacker only knows the output it should be unfeasible to calculate any of the inputs.

• If an attacker knows the output and one of the inputs it should be unfeasible to figure out the other input.

The compression function should also be collision resistant. That is, it should be hard to find two different sets of inputs that compress to the same outputs.

[edit] The Merkle-Damgård construction

Main article: Merkle-Damgård construction

One-way compression functions are used in the Merkle-Damgård construction inside cryptographic hash functions.

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

[edit] Often built from block ciphers

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

Block ciphers take (like one-way compression functions) two fixed size inputs (the key and the plaintext) and return one single output (the ciphertext) which is the same size as the input plaintext.

However, modern block ciphers are only partially one-way. That is, given a plaintext and a ciphertext it is infeasible to find a key that encrypts the plaintext to the ciphertext. But, given a ciphertext and a key a matching plaintext can be found simply by using the block cipher's decryption function. Thus, to turn a block cipher into a one-way compression function some extra operations have to be added.

Some methods to turn any normal block cipher into a one-way compression function are Davies-Meyer, Matyas-Meyer-Oseas, Miyaguchi-Preneel, MDC-2 and MDC-4. They are then used inside the Merkle-Damgård construction to build the actual hash function. These methods are described in detail further down. (MDC-2 is also the name of a hash function patented by IBM.)

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 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^[1]. 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 block cipher and a hash function. It can also save code space in very tiny embedded systems like for instance smart cards or nodes in cars or other machines.

If a block cipher has a block size of say 128 bits most of the methods create a hash function that has the block size of 128 bits and produces a hash of 128 bits. But there are also methods to 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.

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.
• The resulting hash size is big enough. 64-bit is too small, 128-bit might be enough.
• The last block is properly length padded prior to the hashing. (See the Merkle-Damgård construction.) Length padding is normally implemented and handled internally in specialised hash functions like SHA-1 etc.

The constructions presented below: Davies-Meyer, Matyas-Meyer-Oseas and Miyaguchi-Preneel have been shown to be secure under the black-box analysis^[2]. The black-box model assumes that a random block cipher is used. In this model an attacker may freely encrypt and decrypt any blocks, but does not have access to an implementation of the block cipher.

[edit] Davies-Meyer

The Davies-Meyer one-way 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 XORed () 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:

If the block cipher uses for instance 256-bit keys then each message block (m_i) 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.

If the used block cipher is not secure i.e. has been broken then a so-called fixed point attack can be applied to this construction ^[3]. According to Bruce Schneier this "is not really worth worrying about"^[4].

The security of the Davies-Meyer construction under the black-box assumption was first proved by R. Winternitz^[5].

[edit] Matyas-Meyer-Oseas

The Matyas-Meyer-Oseas 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 () 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.

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

[edit] Miyaguchi-Preneel

The Miyaguchi-Preneel 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 () 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.

In mathematical notation Miyaguchi-Preneel can be described as:

The roles of m_i and H_i-1 may be switched, so that H_i-1 is encrypted under the key m_i. Thus making this method an extension of Davies-Meyer instead.

[edit] See also

• WHIRLPOOL - A cryptographic hash function built using the Miyaguchi-Preneel construction and a block cipher similar to Square and AES.
• CBC-MAC, OMAC and PMAC - Methods to turn block ciphers into message authentication codes (MACs).

[edit] References

• Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone (2001), chapter 9.

1. ^ 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".
2. ^ John Black, Phillip Rogaway, and Tom Shrimpton. Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. Advances in Cryptology - CRYPTO '02, Lecture Notes in Computer Science, vol. 2442, pp. 320-335, Springer, 2002. See the table on page 3, Davies-Meyer, Matyas-Meyer-Oseas and Miyaguchi-Preneel are numbered in the first column as hash functions 5, 1 and 3.
3. ^ Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 375.
4. ^ Bruce Schneier Applied Cryptography, second edition, page 448
5. ^ 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.

v • d • e   Cryptographic hash functions and Message authentication codes (MACs) Hash algorithms: Gost-Hash | HAS-160 | HAVAL | MDC-2 | MD2 | MD4 | MD5 | N-Hash | RadioGatún | RIPEMD | SHA family | Snefru | Tiger | WHIRLPOOL | crypt(3) DES MAC algorithms: DAA | CBC-MAC | HMAC | OMAC/CMAC | PMAC | UMAC | Poly1305-AES Authenticated encryption modes: CCM | CWC | EAX | GCM | OCB Attacks: Hash collision | Birthday attack | Preimage attack | Rainbow table | Brute force attack Misc: Avalanche effect | Hash collision | Merkle-Damgård construction   Standardization: CRYPTREC | NESSIE v • d • e   Cryptography History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers | Steganography