Content deleted Content added
→Wide pipe construction: Removed some redundant vertical whitespace. |
→The Merkle–Damgård construction: Moved <br clear=both/> down to bottom. |
||
Line 39:
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 [[Merkle–Damgård construction]]. Most widely used hash functions, including [[SHA-1]] and [[MD5]], take this form.
<br style="clear:both"/>▼
When length padding (also called MD-strengthening) is applied attacks cannot find collisions faster than the birthday paradox (2<sup>n/2</sup>, n is the block size in bits) if the used f-function is collision-resistant<ref name="damgard89">Ivan Damgård. A design principle for hash functions. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 416–427. Springer, 1989.</ref><ref name="merkle89">Ralph Merkle. One way hash functions and DES. In Gilles Brassard, editor, CRYPTO, volume 435 of LNCS, pages 428–446. Springer, 1989.</ref>. Hence, the Merkle–Damgård hash construction reduces the problem of finding a proper hash function to finding a proper compression function.
A second preimage attack (given a message m1 an attacker finds another message m2 to satisfy hash(m1) = hash(m2) ) can be done according to Kelsey and Schneier <ref name="ks05">John Kelsey and Bruce Schneier. Second preimages on n-bit hash functions for much less than 2<sup>n</sup> work. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 474–490. Springer, 2005.</ref> for a 2<sup>k</sup>-message-block message in time k x 2<sup>n/2+1</sup>+2<sup>n-k+1</sup>. Note that the complexity is above 2<sup>n/2</sup> but below 2<sup>n</sup> when messages are long and that when messages get shorter the complexity of the attack approaches 2<sup>n</sup>.
▲<br style="clear:both"/>
== Wide pipe construction ==
| |||