Augmented sets of output differences and new distinguishers for SPN ciphers

Area of Science:

• Cryptography and Network Security
• Abstract Algebra and Coding Theory

Background:

• Substitution Permutation Networks (SPNs) are a fundamental class of block ciphers.
• Existing cryptanalytic methods for SPNs, such as subspace trails, have limitations in distinguishing cipher behavior.
• The need for robust and efficient distinguishers is critical for assessing cipher security.

Purpose of the Study:

• To introduce novel generic and black-box distinguishers for SPN ciphers.
• To develop an efficient algorithm for computing these distinguishers.
• To evaluate the effectiveness of the new distinguishers against established cryptographic primitives.

Main Methods:

• Construction of augmented vector spaces of output differences based on a novel vector transformation.
• Leveraging Reed-Muller codes to determine the rank of the linear span of augmented sets.
• Experimental estimation of the number of vectors required to span these augmented spaces.
• Development and application of an efficient algorithm for computing augmented vector spaces for SPNs.

Main Results:

• The rank of the linear span of the d-order augmented set is proven to be 2^n - 2^(n-d).
• Experimental analysis provides insights into the vector requirements for spanning augmented spaces.
• The developed algorithm efficiently computes d-order augmented vector spaces for SPN ciphers.
• New distinguishers for GIFT, PRESENT, and SKINNY ciphers cover more rounds than subspace trails.

Conclusions:

• Augmented vector spaces of output differences provide powerful new distinguishers for SPN ciphers.
• The proposed method offers a generic and efficient approach to cryptanalysis.
• The new distinguishers demonstrate superior performance, extending the analysis of round-reduced lightweight ciphers.