One-way compression function

This page is currently in the process of having information merged to it from the following articles: Davies-Meyer hash, Matyas-Meyer-Oseas hash and Miyaguchi-Preneel hash.

In cryptography, there are several methods to use a block cipher to build a cryptographic hash function. The methods resembles the block cipher modes of operation usually used for encryption. Three such methods to turn any normal block cipher into a hash are Davies-Meyer, Matyas-Meyer-Oseas and Miyaguchi-Preneel. They are described in detail further down.

Using a block cipher as a hash function usually is much slower then using a specially designed hash function. But in some cases it might be easier since it means just implementing a block cipher and then using it both as a 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 is secure if the following conditions are met:

• The block cipher needs to be secure.
• The resulting hash size needs to be big enough. 64-bit is too small, 128-bit might be enough.
• The last block needs to be properly length padded prior to the hashing. (This is normally implemented and handled internally in specialised hash functions like SHA-1 etc.)

Davies-Meyer

File:Davies-Meyer hash.png

The Davies-Meyer hash construction

The Davies-Meyer hash construction feeds each block of the message (m_i) as the key to the block cipher. It feeds the previous hash value (H_i-1) as the cleartext to be encrypted. The output ciphertext is then also XORed (${\displaystyle \oplus }$ ) 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₀).

${\displaystyle H_{i}=E_{m_{i}}(H_{i-1})\oplus H_{i-1}}$ 

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.

Matyas-Meyer-Oseas

File:Matyas-Meyer-Oseas hash.png

The Matyas-Meyer-Oseas hash construction

The Matyas-Meyer-Oseas hash construction can be considered the dual (the opposite) of Davies-Meyer.

It feeds each block of the message (m_i) as the cleartext to be encrypted. The output ciphertext is then also XORed (${\displaystyle \oplus }$ ) 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 have different block and key size 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.

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}}$ 

Miyaguchi-Preneel

File:Miyaguchi-Preneel hash.png

The Miyaguchi-Preneel hash construction

The Miyaguchi-Preneel hash construction is an extended variant of Matyas-Meyer-Oseas.

It feeds each block of the message (m_i) as the cleartext to be encrypted. The output ciphertext is then XORed (${\displaystyle \oplus }$ ) 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 have different block and key size 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.

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}}$ 

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.