More Rounds, Less Security?

Abstract : This paper focuses on a surprising class of cryptanalysis results for symmetric-key primitives: when the number of rounds of the primitive is increased, the complexity of the cryptanalysis result decreases. Our primary target will be primitives that consist of identical round functions, such as PBKDF1, the Unix password hashing algorithm, and the Chaskey MAC function. However, some of our results also apply to constructions with non-identical rounds, such as the PRIDE block cipher. First, we construct distinguishers for which the data complexity decreases when the number of rounds is increased. They are based on two well-known observations: iterating a random permutation increases the expected number of fixed points, and iterating a random function decreases the expected number of image points. We explain that these effects also apply to components of cryptographic primitives, such as a round of a block cipher. Second, we introduce a class of key-recovery and preimage-finding techniques that correspond to exhaustive search, however on a smaller part (e.g. one round) of the primitive. As the time complexity of a cryptanalysis result is usually measured by the number of full-round evaluations of the primitive, increasing the number of rounds will lower the time complexity. None of the observations in this paper result in more than a small speed-up over exhaustive search. Therefore, for lightweight applications, implementation advantages may outweigh the presence of these observations.
Type de document :
Rapport
[Research Report] Inria Paris Rocquencourt. 2015
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01241075
Contributeur : Nicky Mouha <>
Soumis le : mercredi 9 décembre 2015 - 20:53:20
Dernière modification le : mardi 13 décembre 2016 - 15:42:56
Document(s) archivé(s) le : jeudi 10 mars 2016 - 16:27:45

Fichier

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

Identifiants

  • HAL Id : hal-01241075, version 1

Collections

Citation

Ritam Bhaumik, Avijit Dutta, Jian Guo, Jérémy Jean, Nicky Mouha, et al.. More Rounds, Less Security?. [Research Report] Inria Paris Rocquencourt. 2015. 〈hal-01241075〉

Partager

Métriques

Consultations de la notice

111

Téléchargements de fichiers

57