Herding, Second Preimage, and Trojan Message Attacks Beyond Merkle-Damgaard

Published

November 3, 2009

Author(s)

Elena Andreeva, Charles Bouillaguet , Orr Dunkelman, John M. Kelsey

Abstract

In this paper we present new attack techniques to analyze the structure of hash functions that are not based on the classical Merkle-Damgaard construction. We extend the herding attack to concatenated hashes, and to certain hash functions that process each message block several times. Using this technique, we show a second preimage attack on the folklore "hash-twice" construction which process two concatenated copies of the message. We follow with showing how to apply the herding attack to tree hashes. Finally, we present a new type of attack - the trojan message attack, which allows for producing second preimages of unknown messages (from a small known space) when they are appended with a fixed suffix.

Proceedings Title

Selected Areas in Cryptography (Lecture Notes in Computer Science)

Volume

5867

Conference Dates

August 13-14, 2009

Conference Location

Calgary, CA

Conference Title

16th Annual International Workshop, Selected Areas in Cryptography (SAC 2009)

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-642-05445-7_25

Local Download

Keywords

concatenated hash, herding attack, second preimage attack, tree hash, Trojan message attack, zipper hash

Citation

Andreeva, E. , Bouillaguet, C. , Dunkelman, O. and Kelsey, J. (2009), Herding, Second Preimage, and Trojan Message Attacks Beyond Merkle-Damgaard, Selected Areas in Cryptography (Lecture Notes in Computer Science), Calgary, CA, [online], https://doi.org/10.1007/978-3-642-05445-7_25, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=903353 (Accessed January 2, 2025)