One-way Compression Function - Construction From Block Ciphers

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

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, if n denotes the output bit-length of the block cipher the rate represents the ratio between the number of processed bits of input m, n output bits and the necessary block cipher operations s to produce these n output bits. Generally, the usage of less block cipher operations could result 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 in the formula .

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 (fixed points or key-collisions).
• The resulting hash size is big enough. According to the birthday attack a security level of 280 (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.