One-way compression function: Difference between revisions

Revision as of 23:07, 10 August 2016

Revision as of 18:47, 23 August 2016

Line 1:

In [[cryptography]], a '''one-way compression function''' is a function that transforms two fixed-length inputs into a fixed-length output.<ref>Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing (August 2001) page 328.</ref> The transformation is [[one-way function|"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 [[data compression]], which by definition can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data.

[[Image:One-way compression.svg|thumb|200px|right|A one-way compression function]]

One-way compression functions are for instance used in the [[Merkle–Damgård construction]] inside [[cryptographic hash function]]s.

One-way compression functions are often built from [[block cipher]]s.

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

Line 73:

* 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-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, ''[httphttps://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-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 161:

== See also ==

* [[WHIRLPOOL]] -– A cryptographic hash function built using the Miyaguchi–Preneel construction and a block cipher similar to [[Square (cipher)|Square]] and [[Advanced Encryption Standard|AES]].

* [[CBC-MAC]], [[One-key MAC|OMAC]] and [[PMAC (cryptography)|PMAC]] -– Methods to turn block ciphers into [[message authentication code]]s (MACs).

== References ==

{{Reflist}}

* ''[{{cite book |url=http://www.cacr.math.uwaterloo.ca/hac/ |title=Handbook of Applied Cryptography]'' by |last=Menezes, |last2=van Oorschot and |last3=Vanstone (|year=2001), |chapter=Hash 9Functions and Data Integrity |chapterurl=http://cacr.uwaterloo.ca/hac/about/chap9.pdf }}

<references/>

* ''[{{cite web |url=http://www.crypto.rub.de/its_seminar_ws0809.html |title=Building Hash Functions from Block Ciphers, Their Security and Implementation Properties]'' by |first=Timo |last=Bartkewitz (|year=2009). |deadurl=yes }}{{dead link|date=August 2016}}

{{Cryptography navbox|hash}}