HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Second Preimage Attacks on Dithered Hash Functions

Abstract : We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean [8] and Kelsey and Schneier [16] with the herding attack of Kelsey and Kohno [15]. 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 [25], Shoup's UOWHF[26] and the ROX hash construction [2]. We analyze the properties of the dithering sequence used in [25], 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 [8, 16] 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 2^R 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

Contributor : Charles Bouillaguet Connect in order to contact the contributor
Submitted on : Thursday, September 17, 2009 - 12:05:20 AM
Last modification on : Thursday, March 17, 2022 - 10:08:35 AM
Long-term archiving on: : Tuesday, June 15, 2010 - 10:02:04 PM


Files produced by the author(s)




Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan Hoch, John Kelsey, et al.. Second Preimage Attacks on Dithered Hash Functions. Eurocrypt, Apr 2008, Istanbul, Turkey. pp.270-288, ⟨10.1007/978-3-540-78967-3_16⟩. ⟨inria-00417796⟩



Record views


Files downloads