Mind the Middle Layer: The HADES Design Strategy Revisited

Abstract

The HADES design strategy combines the classical SPN construction with the Partial SPN (PSPN) construction, in which at every encryption round, the non-linear layer is applied to only a part of the state. In a HADES design, a middle layer that consists of PSPN rounds is surrounded by outer layers of SPN rounds. The security arguments of HADES with respect to statistical attacks use only the SPN rounds, disregarding the PSPN rounds. This allows the designers to not pose any restriction on the MDS matrix used as the linear mixing operation.

In this paper we show that the choice of the MDS matrix significantly affects the security level provided by HADES designs. If the MDS is chosen properly, then the security level of the scheme against differential and linear attacks is significantly higher than claimed by the designers. On the other hand, weaker choices of the MDS allow for extremely large invariant subspaces that pass the entire middle layer without activating any non-linear operation (a.k.a. S-box).

We showcase our results on the Starkad and Poseidon instantiations of HADES. For Poseidon, we significantly improve the lower bounds on the number of active S-boxes with respect to both differential and linear cryptanalysis provided by the designers—for example, from 28 to 60 active S-boxes for the t = 6 variant. For Starkad, we show that for any variant with t (i.e., the number of S-boxes in each round) divisible by 4, the cipher admits a huge invariant subspace that passes any number of PSPN rounds without activating any S-box (e.g., a subspace of size 2^{1134} for the t = 24 variant). Furthermore, for various choices of the parameters, this invariant subspace can be used to mount a preimage attack on the hash function that breaks its security claims. On the other hand, we show that the problem can be fixed easily by replacing t with any value that is not divisible by four.

Following our paper, the designers of Starkad and Poseidon amended their design, by adding requirements which ensure that the MDS matrix is chosen properly.

1 Introduction

1.1 Background

Substitution-permutation network (SPN) is a classical design strategy of cryptographic permutations, used in the AES [NIST01] and in numerous other modern cryptosystems. An SPN iterates many times a sequence of operations called ‘round’, which consists of a layer of local non-linear operations (S-boxes) and a global linear mixing layer. The wide trail strategy, employed in the AES, allows designing SPNs with an easily provable lower bound on the number of active S-boxes in any differential or linear characteristic, thus providing a security guarantee with respect to the most common statistical cryptanalytic attacks.

In 2013, Gérard et al. [GGNS13] proposed the Partial SPN (PSPN) construction, in which the S-box layer is applied to only a part of the state in each round (in exchange for somewhat increasing the number of rounds). This approach, that has obvious performance advantages in various scenarios, was used in the block ciphers Zorro [GGNS13] and LowMC [ARS+15]. A drawback of this approach is that ‘clean’ security arguments (like the wide trail strategy) are not applicable for PSPNs, and thus, the security of these designs was argued by more ad-hoc approaches. These turned out to be insufficient, as Zorro was practically broken in [BDD+15] and the security of the initial versions of LowMC was shown in [DLMW15, DEM15] to be significantly lower than claimed by the designers.

At Eurocrypt 2020, Grassi et al. [GLR+20] proposed the HADES design strategy that combines the classical SPN construction with the PSPN construction. In a HADES design, a middle layer of PSPN rounds is surrounded by two layers of SPN rounds. The scheme allows enjoying ‘the best of the two worlds’—the efficiency provided by the PSPN construction, along with the clean security arguments applicable for the SPN construction. Specifically, the security arguments of the cryptosystem with respect to statistical (e.g., differential and linear) attacks are provided only by the SPN (a.k.a. ‘full’) rounds, using the wide trail strategy. The security arguments with respect to algebraic attacks use also the PSPN rounds, and take advantage of the fact that a partial non-linear layer increases the algebraic degree in essentially the same way as a ‘full’ non-linear layer. The linear layer in the HADES design is implemented by an MDS matrix (see [NIST01]), which guarantees that if the number of S-boxes in any full round is t, then any differential or linear characteristic over two full rounds activates at least t + 1 S-boxes. Since the PSPN rounds are not used in the security arguments with respect to statistical attacks, the HADES designers do not impose any restriction on the MDS used in the scheme. As a specific example, they propose using Cauchy matrices over finite fields (to be defined in Sec. 2).

The designers of HADES presented applications of their strategy for securing data transfers with distributed databases using secure multiparty computation (MPC). Subsequently, Grassi et al. proposed Starkad [GKK+19, initial version] and Poseidon [GKR+21]—hash functions whose underlying permutations are instantiations of the HADES methodology, aimed at applications for practical proof systems, such as SNARKs, STARKs, or Bulletproofs. The HADES family of algorithms (including various Starkad and Poseidon variants) was a candidate in the STARK-Friendly Hash Challenge [SW20].

1.2 Our Results

In this paper we study the effect of the MDS matrix on the security level of HADES designs. We show that when the MDS is chosen properly, the PSPN rounds can be taken into consideration in the security arguments against differential and linear attacks, leading to a very significant improvement in the lower bound on the number of active S-boxes in differential and linear characteristics. On the other hand, we show that a weaker choice of the MDS matrix may lead to existence of huge invariant subspaces for the entire middle layer that do not activate any S-box (for any number of PSPN rounds). Furthermore, for certain instances (albeit, not for the specific instances chosen in [GKK+19, initial version] and [SW20]), these invariant subspaces allow breaking the hash function with a Gröbner-basis [BW91] preimage attack.

To be specific, we focus on the variants of Starkad and Poseidon suggested in [GKK+19, initial version]. Interestingly, our results point out a sharp difference between the cases of a prime field (Poseidon) and a binary field (Starkad).

Analysis of Poseidon. In the case of Poseidon (which operates over a prime field \text{GF}(p)), for all variants proposed in [GKK+19, 11], we significantly improve the lower bound on the number of active S-boxes in differential and linear characteristics. The improvement is especially large for variants with a small number of S-boxes in each round (denoted in [GLR+20] by t). For example, for t = 6 (which is the main reference variant provided in the supplementary material of [GKK+19]), the designers claim a lower bound of 4 \cdot (6 + 1) = 28 active S-boxes, based on application of the wide trail strategy to the ‘full’ rounds. We prove that the PSPN rounds must activate at least 32 S-boxes, thus more than doubling the lower bound on the number of active S-boxes to 60. For the t = 2 variant, the improvement is most striking: there are at least 41 active S-boxes in the PSPN rounds, while the designers’ bound for the SPN rounds is 12 S-boxes. We obtain the new lower bounds using an automated characteristic search tool for PSPNs proposed in [BDD+15]. A comparison of our new lower bounds and the lower bounds of the designers is presented in Table 1.

Analysis of Starkad. In the case of Starkad (which operates over a binary field \text{GF}(2^n)), perhaps surprisingly, there is a significant difference between different values of t. For t = 24 (which is the main reference variant), we show that there exists an invariant subspace U of size 2^{18 \cdot 63} = 2^{1134} that does not activate the S-box in the PSPN rounds. This means that U passes any number of PSPN rounds, without activating any S-box! On the other hand, for t = 47 and t = 51, there are no t-round differential or linear characteristics that do not activate any S-box.

Theorem 1 implies that for any t that is divisible by 4, there is a huge subspace U of size at least 2^{nt/4} that passes any number of PSPN rounds without activating any S-box.

An especially notable case is Starkad variants with t = 2^k. For such variants, we show that the MDS is essentially an involution.

We obtain Theorems 1 and 2 via an extensive study of properties of Cauchy matrices over binary fields. As Cauchy matrices are widely used (e.g., for error correcting codes, see [RL89]), these linear-algebraic results are of independent interest.

We show that the invariant subspaces can be used to mount a Gröbner-basis preimage attack proposed by Beyne et al. [6, Sec. 6.2], and that for certain choices of the parameters, the resulting attack breaks the security claims of the hash function. On the other hand, our results show that this deficiency can be fixed easily: it is sufficient to choose a value of t that is not divisible by 4 (see Table 2). Furthermore, various other mild changes (such as slightly altering the way in which the sequences \{x_i\}, \{y_j\} used in the construction of the Cauchy matrix are selected) are also sufficient for avoiding the existence of an invariant subspace.

1.3 Practical Impact of Our Results and Subsequent Work

Our results for strong MDS matrices. The designers of Starkad and Poseidon accepted our results and included them in the amended security analysis presented in [GKK+19, updated version, Sec. 5.4.1] and [GKR+21]. In particular, the authors agreed with our claim that as far as statistical attacks are concerned, several full rounds could be replaced by partial rounds without reducing the security claims. Nevertheless, they decided to not reduce the number of full rounds in the amended version, since the full rounds are advantageous over partial rounds also with respect to certain algebraic attacks, such as Gröbner basis attacks.

Our results for weak MDS matrices. Following our results, the designers of Starkad and Poseidon amended the design in such a way that invariant subspaces that pass an infinite number of PSPN rounds would not be possible. To this end, they adopted the amendments we proposed (and in particular, required t to be odd), along with other amendments.

In addition, the STARK-Friendly Hash Challenge [SW20] cryptanalytic committee used our results, alongside other results, to motivate their recommendation to remove Starkad from consideration in the challenge (see [4, Sec. 4]).

Subsequent work. Motivated by our results, Grassi et al. [GRS20] presented a systematic study of linear layers for which the cipher admits an invariant subspace that passes all PSPN rounds for free. The results of the analysis were used to determine the requirements on the MDS matrix used in the amended variant of Starkad and Poseidon [GKK+19, updated version].

1.4 Organization of the Paper

This paper is organized as follows. We briefly describe the HADES construction and its instantiations, Starkad and Poseidon, in Section 2. In Section 3 we present our results on variants of Poseidon. In Section 4 we explore a special class of matrices over binary fields and obtain the linear-algebraic results required for proving Theorems 1 and 2. In Section 5 we present our results on variants of Starkad, and in particular, prove Theorems 1 and 2. We conclude the paper with a discussion and open problems in Section 6.

2 The HADES Construction

In this section we briefly describe the structure of a HADES permutation [GLR+20]. A block cipher / permutation designed according to the HADES strategy employs four types of operations:

1. AddRoundKey, denoted by \text{ARK}(\cdot): a bitwise XOR of a round subkey (or a round constant for unkeyed designs) with the state;
2. Full S-box Layer, denoted by S(\cdot): parallel application of t copies of an identical S-box to the entire state;
3. Partial S-box Layer, denoted by S^*(\cdot): application of a single S-box to a part of the state, while the rest of the state remains unchanged;
4. Mixing Layer, denoted by M(\cdot): multiplication of the entire state by an MDS matrix.

A full round is defined as M \circ S \circ \text{ARK}(\cdot), and a partial round is defined as M \circ S^* \circ \text{ARK}(\cdot). The cipher consists of R_f full rounds, followed by R_P partial rounds, followed by R_f full rounds, where the parameters R_P, R_f are chosen by a complex rule intended mainly to thwart algebraic attacks.

In this paper, we study the Poseidon and Starkad permutations [GKK+19], built according to the HADES design strategy. Poseidon works over a finite field \text{GF}(p), while Starkad works over a binary field \text{GF}(2^n). Starkad uses only the S-box S(x) = x^3, while Poseidon uses also x^{-1} and x^5. For our purposes, the choice of the S-box is not relevant.

The block ciphers are parameterized by R_P, R_f (as in HADES), n—the logarithm of the field size, and t—the number of S-boxes applied in each full round.

The MDS matrix. The design component on which we focus is the MDS matrix used in the linear layer. In the case of a binary field \text{GF}(2^n), the matrix is a so-called Cauchy matrix, constructed as follows. First, a constant r is chosen. Then, one sets up two sequences \{x_i\}, \{y_j\} of length t, by choosing a starting point x_0 and setting

where + denotes integer addition. The t-by-t MDS matrix M is set as

where the inversion is taken in the field \text{GF}(2^n). In all Starkad variants presented in [GKK+19], the parameters x_0, r are set to 0, t, respectively.

3 Improved Security Bounds for Poseidon Permutations

In this section we show that the lower bounds on the number of active S-boxes in a differential or a linear characteristic obtained by the designers of Poseidon, can be improved significantly by taking into consideration active S-boxes in PSPN rounds and lower bounding their number.

In order to lower-bound the number of active S-boxes, we use a generic characteristic search algorithm for PSPNs, presented by Bar-On et al. [BDD+15] at Eurocrypt 2015. For a parameter a, the algorithm allows computing the (provably) minimal number r of rounds such that any r-round differential/linear characteristic must activate at least a + 1 S-boxes.

For t = 2, the algorithm is not needed. Indeed, the MDS property of the matrix guarantees that both S-boxes are active every second round, and hence, the lower bound on the number of active S-boxes in an r-round characteristic is at least r/2. The t = 2 variant of Poseidon has 82 PSPN rounds, and thus, any characteristic over the PSPN rounds has at least 41 active S-boxes. Interestingly, the lower bound obtained by the designers using the wide trail strategy is much lower—only 12 active S-boxes.

For t = 6, which is the main variant proposed by the designers, we were able to run the algorithm up to a = 8, showing that there is no characteristic with at most 8 active S-boxes for 22 rounds. As this variant of Poseidon contains 84 partial rounds, our result implies that any characteristic for the PSPN rounds of Poseidon activates at least 32 S-boxes. This number is higher than the lower bound proved by the designers—28 active S-boxes in the SPN rounds. Combining the bounds, we obtain a provable lower bound of 60 active S-boxes for the entire cipher, more than doubling the bound proved by the designers.

For large values of t (e.g., t = 16), the lower bound that follows from the wide trail strategy becomes much more effective, and on the other hand, the number of PSPN rounds is reduced. As a result, our lower bound for the PSPN rounds is less effective for these variants.

It should be emphasized that for all variants and for all values of a we were able to check, the minimal number of rounds for which any characteristic must activate at least a + 1 S-boxes is t + 2a—matching exactly the generic estimate of [BDD+15]. This suggests that in this respect, the MDS matrices of all Poseidon variants achieve the effect of ‘random’ matrices.

4 A Class of Matrices over a Binary Field and its Properties

In this section we study the properties of a certain class of matrices over commutative rings with characteristic 2 (e.g., binary fields \text{GF}(2^n)). As we will show in Section 5, the MDS matrix used in Starkad belongs to this class (for all variants of Starkad), and thus, the results of this section will allow us to study the security of the middle layer of Starkad constructions.

4.1 Special Matrices and Their Basic Properties

Proof. We have to show that for any k \geq 0, if M_1, M_2 \in R^{2^k \times 2^k} are special matrices, then (1) -M_1, M_1 + M_2, and M_1 \cdot M_2 are special matrices; (2) M_1 and M_2 commute.

The proof is a simple induction on k. For k = 0 the claim is obvious. For k > 0, assume the claim holds for k - 1, and let

be 2^k \times 2^k special matrices. We have M_1 + M_2 = \begin{bmatrix} A+C & B+D \\ B+D & A+C \end{bmatrix}. As by the induction hypothesis, A+C and B+D are special matrices, M_1 + M_2 is a special matrix as well. Similarly, for any c \in R, c \cdot M_1 is a special matrix.

Furthermore, we have

where X = AC + BD and Y = AD + BC. By the induction hypothesis X and Y are special matrices, and thus, M_1 \cdot M_2 is a special matrix as well. To show that special matrices commute, we first observe that they are symmetric, i.e., M_1^T = M_1 (by induction on k). Then M_1 \cdot M_2 = (M_1 \cdot M_2)^T = M_2^T \cdot M_1^T = M_2 \cdot M_1. \square

4.2 Special Matrices over Commutative Rings of Characteristic 2

Proof. By induction on k. For k = 0 the claim is obvious. For k > 0, let M = \begin{bmatrix} A & B \\ B & A \end{bmatrix}. The characteristic polynomial satisfies

Since A + B is a special matrix, the induction hypothesis gives f_M(x) = (x - \lambda(A+B))^{2^k}. For part (2), since \text{char}(R) = 2 and special matrices commute, we have

4.3 Nilpotent Special Matrices over Commutative Rings with Characteristic 2

In this subsection we consider the subring N_k of S_k which consists of the special matrices M that are nilpotent (i.e., N_k = \{M \in S_k : \exists\, t,\; M^t = 0\}). By Proposition 2, N_k has a simple characterization: N_k = \{M \in S_k : \lambda(M) = 0\}. We aim at showing that the product of any k+1 matrices in N_k equals zero.

Proof. By applying Proposition 6 on the sequence of products P_j = \prod_{i=1}^j M_i, we deduce that for all j \geq 1, P_j is a depth-(j-1) zero. In particular, P_{k+1} is a depth-k zero, which means that it is the zero matrix by the definition of zero depth. \square

4.4 Block Matrices with Special Blocks

In this subsection we consider s-by-s block matrices over a commutative ring R with characteristic 2, in which each block is a special 2^k-by-2^k matrix. We aim at showing that the minimal polynomial of any such matrix is of degree at most s(k+1).

Proof. First, we claim that q(M) is a block matrix whose blocks are nilpotent special matrices. Indeed, by Proposition 3, \lambda(q(M)_{i,j}) = (q(M''))_{i,j} = 0, where the last equality holds by the Cayley–Hamilton theorem. Now, by Proposition 7, each block of q(M)^{k+1} is a sum of products of k+1 nilpotent 2^k-by-2^k special matrices, hence each product is the zero matrix, and thus q(M)^{k+1} = 0. \square

4.5 A Stronger Conjectured Bound

We proved this conjecture for s = 2 by a direct computation, and verified it experimentally for many values of t, over various binary fields. In particular, it matches all sizes of invariant subspaces presented in Table 2.

5 A Large Invariant Subspace in the Middle Layer of Starkad Permutations

In this section we apply the results on special matrices obtained in Section 4 to show that for many choices of t, the Starkad permutation admits a huge invariant subspace that allows bypassing any number of PSPN rounds without activating any S-box. We then explain how the invariant subspace can be used to mount a Gröbner basis preimage attack on Starkad, and subsequently show that these invariant subspaces can be easily avoided.

5.1 The Starkad MDS and Special Matrices

Corollary 1. For any t = 2^k, the MDS in Starkad with t S-boxes in each SPN round is a special matrix.

Corollary 2. For any t = 2^k \cdot s, the MDS in Starkad with t S-boxes in each SPN round is an s-by-s block matrix, each of whose blocks is a special matrix.

5.2 A Large Invariant Subspace in Starkad with 4\ell S-Boxes in Each Full Round

Proof of Theorem 1. Let M be a matrix satisfying the assumptions. By Corollary 2, it is an s-by-s block matrix, where each block is a 2^k-by-2^k special matrix. Hence, by Proposition 10, there exists a polynomial q' of degree s(k+1) such that q'(M) = 0. Let

where (X)_1 stands for the top n bits. Clearly, U is a linear subspace of dimension at least s(2^k - (k+1)) = (1 - \frac{k+1}{2^k})t. For any \ell \in \mathbb{N} and x \in U, using polynomial division we write M^\ell = q'(M) \cdot q_0(M) + q_1(M), where \deg(q_1) < s(k+1). Then (M^\ell x)_1 = (q_1(M)x)_1 = 0 since q'(M) = 0 and x \in U. \square

Proof of Theorem 2. By Corollary 1, M is a special matrix. By Proposition 2, M^2 = \lambda(M)^2 \cdot I, where \lambda(M) is the sum of elements in each row. By the construction of the Starkad MDS, these elements are the inverses of \{2^k + i\}_{i=0}^{2^k - 1}. Hence \alpha = (\sum_{j=2^k}^{2^{k+1}-1} j^{-1})^2. The dimension of U is at least t - 2, since it suffices to require x_1 = 0 and (Mx)_1 = 0. \square

5.3 Using the Invariant Subspaces for a Preimage Attack

In [6, Sec. 6.2], Beyne et al. showed that if the linear layer of Starkad or Poseidon was an involution, this could be used to mount a Gröbner basis preimage attack on the scheme. The basic idea behind the attack is simple. Assuming that the linear layer is involutionary, there exists an invariant subspace of dimension t - 2 over the field that passes all PSPN rounds without activating any S-box. Hence, if we restrict ourselves to plaintexts whose intermediate values lie in the invariant subspace, a Gröbner basis attack on the scheme can bypass all PSPN rounds for free. The preimage is then found by representing the full rounds as a system of equations, adding the linear constraints, and solving the resulting system using Gröbner basis methods.

The authors of [BCD+20] conclude that a preimage can be found in time

where the parameters \gamma and \omega are such that the computational cost of computing the row-reduced echelon form of an m-by-n matrix is \gamma m n^\omega.

Application of the attack in our scenario. The preimage attack of [BCD+20] is presented in terms of the multiplicative order of the linear layer. However, it is easy to see that the multiplicative order of the matrix can be replaced by the co-dimension of the invariant subspace that passes the PSPN rounds without activating any S-box. Therefore, the attack can be applied to Starkad, where in the formula c + 2 is replaced with c + d_0, where d_0 is the degree of the minimal polynomial of M. In particular, if we take a variant of Starkad with the binary field \text{GF}(2^{127}) and t any power of 2, then the scheme admits a preimage attack of complexity about 2^{220}, which breaks the 256-bit security bound. We note however that for all actually proposed sets of parameters, the complexity of the preimage attack does not break the security bound.

5.4 The Invariant Subspaces Can Be Avoided Easily

While it is not clear whether the invariant subspaces can be exploited to attack the Starkad hash function, their existence is an undesirable feature. The ‘good news’ are that these subspaces can be easily avoided, by a careful choice of parameters. We present three possible ways:

Choosing the value of t carefully. One possible way is to choose t that is not divisible by 4.

Changing the parameter r. Another possible way is to change the parameter r used in the generation of the MDS matrix. Our experiments indicate that whenever r is not divisible by 4, there is no invariant subspace of the form described above.

Shifting the sequence \{x_i\}. A third possible mild change is shifting the sequence \{x_i\}, namely, taking x_i = x_0 + i - 1 for some x_0 \neq 0.

6 Discussion and Open Problems

6.1 Discussion: PSPN Rounds vs. SPN Rounds

In this paper we showed that the MDS matrix used in HADES constructions significantly affects the security level provided by the cryptosystem. This emphasizes the need of choosing the MDS matrix in the construction carefully, but also gives rise to a more general question regarding the design strategy.

Specifically, we showed in Section 3 that when the MDS matrix is chosen properly (which is the case for all suggested variants of Poseidon), the lower bound on the number of active S-boxes in differential and linear characteristics can be significantly improved by taking into consideration the PSPN rounds. In some of the cases, the lower bound we obtain on the number of active S-boxes in the PSPN rounds is much larger than the lower bound obtained by the designers using the wide-trail strategy.

This gives rise to the question, whether full SPN rounds are ‘cost effective’ compared to PSPN rounds, in scenarios where the complexity is dominated by the number of S-boxes in the construction. The wide trail strategy provides a tight lower bound of t + 1 active S-boxes over two rounds which employ 2t S-boxes in total. For PSPN rounds with a single S-box in each round, the analysis of [BDD+15] suggests that for a ‘good’ MDS, the minimal number of active S-boxes over m rounds (which employ m S-boxes) is \frac{m - t}{2} + 1. While the ratio \frac{t+1}{2t} obtained by SPN rounds is somewhat larger than the ratio \frac{m-t+2}{2m} obtained for PSPN rounds, the asymptotic difference between the ratios is small.

6.2 Open Problems

Finding better ways to exploit the invariant subspace in Starkad. The first open problem arising from this paper is, whether there are more efficient ways to exploit the large invariant subspaces found for variants of Starkad to mount attacks on the schemes.

Optimal bound on the size of the invariant subspace. Another open problem is to prove Conjecture 1—namely, to show that the dimension of the invariant subspace for t = 2^k \cdot s is at least t - 2s. Numerous experiments suggest that the conjecture (which would be tight if proved) indeed holds, and it seems that a proof is not out of reach.

Improved cryptanalysis techniques for PSPN rounds. As was pointed out by the HADES designers, the cryptanalysis tools available for PSPN designs are very scarce. Developing new tools may enable a wider use of PSPN rounds, and further development of designs based on them.

Balancing the number of SPN vs. PSPN rounds in HADES designs. Our results may suggest that one can design more efficient instantiations of HADES by choosing the MDS properly, taking into consideration the middle layer, and changing the balance between SPN and PSPN rounds.

Acknowledgements

The authors are grateful to Tim Beyne, Itai Dinur, Lorenzo Grassi and Christian Rechberger, for helpful discussions and suggestions.

References

• [ARS+15] Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. EUROCRYPT 2015, LNCS 9056, pp. 430–454. Springer (2015).
• [BDD+15] Bar-On, A., Dinur, I., Dunkelman, O., Lallemand, V., Keller, N., Tsaban, B.: Cryptanalysis of SP networks with partial non-linear layers. EUROCRYPT 2015, LNCS 9056, pp. 315–342. Springer (2015).
• [BW91] Becker, T., Weispfenning, V.: Gröbner bases—a computational approach to commutative algebra (1991).
• [BGL+20] Ben-Sasson, E., Goldberg, L., Levit, D.: STARK friendly hash—survey and recommendation. IACR ePrint 2020/948.
• [Bey20] Beyne, T.: Personal communication (2020).
• [BCD+20] Beyne, T., Canteaut, A., Dinur, I., Eichlseder, M., Leander, G., Leurent, G., Naya-Plasencia, M., Perrin, L., Sasaki, Y., Todo, Y., Wiemer, F.: Out of oddity—new cryptanalytic techniques against symmetric primitives optimized for integrity proof systems. CRYPTO 2020, LNCS 12172, pp. 299–328. Springer (2020). [page on this site]
• [DLMW15] Dinur, I., Liu, Y., Meier, W., Wang, Q.: Optimized interpolation attacks on LowMC. ASIACRYPT 2015, LNCS 9453, pp. 535–560. Springer (2015).
• [DEM15] Dobraunig, C., Eichlseder, M., Mendel, F.: Higher-order cryptanalysis of LowMC. ICISC 2015, LNCS 9558, pp. 87–101. Springer (2015).
• [GGNS13] Gérard, B., Grosso, V., Naya-Plasencia, M., Standaert, F.: Block ciphers that are easier to mask: How far can we go? CHES 2013, LNCS 8086, pp. 383–399. Springer (2013).
• [GKK+19] Grassi, L., Kales, D., Khovratovich, D., Roy, A., Rechberger, C., Schofnegger, M.: Starkad and Poseidon: New hash functions for zero knowledge proof systems. IACR ePrint 2019/458. [page on this site]
• [GKR+21] Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. USENIX Security 2021. [page on this site]
• [GLR+20] Grassi, L., Lüftenegger, R., Rechberger, C., Rotaru, D., Schofnegger, M.: On a Generalization of Substitution-Permutation Networks: The HADES Design Strategy. EUROCRYPT 2020, LNCS 12106, pp. 674–704. Springer (2020). [page on this site]
• [GRS20] Grassi, L., Rechberger, C., Schofnegger, M.: Weak linear layers in word-oriented partial SPN and HADES-like ciphers. IACR ePrint 2020/500. [page on this site]
• [NIST01] NIST: Advanced Encryption Standard, FIPS 197 (2001).
• [RL89] Roth, R.M., Lempel, A.: On MDS codes via Cauchy matrices. IEEE Trans. Information Theory 35(6), 1314–1319 (1989).
• [Sil00] Silvester, J.R.: Determinants of block matrices. The Mathematical Gazette 84(501), 460–467 (2000).
• [SW20] StarkWare: STARK-Friendly Hash Challenge (2019–2020).

Appendix A: Detailed Description of the Pattern Search Algorithm

A.1 Checking a Single Pattern

In order to check whether there exists a differential characteristic following a specific pattern, one can use the following algorithm:

Each row of the state corresponds to the coefficients in the linear combination of the t + a variables. On a non-active S-box, we get a linear restriction by the coefficients in the first row. On an active S-box, we replace the first row by a new variable.

A.2 Checking All r-Round Patterns with a Active S-Boxes

We can also iterate over all the patterns of length r with a active S-boxes, using the following simple recursive algorithm:

The function should be called with \text{pattern} = \emptyset, s = 0, a, i = 2, n = t + 2a.