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.
Type de document :
Communication dans un congrès
Springer. Eurocrypt, Apr 2008, Istanbul, Turkey. 4965, pp.270-288, 2008, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/p3558g52822mmj23/〉. 〈10.1007/978-3-540-78967-3_16〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00417796
Contributeur : Charles Bouillaguet <>
Soumis le : jeudi 17 septembre 2009 - 00:05:20
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mardi 15 juin 2010 - 22:02:04

Fichier

eurocrypt2008.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan Hoch, John Kelsey, et al.. Second Preimage Attacks on Dithered Hash Functions. Springer. Eurocrypt, Apr 2008, Istanbul, Turkey. 4965, pp.270-288, 2008, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/p3558g52822mmj23/〉. 〈10.1007/978-3-540-78967-3_16〉. 〈inria-00417796〉

Partager

Métriques

Consultations de la notice

403

Téléchargements de fichiers

300