One-way Compression Function - Matyas–Meyer–Oseas

Matyas–Meyer–Oseas

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

The scheme has the rate:

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 for a 2k-message-block message in time k x 2n/2+1+2n-k+1. Note that the complexity is above 2n/2 but below 2n when messages are long and that when messages get shorter the complexity of the attack approaches 2n.