Lecture Notes in Computer Science, 2004, Volume 3152/2004, 99-213, DOI: 10.1007/978-3-540-28628-8_19

Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions

Antoine Joux

View Related Documents

Abstract

In this paper, we study the existence of multicollisions in iterated hash functions. We show that finding multicollisions, i.e. r-tuples of messages that all hash to the same value, is not much harder than finding ordinary collisions, i.e. pairs of messages, even for extremely large values of r. More precisely, the ratio of the complexities of the attacks is approximately equal to the logarithm of r. Then, using large multicollisions as a tool, we solve a long standing open problem and prove that concatenating the results of several iterated hash functions in order to build a larger one does not yield a secure construction. We also discuss the potential impact of our attack on several published schemes. Quite surprisingly, for subtle reasons, the schemes we study happen to be immune to our attack.

Fulltext Preview

Image of the first page of the fulltext document