Paper 2020/1095

Cycle structure of generalized and closed loop invariants

Yongzhuang Wei, Rene Rodriguez, and Enes Pasalic


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.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Block ciphersGeneralized nonlinear invariantsPermutation cyclesClosed loop invariantsLinear structureDistinguishing attacksSP networks
Contact author(s)
enes pasalic6 @ gmail com
2020-09-15: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.