Paper 2015/484

More Rounds, Less Security?

Jian Guo, Jérémy Jean, Nicky Mouha, and Ivica Nikolić

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Iterated cipherfixed pointsslide attackPRIDEChaskeyPKCSPBKDF1Unix password hashing algorithmEven-MansourFX-construction.
Contact author(s)
nicky @ mouha be
History
2016-06-02: last of 3 revisions
2015-05-21: received
See all versions
Short URL
https://ia.cr/2015/484
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/484,
      author = {Jian Guo and Jérémy Jean and Nicky Mouha and Ivica Nikolić},
      title = {More Rounds, Less Security?},
      howpublished = {Cryptology ePrint Archive, Paper 2015/484},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/484}},
      url = {https://eprint.iacr.org/2015/484}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.