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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Cyclic shiftXORCycle of linear layerPermutation matrixNonlinear invariant
Contact author(s)
enes pasalic6 @ gmail com
History
2020-09-25: received
Short URL
https://ia.cr/2020/1163
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1163,
      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{https://eprint.iacr.org/2020/1163}},
      url = {https://eprint.iacr.org/2020/1163}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.