Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : Nicky Mouha Connect in order to contact the contributor
Submitted on : Wednesday, December 9, 2015 - 8:53:20 PM
Last modification on : Friday, November 4, 2022 - 3:02:51 PM
Long-term archiving on: : Thursday, March 10, 2016 - 4:27:45 PM


Files produced by the author(s)


  • HAL Id : hal-01241075, version 1



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⟩



Record views


Files downloads