Paper 2020/1163

Specifying cycles of minimal length for commonly used linear layers in block ciphers

Guoqiang Deng, Yongzhuang Wei, Xuefeng Duan, Enes Pasalic, and Samir Hodzic


With the advances of Internet-of-Things (IoT) applications in smart cities and the pervasiveness of network devices with limited resources, lightweight block ciphers have achieved rapid development recently. Due to their relatively simple key schedule, nonlinear invariant attacks have been successfully applied to several families of lightweight block ciphers. This attack relies on the existence of a nonlinear invariant $g:\F_2^n \rightarrow \F_2$ for the round function $F_k$ so that $g(x) + g(F_k(x))$ is constant for any input value $x$. Whereas invariants of the entire $S$-box layer has been studied in terms of the corresponding cycle structure [TLS16,WRP20] (assuming the use of bijective S-boxes), a similar analysis for the linear layer has not been performed yet. In this article, we provide a theoretical analysis for specifying the minimal length of cycles for commonly used linear permutations (implementing linear layers) in lightweight block ciphers. Namely, using a suitable matrix representation, we exactly specify the minimal cycle lengths for those (efficiently implemented) linear layers that employ ShiftRows, Rotational-XOR and circular Boolean matrix operations which can be found in many well-known families of block ciphers. These results are practically useful for the purpose of finding nonlinear invariants of the entire encryption rounds since these can be specified using the intersection of cycles corresponding to the linear and S-box layer. We also apply our theoretical analysis practically and specify minimal cycle lengths of linear layers for certain families of block ciphers including some NIST candidates.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Cyclic shiftXORCycle of linear layerPermutation matrixNonlinear invariant
Contact author(s)
enes pasalic6 @ gmail com
2020-09-25: received
Short URL
Creative Commons Attribution


      author = {Guoqiang Deng and Yongzhuang Wei and Xuefeng Duan and Enes Pasalic and Samir Hodzic},
      title = {Specifying cycles of minimal length   for commonly used  linear layers in block ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1163},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.