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.

Second Preimage Attacks on Dithered Hash Functions

Published

Author(s)

Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan J. Hoch, John M. Kelsey, Adi Shamir, Sebastien Zimmer

Abstract

We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean Dean99} and Kelsey and Schneier KS05} with the herding attack of Kelsey and Kohno KK06}. We show that these generic attacks apply to hash functions using the Merkle-Damgård construction with only slightly more work than the previously known attack, but allow enormously more control of the contents of the second preimage found. Additionally, we show that our new attack applies to several hash function constructions which are not vulnerable to the previously known attack, including the dithered hash proposal of Rivest Rivest05Abelian}, Shoup s UOWHF Shoup00b} and the ROX hash construction ANPS07}.We analyze the properties of the dithering sequence used in Rivest05Abelian}, and develop a time-memory tradeoff which allows us to apply our second preimage attack to a wide range of dithering sequences, including sequences which are much stronger than those in Rivest s proposals. Finally, we show that both the existing second preimage attacks Dean99,KS05} and our new attack can be applied even more efficiently to multiple target messages; in general, given a set of many target messages with a total of 2R message blocks, these second preimage attacks can find a second preimage for one of those target messages with no more work than would be necessary to find a second preimage for a single target message of 2[R] message blocks.
Proceedings Title
Advances in Cryptology – EUROCRYPT 2008 (Lecture Notes in Computer Science)
Volume
4965
Conference Dates
April 13-17, 2008
Conference Location
Istanbul, TR
Conference Title
27th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2008)

Keywords

Cryptanalysis, Hash Function, Dithering

Citation

Andreeva, E. , Bouillaguet, C. , Fouque, P. , Hoch, J. , Kelsey, J. , Shamir, A. and Zimmer, S. (2008), Second Preimage Attacks on Dithered Hash Functions, Advances in Cryptology – EUROCRYPT 2008 (Lecture Notes in Computer Science), Istanbul, TR, [online], https://doi.org/10.1007/978-3-540-78967-3_16, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=152101 (Accessed March 29, 2024)
Created April 16, 2008, Updated October 12, 2021