Second Preimage Attacks on Dithered Hash Functions

Published

April 17, 2008

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)

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-540-78967-3_16

Local Download

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 January 2, 2025)