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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/inria-00417796
Contributor : Charles Bouillaguet <>
Submitted on : Thursday, September 17, 2009 - 12:05:20 AM
Last modification on : Thursday, October 15, 2020 - 2:42:03 PM
Long-term archiving on: : Tuesday, June 15, 2010 - 10:02:04 PM

File

eurocrypt2008.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

516

Files downloads

499