CryptoDB
Authors: | |
---|---|
Download: | |
Abstract: | The classic Merkle-Damg{\aa}rd (\textbf{MD}) structure provides a popular way of turning a fixed-length compression function into a variable-length input cryptographic hash function. However, the multi-block collision attacks (MBCA) on the \textbf{MD}-style hash functions MD5, SHA-0 and SHA-1 demonstrate the weakness of the \textbf{MD} construction in extending the collision resistance property of a single compression function to its iterations. In this paper, we investigate a recently proposed cryptographic construction (called \textbf{3C}) devised by enhancing the \textbf{MD} construction, and prove it provides quantitatively more resistance against MBCA than does the \textbf{MD}-style. Specifically, we prove that it requires at least $2^{t/2}$ computational effort to perform any MBCA on the $t$-bit \textbf{3C} hash function when the same attack on a $t$-bit \textbf{MD} hash function (using the same compression function) requires an effort not less than $2^{t/4}$. This is the first result showing a generic construction with resistance to MBCA. We further improve the resistance of the \textbf{3C} design against MBCA and propose the new \textbf{3C+} hash function construction. We prove that \textbf{3C+} is completely \emph{immune} to MBCA since it costs at least $2^{t/2}$ effort to perform any MBCA on the \textbf{3C+} construction. This reduces the collision security of \textbf{3C+} to the collision security of the underlying compression function, hence restoring the paradigm that one only needs to design a secure compression function to obtain a secure iterated hash function. Both the \textbf{3C} and \textbf{3C+} constructions are very simple adjustments to the \textbf{MD} construction and they are immune to the straight forward extension attacks which apply to the \textbf{MD} hash functions. The second preimage attacks on $t$-bit hash functions also do not work on the constructions presented in this paper. |
BibTeX
@misc{eprint-2006-21554, title={}, booktitle={IACR Eprint archive}, keywords={Merkle-Damg{\aa}rd construction, multi-block collision attacks (MBCA), hash function, 3C, 3C+.}, url={http://eprint.iacr.org/2006/061}, note={currently unpublished p.gauravaram@isi.qut.edu.au 13257 received 15 Feb 2006, last revised 15 Mar 2006, withdrawn 19 Apr 2006}, author={Praveen Gauravaram and William Millan and Ed Dawson and Kapali Viswanathan}, year=2006 }