Cryptology ePrint Archive: Report 2006/061

Praveen Gauravaram and William Millan and Ed Dawson and Kapali Viswanathan

Abstract: The classic Merkle-Damgå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.

Category / Keywords: Merkle-Damg{\aa}rd construction, multi-block collision attacks (MBCA), hash function, 3C, 3C+.

Publication Info: currently unpublished

Date: received 15 Feb 2006, last revised 15 Mar 2006, withdrawn 19 Apr 2006

Contact author: p gauravaram at isi qut edu au

Available format(s): (-- withdrawn --)

Note: Paper is withdrawn because it is accepted at ACISP 2006 conference.

Version: 20060419:075717 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]