One-way compression function

One-way

A one-way function is a function that is easy to compute but hard to invert. A one-way compression function (also called hash function) should have the following properties:

• 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 infeasible to calculate an input. In other words, given an output ${\displaystyle h}$, it should be unfeasible to calculate an input ${\displaystyle m}$ such that ${\displaystyle \mathrm{hash}(m)=h}$.
• Second preimage-resistance: Given an input ${\displaystyle m_1}$ whose output is ${\displaystyle h}$, it should be infeasible to find another input ${\displaystyle m_2}$ that has the same output ${\displaystyle h}$, i.e. ${\displaystyle \mathrm{hash}(m_1)=\mathrm{hash}(m_2)}$.
• 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 ${\displaystyle m_1\ne m_2}$ such that ${\displaystyle \mathrm{hash}(m_1)=\mathrm{hash}(m_2)}$. Due to the birthday paradox (see also birthday attack) there is a 50% chance a collision can be found in time of about ${\displaystyle 2^{n/2}}$ where ${\displaystyle n}$ 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 ${\displaystyle 2^{n/2}}$ work.

Ideally one would like the "infeasibility" in preimage-resistance and second preimage-resistance to mean a work of about ${\displaystyle 2^n}$ where ${\displaystyle n}$ is the number of bits in the hash function's output. However, particularly for second preimage-resistance this is a difficult problem.

The Merkle–Damgård construction

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) 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 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 (${\displaystyle 2^{n/2}}$, ${\displaystyle n}$ being the block size in bits) if the used function ${\displaystyle f}$ is collision-resistant. 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 ${\displaystyle m_1}$ an attacker finds another message ${\displaystyle m_2}$ to satisfy ${\displaystyle \mathrm{hash}(m_1)=\mathrm{hash}(m_2)}$ can be done according to Kelsey and Schneier for a ${\displaystyle 2^k}$-message-block message in time ${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$. The complexity of this attack reaches a minimum of ${\displaystyle 2^{3n/4+2}}$ for long messages when ${\displaystyle k=2^{n/4}}$ and approaches ${\displaystyle 2^n}$ when messages are short.

Construction 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 (single-block-length compression functions) and MDC-2, MDC-4, Hirose (double-block-length compressions functions).

Single-block-length compression functions output the same number of bits as processed by the underlying block cipher. Consequently, double-block-length compression functions output twice the number of bits.

If a block cipher has a 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å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 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. 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 code space in very tiny embedded systems like for instance smart cards or 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, the rate represents the ratio between the number of processed bits of input ${\displaystyle m}$, the output bit-length ${\displaystyle n}$ of the block cipher, and the necessary block cipher operations ${\displaystyle s}$ to produce these ${\displaystyle n}$ output bits. Generally, the usage of fewer block cipher operations results 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:

${\displaystyle R_h=\frac{\left|m_i\right|}{s\cdot n}}$

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

The constructions presented below: Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel and Hirose have been shown to be secure under the black-box analysis. The goal is to show that any attack that can be found is at most as efficient as the birthday attack under certain assumptions. The black-box model assumes that a block cipher is used that is randomly chosen from a set containing all appropriate block ciphers. In this model an attacker may freely encrypt and decrypt any blocks, but does not have access to an implementation of the block cipher. The encryption and decryption function are represented by oracles that receive a pair of either a plaintext and a key or a ciphertext and a key. The oracles then respond with a randomly chosen plaintext or ciphertext, if the pair was asked for the first time. They both share a table for these triplets, a pair from the query and corresponding response, and return the record, if a query was received for the second time. For the proof there is a collision finding algorithm that makes randomly chosen queries to the oracles. The algorithm returns 1, if two responses result in a collision involving the hash function that is built from a compression function applying this block cipher (0 else). The probability that the algorithm returns 1 is dependent on the number of queries which determine the security level.

Davies–Meyer

The Davies–Meyer single-block-length compression function feeds each block of the message (${\displaystyle m_i}$) as the key to a block cipher. It feeds the previous hash value (${\displaystyle H_{i-1}}$) as the plaintext to be encrypted. The output ciphertext is then also XORed (⊕) with the previous hash value (${\displaystyle H_{i-1}}$) to produce the next hash value (${\displaystyle H_i}$). In the first round when there is no previous hash value it uses a constant pre-specified initial value (${\displaystyle H_0}$).

In mathematical notation Davies–Meyer can be described as:

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

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

${\displaystyle R_{DM}=\frac{k}{1\cdot n}=\frac{k}{n}}$

If the block cipher uses for instance 256-bit keys then each message block (${\displaystyle 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.

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 points for the construction: for any ${\displaystyle m}$, one can find a value of ${\displaystyle h}$ such that ${\displaystyle E_m(h)\oplus h=h}$: one just has to set ${\displaystyle h=E_m^{-1}(0)}$. This is a property that random functions 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 ${\displaystyle m_1}$, attacker finds another message ${\displaystyle m_2}$ to satisfy ${\displaystyle \mathrm{hash}(m_1)=\mathrm{hash}(m_2)}$) of Kelsey and Schneier for a ${\displaystyle 2^k}$-message-block message in time ${\displaystyle 3\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 ${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$ time. In both cases the complexity is above ${\displaystyle 2^{n/2}}$ but below ${\displaystyle 2^n}$ when messages are long and that when messages get shorter the complexity of the attack approaches ${\displaystyle 2^n}$.

The security of the Davies–Meyer construction in the Ideal Cipher Model was first proven by R. Winternitz.

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 (${\displaystyle m_i}$) as the plaintext to be encrypted. The output ciphertext is then also XORed (⊕) with the same message block (${\displaystyle m_i}$) to produce the next hash value (${\displaystyle H_i}$). The previous hash value (${\displaystyle 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 (${\displaystyle H_0}$).

If the block cipher has different block and key sizes the hash value (${\displaystyle 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 ${\displaystyle g}$ to be converted/padded to fit as key for the cipher.

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

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

The scheme has the rate:

${\displaystyle R_{MMO}=\frac{n}{1\cdot n}=1}$

A second preimage attack (given a message ${\displaystyle m_1}$ an attacker finds another message ${\displaystyle m_2}$ to satisfy ${\displaystyle \mathrm{hash}(m_1)=\mathrm{hash}(m_2)}$) can be done according to Kelsey and Schneier for a ${\displaystyle 2^k}$-message-block message in time ${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$. The complexity is above ${\displaystyle 2^{n/2}}$ but below ${\displaystyle 2^n}$ when messages are long, and that when messages get shorter the complexity of the attack approaches ${\displaystyle 2^n}$.

Miyaguchi–Preneel

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 (${\displaystyle m_i}$) as the plaintext to be encrypted. The output ciphertext is then XORed (⊕) with the same message block (${\displaystyle m_i}$) and then also XORed with the previous hash value (${\displaystyle H_{i-1}}$) to produce the next hash value (${\displaystyle H_i}$). The previous hash value (${\displaystyle 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 (${\displaystyle H_0}$).

If the block cipher has different block and key sizes the hash value (${\displaystyle 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 ${\displaystyle g}$ to be converted/padded to fit as key for the cipher.

In mathematical notation Miyaguchi–Preneel can be described as:

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

The scheme has the rate:

${\displaystyle R_{MP}=\frac{n}{1\cdot n}=1}$

The roles of ${\displaystyle m_i}$ and ${\displaystyle H_{i-1}}$ may be switched, so that ${\displaystyle H_{i-1}}$ is encrypted under the key ${\displaystyle m_i}$, thus making this method an extension of Davies–Meyer instead.

A second preimage attack (given a message ${\displaystyle m_1}$ an attacker finds another message ${\displaystyle m_2}$ to satisfy ${\displaystyle \mathrm{hash}(m_1)=\mathrm{hash}(m_2)}$) can be done according to Kelsey and Schneier for a ${\displaystyle 2^k}$-message-block message in time ${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$. The complexity is above ${\displaystyle 2^{n/2}}$ but below ${\displaystyle 2^n}$ when messages are long, and that when messages get shorter the complexity of the attack approaches ${\displaystyle 2^n}$.

Hirose

The Hirose double-block-length one-way compression function consists of a block cipher plus a permutation ${\displaystyle p}$. It was proposed by Shoichi Hirose in 2006 and is based on a work by Mridul Nandi.

It uses a block cipher whose key length ${\displaystyle k}$ is larger than the block length ${\displaystyle n}$, and produces a hash of size ${\displaystyle 2n}$. For example, any of the AES candidates with a 192- or 256-bit key (and 128-bit block).

Each round accepts a portion of the message ${\displaystyle m_i}$ that is ${\displaystyle k-n}$ bits long, and uses it to update two ${\displaystyle n}$-bit state values ${\displaystyle G}$ and ${\displaystyle H}$.

First, ${\displaystyle m_i}$ is concatenated with ${\displaystyle H_{i-1}}$ to produce a key ${\displaystyle K_i}$. Then the two feedback values are updated according to:

• ${\displaystyle G_i=E_{K_i}(G_{i-1})\oplus G_{i-1}}$
• ${\displaystyle H_i=E_{K_i}(p(G_{i-1}))\oplus p(G_{i-1})}$

${\displaystyle p(G_{i-1})}$ is an arbitrary fixed-point-free permutation on an ${\displaystyle n}$-bit value, typically defined as ${\displaystyle p(x)=x\oplus c}$ for an arbitrary non-zero constant ${\displaystyle 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 ${\displaystyle H_t||G_t}$. The scheme has the rate $R_{Hirose}=\frac{k-n}{2n}$ relative to encrypting the message with the cipher.

Hirose also provides a proof in the Ideal Cipher Model.

Sponge construction

The sponge construction can be used to build one-way compression functions.