Security Analysis of SIMD

Charles Bouillaguet 1 Pierre-Alain Fouque 1, 2, 3 Gaëtan Leurent 3
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 the SHA-3 candidate SIMD. We first show a new free-start distinguisher based on symmetry relations. It allows to distinguish the compression function of SIMD from a random function with a single evaluation. However, we also show that this property is very hard to exploit to mount any attack on the hash function because of the mode of operation of the compression function. Essentially, if one can build a pair of symmetric states, the symmetry property can only be triggered once. In the second part, we show that a class of free-start distinguishers is not a threat to the wide-pipe hash functions. In particular, this means that our distinguisher has a minimal impact on the security of the hash function, and we still have a security proof for the SIMD hash function. Intuitively, the reason why this distinguisher does not weaken the function is that getting into a symmetric state is about as hard as finding a preimage. Finally, in the third part we study differential path in SIMD, and give an upper bound on the probability of related key differential paths. Our bound is in the order of 2?n/2 using very weak assumptions. Resistance to related key attacks is often overlooked, but it is very important for hash function designs.
Type de document :
Communication dans un congrès
Alex Biryukov. Selected Areas in Cryptography, 10th Annual International Workshop, SAC 2010, 2010, Ontario, Canada. Springer, 2010, Lecture Notes in Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00556680
Contributeur : Pierre-Alain Fouque <>
Soumis le : lundi 17 janvier 2011 - 15:37:09
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10
Document(s) archivé(s) le : mardi 6 novembre 2012 - 11:37:36

Fichier

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

Identifiants

  • HAL Id : inria-00556680, version 1

Collections

Citation

Charles Bouillaguet, Pierre-Alain Fouque, Gaëtan Leurent. Security Analysis of SIMD. Alex Biryukov. Selected Areas in Cryptography, 10th Annual International Workshop, SAC 2010, 2010, Ontario, Canada. Springer, 2010, Lecture Notes in Computer Science. 〈inria-00556680〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

147