Detection of non-trivial preservable quotient spaces in S-Box(es)

Substitution Box (S-Box) is employed in block ciphers to ensure non-linearity. An n-bit bijective S-Box is a member of the Symmetric Group S2n . Ideally, an S-Box must follow a stringent cryptographic profile. Designing an S-Box is a transparent and justified process. The concerning point for an evaluator is the presence of vulnerabilities in the design of an S-Box, i.e., Kuznyechick. If a malicious designer keeps the non-trivial subspaces secret, it leads to sophisticated cryptanalytic attacks. This article investigates the behaviour of non-trivial subspaces in an S-Box and its Affine, Extended Affine (EA) and Carlet-Charpin-Zinoviev (CCZ) equivalence classes. This paper presents a novel algorithm for finding preservable quotient spaces in an S-Box, thus leveraging a way for shortlisting the potential candidates for an S-Box with backdoors. The proposed work emphasizes checking whether a target S-Box is a potential backdoor candidate. The backdoored designs proposed by KG Paterson, Carlo Harpes and Bannier are being identified and validated with the help of the proposed algorithm. Our findings establish that the additive linear structures responsible for the non-trivial subspace are not invariant under the EA and CCZ. Moreover, the analysis of 3 - bit permutations reveals that almost 23% population of S23 preserve the quotient subspaces. Irrespective of the linear structures in its non-linear layer, the NIST Lightweight competitors do not preserve the quotient spaces in both the input and output space.