One-way compression function
Another method is 2BOW (or NBOW in general), which is a "high-rate multi-block-length hash function based on block ciphers"[1] and typically achieves (asymptotic) rates between 1 and 2 independent of the hash size (only with small constant overhead).
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 (
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.
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.
Single-block-length compression functions output the same number of bits as processed by the underlying block cipher.
These methods are then used inside the Merkle–Damgård construction to build the actual hash function.
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.
[6] In practice reasonable speeds are achieved provided the key scheduling of the selected block cipher is not a too heavy operation.
It can also save code space in very tiny embedded systems like for instance smart cards or nodes in cars or other machines.
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
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 oracles then respond with a randomly chosen plaintext or ciphertext, if the pair was asked for the first time.
For the proof there is a collision finding algorithm that makes randomly chosen queries to the oracles.
The probability that the algorithm returns 1 is dependent on the number of queries which determine the security level.
The output ciphertext is then also XORed (⊕) with the previous hash value (
Variations of this method replace XOR with any other group operation, such as addition on 32-bit unsigned integers.
So far, no practical attack has been based on this property, but one should be aware of this "feature".
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
The security of the Davies–Meyer construction in the Ideal Cipher Model was first proven by R.
[10] The Matyas–Meyer–Oseas single-block-length one-way compression function can be considered the dual (the opposite) of Davies–Meyer.
In mathematical notation Matyas–Meyer–Oseas can be described as: The scheme has the rate: A second preimage attack (given a message
It was independently proposed by Shoji Miyaguchi and Bart Preneel.
The Hirose[8] double-block-length one-way compression function consists of a block cipher plus a permutation
It was proposed by Shoichi Hirose in 2006 and is based on a work[11] by Mridul Nandi.
