Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

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

Published

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)

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 July 12, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created November 2, 2009, Updated October 12, 2021