Paper 2020/1095

Cycle structure of generalized and closed loop invariants

Yongzhuang Wei, Rene Rodriguez, and Enes Pasalic

Abstract

This article gives a rigorous mathematical treatment of generalized and closed loop invariants (CLI) which extend the standard notion of (nonlinear) invariants used in the cryptanalysis of block ciphers. Employing the cycle structure of bijective S-box components, we precisely characterize the cardinality of both generalized and CLIs. We demonstrate that for many S-boxes used in practice quadratic invariants (especially useful for mounting practical attacks in cases when the linear layer is an orthogonal matrix) might not exist, whereas there are many quadratic invariants of generalized type (alternatively quadratic CLIs). In particular, it is shown that the inverse mapping $S(x)=x^{-1}$ over $GF(2^4)$ admits quadratic CLIs that additionally possess linear structures. The use of cycle structure is further refined through a novel concept of active cycle set, which turns out to be useful for defining invariants of the whole substitution layer. We present an algorithm for finding such invariants provided the knowledge about the cycle structure of the constituent S-boxes used.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Block ciphersGeneralized nonlinear invariantsPermutation cyclesClosed loop invariantsLinear structureDistinguishing attacksSP networks
Contact author(s)
enes pasalic6 @ gmail com
History
2020-09-15: received
Short URL
https://ia.cr/2020/1095
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1095,
      author = {Yongzhuang Wei and Rene  Rodriguez and Enes Pasalic},
      title = {Cycle structure of  generalized and closed loop invariants},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1095},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1095}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.