One-way compression function: Difference between revisions

Revision as of 11:55, 2 February 2006

Revision as of 14:57, 5 February 2006

Line 9:

* The resulting hash size needs to be big enough. 64-bit is too small, 128-bit might be enough.

* The last block needs to be properly [[Padding (cryptography)|length padded]] prior to the hashing. (This is normally implemented and handled internally in specialised hash functions like [[SHA-1]] etc.)

== The Merkle-Damgård structure ==

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 ''compression function''. The last block processed should also be [[Padding (cryptography)|length padded]], this is crucial to the security of this construction. This construction is called the ''[[Ralph Merkle|Merkle]]-[[Ivan Damgård|Damgård]] structure''. Most widely used hash functions, including [[SHA-1]] and [[MD5]], take this form.

<div align=center>[[Image:Merkle-Damgard hash.svg|Merkle-Damgård]]</div>

In the diagram, the compression function is denoted by ''f'', and transforms a fixed length input to an output of the same size. The algorithm starts with an initial value, the [[initialization vector]] (IV). The IV is a fixed value (algorithm or implementation specific). For each message block, the compression (or compacting) function ''f'' takes the result so far, combines it with the message block, and produces an intermediate result. Bits representing the length of the entire message are appended to the message and padded suitably as part of the last block. The value after the last block is taken to be the hash value for the entire message.

The popularity of this construction is due to the fact, proven by Merkle and Damgård, that if the compression function ''f'' is collision-resistant, then so is the hash function constructed using it. Unfortunately, this construction also has several undesirable properties:

* Length extension - once an attacker has one collision, he can find more very cheaply.

* Second-preimage attacks against long messages are always much more efficient than brute force.

* Multicollisions (many messages with the same hash) can be found with only a little more work than collisions.

* "Herding attacks" (first committing to an output h, then mapping messages with arbitrary starting values to h) are possible for more work than finding a collision, but much less than would be expected to do this for a [[random oracle]].

== Davies-Meyer ==

[[Image:Davies-Meyer hash.svg|thumb|230px|right|The Davies-Meyer hash construction]]

The Davies-Meyer hash constructioncompression function feeds each block of the message (m_i) as the key to the block cipher. It feeds the previous hash value (H_i-1) as the cleartext to be encrypted. The output ciphertext is then also [[exclusive-or|XORed]] (<math>\oplus</math>) with the previous hash value (H_i-1) to produce the next hash value (H_i). In the first round when there is no previous hash value it uses a constant pre-specified initial value (H₀).

<math>H_i = E_{m_i}(H_{i-1})\oplus H_{i-1}</math>

Line 25 ⟶ 37:

== Matyas-Meyer-Oseas ==

[[Image:Matyas-Meyer-Oseas hash.svg|thumb|230px|right|The Matyas-Meyer-Oseas hash construction]]

The Matyas-Meyer-Oseas hash constructioncompression function can be considered the dual (the opposite) of Davies-Meyer.

It feeds each block of the message (m_i) as the cleartext to be encrypted. The output ciphertext is then also XORed (<math>\oplus</math>) with the same message block (m_i) to produce the next hash value (H_i). The previous hash value (H_i-1) is fed as the key to the block cipher. In the first round when there is no previous hash value it uses a constant pre-specified initial value (H₀).

Line 36 ⟶ 48:

== Miyaguchi-Preneel ==

[[Image:Miyaguchi-Preneel hash.svg|thumb|230px|right|The Miyaguchi-Preneel hash construction]]

The Miyaguchi-Preneel hash constructioncompression function is an extended variant of Matyas-Meyer-Oseas. It was independently proposed by [[Shoji Miyaguchi]] and [[Bart Preneel]].

It feeds each block of the message (m_i) as the cleartext to be encrypted. The output ciphertext is then XORed (<math>\oplus</math>) with the same message block (m_i) and then also XORed with the previous hash value (H_i-1) to produce the next hash value (H_i). The previous hash value (H_i-1) is fed as the key to the block cipher. In the first round when there is no previous hash value it uses a constant pre-specified initial value (H₀).