One-way compression function: Difference between revisions

Revision as of 10:35, 16 February 2017

Revision as of 23:30, 1 March 2017

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 conventional [[data compression]] algorithms, which by definitioninstead 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]]

Line 12:

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 theequivalent sameto thinghaving as if onea single 256-bit input is compressed together to a single output of 128 bits.

Some compression functions havedo differentnot sizecompress ofby the two inputshalf, but theinstead outputby usuallysome isother the same size as one of the inputsfactor. For instanceexample, ''input A'' might be 256 bits, and '''input B''' 128 bits, and theywhich are compressed together 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.

Line 23:

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 knowhave ansome input(s), it is easy to calculate the output.

* Preimage-resistance: If an attacker only knows the output it should be unfeasible to calculate an input i.e. In other words, given an output ''h'', it should be unfeasible to calculate an input ''m'' such that ''hash''(''m'')=''h''.

* Second preimage-resistance: Given an input ''m1'' whose output is ''h'', it should be unfeasible to find another input ''m2'' that has the same output ''h'' i.e. ''hash''(''m1'')=''hash''(''m2'').

* [[Collision resistance|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 m1 ≠ m2 such that ''hash''(''m1'') = ''hash''(''m2''). Due to the [[Birthday problem|birthday paradox]] (see also [[birthday attack]]) there is a 50% chance a collision can be found in time of about 2^n/2 where 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 work.

Ideally one would like the "unfeasibility" in preimage-resistance and second preimage-resistance to mean a work of about 2ⁿ where n is the number of bits in the hash function's output. RecentHowever, resultsparticularly indicate that in the case offor second preimage-resistance this is morea difficult than has been expected problem.{{Citation needed|date=October 2013}}.

== The Merkle–Damgård construction ==