Cryptanalysis of Tweaked Versions of SMASH and Reparation

Pierre-Alain Fouque 1, 2, 3 Jacques Stern 3 Sebastien Zimmer 1, 2
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : In this paper, we study the security of permutation based hash functions, i.e. block-cipher based hash functions with fixed keys. SMASH is such a hash function presented by Knudsen in 2005 and broken the same year by Rijmen \textit{et al.} Here we show that the tweaked version, proposed soon after to thward the attack can also be attacked in collusion in time $2O(^{n/3})$. This time complexity can be reduced to $O(2^{2\sqrtn})$ for the first tweak version, which means an attack against SMASH-256 in $c\cdot 2^32$ for a small constant $c$. Then, we show that a generalisation of SMASH, using two permutations instead of one, can be proven secure against collision in the ideal-cipher model in $\Omega(2^{n/4})$ queries to the permutations. In order to analyze the tightness of the proof, we devise a non-trivial attack in $O(2^{3n/8})$ queries, which is the best security level that can be reached for 2-permutation based hash functions.
Type de document :
Communication dans un congrès
Roberto Maria Avanzi and Liam Keliher and Francesco Sica. Selected Areas in Cryptography, 15th International Workshop, SAC 2008, 2009, Sackville, New Brunswick, Canada. Springer, 5381, pp.136-150, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-04159-4_9〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00556682
Contributeur : Pierre-Alain Fouque <>
Soumis le : lundi 17 janvier 2011 - 15:37:20
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10
Document(s) archivé(s) le : lundi 18 avril 2011 - 03:00:29

Fichier

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

Identifiants

Collections

Citation

Pierre-Alain Fouque, Jacques Stern, Sebastien Zimmer. Cryptanalysis of Tweaked Versions of SMASH and Reparation. Roberto Maria Avanzi and Liam Keliher and Francesco Sica. Selected Areas in Cryptography, 15th International Workshop, SAC 2008, 2009, Sackville, New Brunswick, Canada. Springer, 5381, pp.136-150, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-04159-4_9〉. 〈inria-00556682〉

Partager

Métriques

Consultations de la notice

313

Téléchargements de fichiers

194