Paper 2006/061

--Withdrawn--

Praveen Gauravaram, William Millan, 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.

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

Metadata
Available format(s)
-- withdrawn --
Publication info
Published elsewhere. currently unpublished
Keywords
Merkle-Damgård constructionmulti-block collision attacks (MBCA)hash function3C3C+.
Contact author(s)
p gauravaram @ isi qut edu au
History
2006-04-19: withdrawn
2006-02-23: received
See all versions
Short URL
https://ia.cr/2006/061
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.