Content deleted Content added
m Reverted edits by 2409:4041:6EC1:295F:CCD8:A411:620F:B4BB (talk) to last version by 天水圍劉馬車 |
→The Merkle–Damgård construction: Deduplicated introducing the construction by name halfway through the section, and the MD-5, SHA-1,2 context. Moved the sentence on length padding into the second paragraph, which describes the method of the construction. Readability improvement on length padding being crucial. Tags: Mobile edit Mobile web edit |
||
Line 35:
A common use of one-way compression functions is in the Merkle–Damgård construction inside cryptographic hash functions. Most widely used hash functions, including [[MD5]], [[SHA-1]] (which is deprecated<ref>{{Cite web|url=https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html| title=Announcing the first SHA1 collision|website=Google Online Security Blog| language=en|access-date=2020-01-12}}</ref>) and [[SHA-2]] use this construction.
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 one-way compression function. The compression function can either be specially designed for hashing or be built from a block cipher. The last block processed should also be [[Padding (cryptography)|length padded]], which is crucial to the security of this construction.
When length padding (also called MD-strengthening) is applied, attacks cannot find collisions faster than the birthday paradox (<math>2^{n/2}</math>, <math>n</math> being the block size in bits) if the used function <math>f</math> is collision-resistant.<ref name="damgard89">Ivan Damgård. [https://link.springer.com/content/pdf/10.1007%2F0-387-34805-0_39.pdf 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. [https://link.springer.com/content/pdf/10.1007%2F0-387-34805-0_40.pdf 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.
| |||