Proving Resistance Against Infinitely Long Subspace Trails: How to Choose the Linear Layer

Abstract

Designing cryptographic permutations and block ciphers using a substitution-permutation network (SPN) approach where the nonlinear part does not cover the entire state has recently gained attention due to favorable implementation characteristics in various scenarios.

For word-oriented partial SPN (P-SPN) schemes with a fixed linear layer, the goal is to better understand how the details of the linear layer affect the security of the construction. In this paper, the authors derive conditions that allow to either set up or prevent attacks based on infinitely long truncated differentials with probability 1. The analysis considers (1) both invariant and non-invariant/iterative trails, and (2) trails with and without active S-boxes.

For these cases, rigorous sufficient and necessary conditions are provided for the matrix that defines the linear layer to prevent the analyzed attacks. A tool is presented that can determine whether a given linear layer is vulnerable based on these results. Furthermore, a sufficient condition for the linear layer is proposed that, if satisfied, ensures that no infinitely long truncated differential exists. This condition is related to the degree and the irreducibility of the minimal polynomial of the matrix that defines the linear layer.

Besides P-SPN schemes, the observations may also have a crucial impact on the Hades design strategy, which mixes rounds with full S-box layers and rounds with partial S-box layers.

Keywords: Partial SPN, Linear Layer, Subspace Trails, Hades Schemes

1. Introduction

Modern cryptography developed many techniques that go well beyond solving traditional confidentiality and authenticity problems in two-party communications. This includes practical applications of secure multi-party computation (MPC), (fully) homomorphic encryption (FHE), and zero-knowledge (ZK) proofs using symmetric primitives. Designs of primitives in symmetric cryptography for these applications are usually led by heuristics such as simplifying their arithmetic representations or linear operations being more efficient than nonlinear ones in these scenarios. The latter example is also used in the context of masking, a widespread countermeasure against side-channel attacks.

Driven by all these application areas, many new symmetric primitives have recently been proposed. They include on one hand masking-friendly designs like NOEKEON [DPAR00], PICARO [PRC12], Zorro [GGNPS13], LS-designs [GLSV14], and candidates from the currently ongoing effort of choosing a next "lightweight" generation of primitives. On the other hand, there is an increasing number of MPC-/FHE-/ZK-friendly proposals, including LowMC [ARS+15], FLIP [MJSC16], Kreyvium [CCF+18], Rasta [DEG+18], MiMC [AGR+16], GMiMC [AGP+19], HADESMiMC [GLR+20b], Ciminion [DGGK19], JARVIS and FRIDAY [AD18], Vision and Rescue [AAB+20], and POSEIDON [GKR+21].

1.1 Choosing the Linear Layer in Partial SPN Schemes

Some of the recalled designs (e.g., LowMC, Zorro, HADESMiMC and POSEIDON) reach the goal of minimizing the total number of multiplications by making use of rounds with a partial S-box layer. These designs are called partial substitution-permutation network (P-SPN) schemes. They are a variant of SPN schemes, in which an input block is transformed into an output block by applying several alternating rounds of substitution boxes and affine permutations. For a t-word SPN scheme over a fixed finite field, the substitution layer usually consists of t parallel (independent) nonlinear functions, called S-boxes. In many cases, the permutation layer is a linear operation defined by the multiplication of the state with a t \times t matrix. In the case of a P-SPN, however, part of the substitution layer is replaced by an identity mapping, leading to practical advantages for applications in which nonlinear operations are more expensive than linear operations.

Many strategies proposed in the literature to guarantee security for SPN schemes are no longer applicable to P-SPN schemes and have to be replaced by more ad-hoc approaches. This includes the well-known wide trail strategy [DR02], which is one of the main techniques for achieving security against various statistical attacks. In the case of Zorro, the heuristic argument proposed by the designers turned out to be insufficient, as iterative differential and linear characteristics were later found [WWGY14, BDD+15]. Similarly, the authors of LowMC chose the number of rounds to guarantee that no differential or linear characteristic can cover the entire function with non-negligible probability. However, they do not provide similarly strong security arguments against other attack vectors, and key-recovery attacks on LowMC have been found [DLMW15].

1.2 Our Contribution and Related Work

Automated characteristic search tools and dedicated key-recovery algorithms for SP networks with partial nonlinear layers have been presented in [BDD+15]. As a main result, this tool can be used to understand how many rounds a given scheme requires to be secure. However, focusing on the matrix that defines the fixed linear layer in a P-SPN scheme, it is not clear which properties this matrix must satisfy to prevent cryptanalytic attacks in general.

Our Goal. The authors aim at a relevant subset of undesirable properties that can lead to attacks: infinitely long truncated differentials with probability 1 [Knu94], or equivalently infinitely long subspace trails [GRR16a, GRR17], i.e., the existence of a nontrivial subspace \mathcal{U} \subseteq \mathbb{F}_q^t of inputs that is mapped into a proper (affine) subspace of the state space over any number of rounds.

Impact of Subspace Trails on Hades-Like Schemes. While such a subspace trail on its own represents a distinguisher, it can also be the starting point for an attack. A preimage attack on the hash function Poseidon based on the existence of such trails has recently been shown in [BCD+20, Sect. 6.2]. The attacked hash function is based on the Hades design strategy [GLR+20b], which uses external rounds with full S-box layers and middle rounds with partial S-box layers.

Infinitely Long Subspace Trails: Necessary & Sufficient Conditions for P-SPN Schemes. The authors present sufficient and necessary conditions that the matrix defining the linear layer must satisfy to guarantee that no infinitely long (nontrivial) subspace trails exist. Specifically, they analyze:

1. the case without active S-boxes in which the input of the S-box is constant (Sections 3 and 4), and
2. the case with active S-boxes in which the input of the S-box can take any possible value (Section 6).

In both cases, the analysis is independent of the round keys and round constants. In the particular case in which the matrix is diagonalizable, the infinitely long subspace trail (if existent) is always related to the eigenspaces of the matrix. More generally, the infinitely long subspace trails are always related to the invariant subspaces of the matrix M defining the linear layer, which can be found via the primary decomposition theorem.

Dedicated Tool. Together with the theoretical observations, practical Sage implementations are also provided. Given a square matrix, the tool can detect the vulnerabilities described in this paper (invariant and iterative trails), both in the case with and without active S-boxes and for binary and prime fields.

2. Preliminaries

Notation. The finite fields are denoted by \mathbb{F}_q, where q = 2^n or q = p^n for a prime p \geq 3 and n \in \mathbb{N}. For brevity, \mathbb{F} is used instead of \mathbb{F}_q. Subspaces are denoted with calligraphic letters (e.g., \mathcal{S}). Given a subspace \mathcal{S} \subseteq \mathbb{F}^t, \mathcal{S}^c denotes a complementary subspace such that \mathcal{S} \oplus \mathcal{S}^c = \mathbb{F}^t. The symbol \oplus denotes the direct sum. The unit vectors of \mathbb{F}_q^t are \{e_1, \ldots, e_t\}.

2.1 Partial SPN Schemes

The paper focuses on P-SPN block ciphers and permutations over (\mathbb{F}_q^t, +, \cdot). All results are independent of the round keys and constants.

Partial SPN (P-SPN) Schemes. The application of r rounds of a t-word P-SPN scheme is denoted by E^r : \mathbb{F}^t \to \mathbb{F}^t. Let 1 \leq s < \lceil t/2 \rceil be the number of S-boxes per round. The composition of the S-box layer and of the linear layer is:

where S_i : \mathbb{F} \to \mathbb{F} for i \in \{1, \ldots, s\} is a nonlinear permutation, and hence t - s input words are unaffected by the S-box layer. The linear layer is defined by the multiplication with an invertible matrix M \in \mathbb{F}^{t \times t}.

Hades-Like Schemes. The recently proposed HADES strategy [GLR+20b] combines both SPN and partial SPN schemes. The initial R_f and the final R_f rounds contain full S-box layers, for a total of R_F = 2R_f rounds. In the middle, R_P rounds with partial S-box layers are used.

2.2 Invariant Subspaces and Subspace Trails

2.3 Decomposition Theorem & Frobenius Normal Form

3. Infinitely Long Invariant Subspace Trails for P-SPN Schemes (Without Active S-Boxes)

Focusing on P-SPN schemes which use the same linear layer in each round, this section studies the properties that the matrix defining the linear layer must satisfy in order to prevent infinitely long invariant subspace trails without active S-boxes.

3.1 Preliminary Results

3.2 Infinitely Long Invariant Subspace Trails via Eigenspaces of M

3.3 Necessary and Sufficient Condition

4. Iterative Subspace Trails Without Active S-Boxes

4.1 Linear Layers with Low Multiplicative Order

Cauchy Matrices in [GKR+21]. The Cauchy matrix proposed for Starkad/Poseidon over \mathbb{F}_{2^n} with t = 2^\tau has multiplicative order 2, enabling iterative trails as shown in [KR21, BCD+20].

4.2 Linear Layers with Low-Degree Minimal Polynomials

5. Practical Tests (Without Active S-Boxes)

5.1 Algorithm for Detecting Weak Matrices

Algorithm 1 uses Theorem 3 and Proposition 4. First, the full space is decomposed into M-invariant subspaces via Theorem 1. Then intersection with identity positions is taken: \mathcal{X}_i^{(0)} = \mathcal{A}_i \cap \langle e_{s+1}, \ldots, e_t \rangle. Proposition 4 is applied iteratively until the dimension stabilizes or reaches zero. The matrix is vulnerable if \dim(\mathcal{I}) > 0. Computational cost is \mathcal{O}(t^3).

5.2 Percentage of Weak Linear Layers

With a sample size of 100,000, focusing on s = 1, both random invertible and random Cauchy matrices were tested over prime and binary fields.

Increasing p (or n) tends to produce more secure matrices. Even for small fields, a secure matrix can easily be found by testing a small number of candidates.

6. Infinitely Long Subspace Trails for P-SPN Schemes (Active S-Boxes)

Assumption on the S-Box. From now on, only S-boxes without any nontrivial linear structures are considered. That is, it is not possible to find nontrivial subspaces \mathcal{U}, \mathcal{V} \subset \mathbb{F} such that for each u there exists v with S(\mathcal{U} + u) = \mathcal{V} + v. Both the AES S-box and the cube map x \mapsto x^3 satisfy this.

6.1 Preliminary Results: Subspace Trails & Truncated Differentials

6.2 Infinitely Long Invariant Subspace Trails with Active S-Boxes via Eigenspaces of M

6.3 Necessary and Sufficient Condition (Active S-boxes)

6.4 Infinitely Long Iterative Subspace Trails with Active S-Boxes

About Iterative Subspace Trails with Active S-Boxes. There exist P-SPN schemes with iterative subspace trails with active S-boxes but no invariant trails. For example, the 3 \times 3 matrix

over \mathbb{F}_p^3 with s = 1 admits the iterative trail (\langle (1,0,0)^T \rangle, \langle (0,1,1)^T \rangle, \langle (0,1,2)^T \rangle) of period 3 with active S-boxes. Since \dim(\langle \mathcal{V}_0, \mathcal{V}_1, \mathcal{V}_2 \rangle) = 3, no invariant subspace trail can be set up.

7. Practical Tests (Active S-Boxes)

This section proposes two algorithms: one for infinitely long invariant subspace trails with active S-boxes, and one for iterative trails. Several matrices are tested over \mathbb{F}_p and \mathbb{F}_{2^n}.

7.1 Related Strategies in the Literature

The algorithms are based on the approach from [LMR15]. Given an SPN-like permutation, the goal is to find a subspace \mathcal{U} and offset u that is invariant under the keyless round function. The approach guesses a one-dimensional subspace and increases the space by computing \mathcal{A}_{i+1} = \langle R(\mathcal{A}_i + u) - v, \mathcal{A}_i \rangle until stabilization.

7.2 Algorithms for Detecting Weak Matrices

Algorithm 2 (invariant trails with active S-boxes): For each non-empty subset I_s \subseteq \{1, \ldots, s\}, start with the subspace generated by the unit vectors at active S-box positions. Keep including M^j \cdot e_i to the space until stabilization. Runtime is \mathcal{O}(2^s \cdot s \cdot t).

Algorithm 3 (iterative trails with active S-boxes): Replaces the single set I_s by l potentially different sets I_1, \ldots, I_l. Total runtime is \mathcal{O}(ls(2^s t + l)).

7.3 Percentage of Weak Linear Layers

Results across Algorithms 1, 2, and 3 show that the vulnerability percentages are generally small. A similar amount of matrices is vulnerable w.r.t. Algorithm 2 as w.r.t. Algorithm 1. Matrices vulnerable only to Algorithm 3 (but not 1 or 2) are extremely rare (< 0.01% in nearly all cases).

8. Security Against Infinitely Long Subspace Trails

This section presents a sufficient condition on the matrix defining the linear layer that -- if satisfied -- ensures that no infinitely long (invariant/iterative) subspace trail (with/without active S-boxes) exists. The condition involves only the minimal polynomial of the matrix and is independent of the number of S-boxes per round.

8.1 Sufficient Condition for Preventing Infinitely Long Subspace Trails

Discussion. Given an irreducible polynomial \phi \in \mathbb{F}[x] of degree t, all matrices similar to the companion matrix of \phi satisfy Proposition 13. The percentage of Cauchy MDS matrices satisfying this condition ranges from approximately 8% (for t = 12) to over 33% (for t = 3). Since this is only a sufficient condition, matrices that do not satisfy it may still be secure.

8.2 Open Problems

• Given a matrix for which no infinitely long subspace trail exists, how many rounds are needed to activate at least one S-box? Practical tests suggest t + \varepsilon rounds for \varepsilon \in \{0, 1\}.
• If the S-box has a nontrivial linear structure, the results for active S-boxes may be extendable.
• In the binary case, extending results to linear layers defined via linearized polynomials.

Appendix A. Truncated Differentials and Subspace Trails

Differential attacks [BS91] exploit pairs of inputs with certain differences yielding other differences in the outputs with a non-uniform probability distribution. Truncated differential attacks [Knu94] predict only part of the difference. Using subspace terminology: given pairs of inputs in the same coset of \mathcal{X}, one considers the probability that outputs belong to the same coset of \mathcal{Y}.

The proof of Proposition 10 shows that the subspace trail over the first \mathfrak{R} rounds (no active S-boxes) can be extended by increasing the subspace dimension: at each subsequent round, the S-box outputs are absorbed into the subspace, adding s dimensions per round. The trail persists for at least \mathfrak{R} + \lfloor (t-s)/s \rfloor rounds total.

Appendix B. Infinitely Long Iterative Subspace Trails with Active S-Boxes

Algorithm 3 searches for iterative trails of maximum period l = 2t. For each period r from 2 to l, and for each non-empty subset of S-box positions, Algorithm 2 is applied to M^r. If a meaningful subspace \mathcal{I} is found (i.e., not invariant under M itself), the algorithm checks that M^j \cdot \mathcal{I} is compatible with valid S-box positions at each step. Total runtime is \mathcal{O}(ls(2^s t + l)).

Appendix C. Results Using the Tool and More Examples

C.1 Starkad and Poseidon Matrices. The Cauchy matrices from the Starkad and Poseidon specifications were tested. The Starkad matrix M' over \mathbb{F}_{2^n} and the Poseidon matrix M'' over \mathbb{F}_p are defined as M'_{i,j} = 1/(x_i \oplus y_j) and M''_{i,j} = 1/(x_i + y_j) where x_i = i, y_i = i + t.

These results confirm findings from [KR21, BCD+20]. The fix proposed in [KR21] (changing starting sequences for Cauchy generation) produces matrices with no infinitely long subspace trails.

C.2 Zorro Matrix. The Zorro matrix (a P-SPN over (\mathbb{F}_{2^8})^{16} with s = 4) was also evaluated. No infinitely long (iterative or invariant) subspace trail was found, neither with nor without active S-boxes. The known attacks on Zorro exploit differentials with higher-than-expected probability, not infinitely long subspace trails.

References

• [AAB+20] Aly, Ashur, Ben-Sasson, Dhooghe, Szepieniec. Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols. IACR Trans. Symmetric Cryptol. 2020(3):1-45.
• [AÅBL12] Abdelraheem, Ågren, Beelen, Leander. On the Distribution of Linear Biases: Three Instructive Examples. CRYPTO 2012, LNCS 7417, pp. 50-67.
• [AD18] Ashur, Dhooghe. MARVELlous: a STARK-Friendly Family of Cryptographic Primitives. ePrint 2018/1098.
• [AGP+19] Albrecht, Grassi, Perrin, Ramacher, Rechberger, Rotaru, Roy, Schofnegger. Feistel Structures for MPC, and More. ESORICS 2019, LNCS 11736, pp. 151-171.
• [AGR+16] Albrecht, Grassi, Rechberger, Roy, Tiessen. MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. ASIACRYPT 2016, LNCS 10031, pp. 191-219.
• [ARS+15] Albrecht, Rechberger, Schneider, Tiessen, Zohner. Ciphers for MPC and FHE. EUROCRYPT 2015, LNCS 9056, pp. 430-454.
• [BBI+15] Banik et al. Midori: A Block Cipher for Low Energy. ASIACRYPT 2015, LNCS 9453, pp. 411-436.
• [BCD+20] Beyne, Canteaut, Dinur, Eichlseder, Leander, Leurent, Naya-Plasencia, Perrin, Sasaki, Todo, Wiemer. Out of Oddity -- New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems. CRYPTO 2020, LNCS 12172, pp. 299-328.
• [BCLR17] Beierle, Canteaut, Leander, Rotella. Proving Resistance Against Invariant Attacks. CRYPTO 2017, LNCS 10402, pp. 647-678.
• [BDD+15] Bar-On, Dinur, Dunkelman, Lallemand, Keller, Tsaban. Cryptanalysis of SP Networks with Partial Non-Linear Layers. EUROCRYPT 2015, LNCS 9056, pp. 315-342.
• [Bey18] Beyne. Block Cipher Invariants as Eigenvectors of Correlation Matrices. ASIACRYPT 2018, LNCS 11272, pp. 3-31.
• [BS91] Biham, Shamir. Differential Cryptanalysis of DES-like Cryptosystems. J. Cryptology 4(1):3-72.
• [CCF+18] Canteaut, Carpov, Fontaine, Lepoint, Naya-Plasencia, Paillier, Sirdey. Stream Ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression. J. Cryptology 31(3):885-916.
• [DEG+18] Dobraunig, Eichlseder, Grassi, Lallemand, Leander, List, Mendel, Rechberger. Rasta: A Cipher with Low ANDdepth and Few ANDs per Bit. CRYPTO 2018, LNCS 10991, pp. 662-692.
• [DGGK19] Dobraunig, Grassi, Guinet, Kuijsters. Ciminion: Symmetric Encryption Based on Toffoli-Gates over Large Finite Fields. EUROCRYPT 2021.
• [DLMW15] Dinur, Liu, Meier, Wang. Optimized Interpolation Attacks on LowMC. ASIACRYPT 2015, LNCS 9453, pp. 535-560.
• [DPAR00] Daemen, Peeters, Van Assche, Rijmen. Nessie Proposal: NOEKEON. 2000.
• [DR02] Daemen, Rijmen. AES and the Wide Trail Design Strategy. EUROCRYPT 2002, LNCS 2332, pp. 108-109.
• [GGNPS13] Gerard, Grosso, Naya-Plasencia, Standaert. Block Ciphers That Are Easier to Mask. CHES 2013, LNCS 8086, pp. 383-399.
• [GKR+21] Grassi, Khovratovich, Rechberger, Roy, Schofnegger. Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. USENIX Security 2021.
• [GLR+20a] Grassi, Leander, Rechberger, Tezcan, Wiemer. Weak-Key Distinguishers for AES. SAC 2020.
• [GLR+20b] Grassi, Luftenegger, Rechberger, Rotaru, Schofnegger. On a Generalization of Substitution-Permutation Networks: The HADES Design Strategy. EUROCRYPT 2020, LNCS 12106, pp. 674-704.
• [GLSV14] Grosso, Leurent, Standaert, Varici. LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations. FSE 2014, LNCS 8540.
• [GRR16a] Grassi, Rechberger, Ronjom. Subspace Trail Cryptanalysis and its Applications to AES. IACR Trans. Symmetric Cryptol. 2016(2):192-225.
• [GRR17] Grassi, Rechberger, Ronjom. A new structural-differential property of 5-round AES. EUROCRYPT 2017, LNCS 10211, pp. 289-317.
• [Hog16] Hogben. Handbook of Linear Algebra. CRC Press, 2nd ed.
• [Kai08] Kaiser. Advanced Linear Algebra. 2008.
• [Knu94] Knudsen. Truncated and Higher Order Differentials. FSE 1994, LNCS 1008, pp. 196-211.
• [KR21] Keller, Rosemarin. Mind the Middle Layer: The HADES Design Strategy Revisited. EUROCRYPT 2021.
• [LAAZ11] Leander, Abdelraheem, AlKhzaimi, Zenner. A Cryptanalysis of PRINTcipher: The Invariant Subspace Attack. CRYPTO 2011, LNCS 6841, pp. 206-221.
• [LMR15] Leander, Minaud, Ronjom. A Generic Approach to Invariant Subspace Attacks. EUROCRYPT 2015, LNCS 9056, pp. 254-283.
• [LTW18] Leander, Tezcan, Wiemer. Searching for Subspace Trails and Truncated Differentials. IACR Trans. Symmetric Cryptol. 2018(1):74-100.
• [Mat93] Matsui. Linear Cryptanalysis Method for DES Cipher. EUROCRYPT 1993, LNCS 765, pp. 386-397.
• [MJSC16] Meaux, Journault, Standaert, Carlet. Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts. EUROCRYPT 2016, LNCS 9665.
• [PRC12] Piret, Roche, Carlet. PICARO -- A Block Cipher Allowing Efficient Higher-Order Side-Channel Resistance. ACNS 2012.
• [PW20] Peyrin, Wang. The MALICIOUS Framework: Embedding Backdoors into Tweakable Block Ciphers. CRYPTO 2020.
• [Sto98] Storjohann. An O(n^3) algorithm for the Frobenius normal form. ISSAC 1998, pp. 101-105.
• [TLS16] Todo, Leander, Sasaki. Nonlinear Invariant Attack. ASIACRYPT 2016, LNCS 10032, pp. 3-33.
• [WWGY14] Wang, Wu, Guo, Yu. Differential Cryptanalysis and Linear Distinguisher of Full-Round Zorro. ACNS 2014, LNCS 8479, pp. 308-323.
• [YMT97] Youssef, Mister, Tavares. On the Design of Linear Transformations for Substitution Permutation Encryption Networks. SAC 1996, pp. 40-48.