One-way compression function: Difference between revisions

Revision as of 04:48, 4 January 2018

Revision as of 04:49, 4 January 2018

Line 9:

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

Line 62 ⟶ 61:

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 schedule|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.<ref>John Black, Martin Cochran, and Thomas Shrimpton. ''On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions.'' Advances in Cryptology --– EUROCRYPT '05, Aarhus, Denmark, 2005. The authors define a hash function "highly efficient if its compression function uses exactly one call to a block cipher whose key is fixed".</ref> 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 [[machine code|code]] space in very tiny [[embedded system]]s like for instance [[smart card]]s or [[Electronic control unit|nodes in cars]] or other machines.

Line 73 ⟶ 72:

* 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.<ref>John Black, Phillip Rogaway, and Tom Shrimpton. ''Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV.'' Advances in Cryptology -– CRYPTO '02, Lecture Notes in Computer Science, vol. 2442, pp. 320-335320–335, Springer, 2002. See the table on page 3, Davies–Meyer, Matyas–Meyer–Oseas and Miyaguchi–Preneel are numbered in the first column as hash functions 5, 1 and 3.</ref><ref name = "Hirose06">S. Hirose, ''[https://www.iacr.org/archive/fse2006/40470213/40470213.pdf Some Plausible Constructions of Double-Block-Length Hash Functions]''. In: Robshaw, M.J.B. (ed.) FSE 2006, LNCS, vol. 4047, pp. 210-225210–225, Springer, Heidelberg 2006.</ref> 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 ==

Line 160 ⟶ 159:

Hirose also provides a proof in the Ideal Cipher Model.

== Sponge construction==

The [[sponge construction]] is a one-way compression function with one of its inputs usually being a zero vector.