Cryptology ePrint Archive: Report 2020/1095

Cycle structure of generalized and closed loop invariants

Yongzhuang Wei and 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.

Category / Keywords: secret-key cryptography / Block ciphers; Generalized nonlinear invariants; Permutation cycles; Closed loop invariants; Linear structure; Distinguishing attacks; SP networks

Date: received 11 Sep 2020

Contact author: enes pasalic6 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200915:111809 (All versions of this report)

Short URL: ia.cr/2020/1095


[ Cryptology ePrint archive ]