Reading the Crypto Classics

Joux: "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions“ (Crypto 2004)

2023/02/28 10:00-12:00

Moderator: Vukašin Karadžić (TU Darmstadt, Cryptography and Network Security Group) | Location: online

Organizer: , TU Darmstadt, Cryptography and Information Security Group


This talk is the fifth session in the seminar series “Reading the Crypto Classics” for the winter term 2022/23. The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper/talk

Joux: “Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions“ (Crypto 2004) available at

with the following 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."


For participation in this virtual format, please write an e-mail to the organizer (see above).

More information