One-way compression function

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. 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 not related to conventional data compression algorithms, which instead can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data.

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 (single-block-length compression functions) and MDC-2/Meyer–Schilling, MDC-4, Hirose (double-block-length compression functions). These methods are described in detail further down. (MDC-2 is also the name of a hash function patented by IBM.) Another method is 2BOW (or NBOW in general), which is a "high-rate multi-block-length hash function based on block ciphers" and typically achieves (asymptotic) rates between 1 and 2 independent of the hash size (only with small constant overhead). This method has not yet seen any serious security analysis, so should be handled with care.

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 equivalent to having a single 256-bit input compressed to a single output of 128 bits. Some compression functions do not compress by half, but instead by some other factor. For example, input A might be 256 bits, and input B 128 bits, which are compressed 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.

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 h {\displaystyle h} , it should be unfeasible to calculate an input m {\displaystyle m} such that hash ⁡ ( m ) = h {\displaystyle \operatorname {hash} (m)=h} . Second preimage-resistance: Given an input m 1 {\displaystyle m_{1}} whose output is h {\displaystyle h} , it should be infeasible to find another input m 2 {\displaystyle m_{2}} that has the same output h {\displaystyle h} , i.e. hash ⁡ ( m 1 ) = hash ⁡ ( m 2 ) {\displaystyle \operatorname {hash} (m_{1})=\operatorname {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 m 1 ≠ m 2 {\displaystyle m_{1}\neq m_{2}} such that hash ⁡ ( m 1 ) = hash ⁡ ( m 2 ) {\displaystyle \operatorname {hash} (m_{1})=\operatorname {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 2 n / 2 {\displaystyle 2^{n/2}} where n {\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 2 n / 2 {\displaystyle 2^{n/2}} work. Ideally one would like the "infeasibility" in preimage-resistance and second preimage-resistance to mean a work of about 2 n {\displaystyle 2^{n}} where n {\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

… excerpt ends here. Continue reading the full article.