Tim Beyne

Anne Canteaut

Itai Dinur

Maria Eichlseder

Gregor Leander

Gaëtan Leurent

María Naya-Plasencia

Léo Perrin

Yu Sasaki

Yosuke Todo

Friedrich Wiemer

Out of Oddity -New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems

Keywords: Hash functions, integrity proof systems, Integral attacks, GMiMC, HadesMiMC

The security and performance of many integrity proof systems like SNARKs, STARKs and Bulletproofs highly depend on the underlying hash function. For this reason several new proposals have recently been developed. These primitives obviously require an in-depth security evaluation, especially since their implementation constraints have led to less standard design approaches. This work compares the security levels offered by two recent families of such primitives, namely GMiMC and HadesMiMC. We exhibit low-complexity distinguishers against the GMiMC and HadesMiMC permutations for most parameters proposed in recently launched public challenges for STARK-friendly hash functions. In the more concrete setting of the sponge construction corresponding to the practical use in the ZK-STARK protocol, we present a practical collision attack on a round-reduced version of GMiMC and a preimage attack on some instances of HadesMiMC. To achieve those results, we adapt and generalize several cryptographic techniques to fields of odd characteristic.

Introduction

The emergence of cryptographic protocols with advanced functionalities, such as fully homomorphic encryption, multi-party computation and new types of proof systems, has led to a strong demand for new symmetric primitives offering good performance in the context of these specific applications. Indeed, as emphasized by Katz [26] in his invited lecture at CRYPTO 2019, symmetric-key cryptography has an important role to play in the further practical advancement of these applications. However, the standard criteria which govern the design of symmetric primitives are usually not appropriate in the context of these applications. For instance, the cost of the homomorphic evaluation of a symmetric primitive is mainly determined by its multiplicative size and depth [START_REF] Albrecht | Ciphers for MPC and FHE[END_REF]. Similarly, the area of integrity proof systems, like SNARKs, STARKs, Bulletproofs, is asking for symmetric primitives optimized for yet another cost metric. Moreover, the use of hash functions that are defined over finite fields of odd characteristic, in particular over prime fields is desirable in many such applications. One example of such a use case is the zero-knowledge proof system deployed in the Zcash cryptocurrency. Another very interesting example is the ZK-STARK protocol [START_REF] Ben-Sasson | Scalable, transparent, and post-quantum secure computational integrity[END_REF], which is expected to be deployed on top of the Ethereum blockchain within the next year: it uses as a building-block a collision-resistant hash function, and the performance of the proof system highly depends on the number of arithmetic operations required for describing the hash function (see [START_REF] Aly | Design of symmetric-key primitives for advanced cryptographic protocols[END_REF] for details).

Therefore, several new ciphers and hash functions have been proposed in the last five years for these advanced protocols. They include several FHE-friendly symmetric encryption schemes such as LowMC [START_REF] Albrecht | Ciphers for MPC and FHE[END_REF], FLIP [START_REF] Méaux | Towards stream ciphers for efficient FHE with low-noise ciphertexts[END_REF], Kreyvium [START_REF] Canteaut | Stream ciphers: A practical solution for efficient homomorphicciphertext compression[END_REF] and Rasta [START_REF] Dobraunig | Rasta: A cipher with low ANDdepth and few ANDs per bit[END_REF], some MPC-friendly block ciphers such as MiMC [START_REF] Albrecht | MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity[END_REF] and its variants [START_REF] Albrecht | Feistel structures for MPC, and more[END_REF][START_REF] Grassi | Starkad and Poseidon: New hash functions for zero knowledge proof systems[END_REF], and some primitives dedicated to proof systems such as the functions from the Marvellous family, including Jarvis, Friday [START_REF] Ashur | MARVELlous: a STARK-friendly family of cryptographic primitives[END_REF], Vision and Rescue [START_REF] Aly | Design of symmetric-key primitives for advanced cryptographic protocols[END_REF].

However, all these primitives are very innovative constructions and the implementation constraints which govern their designs may have introduced some unexpected weaknesses. This was the case for LowMC, which was broken a few weeks after its publication [START_REF] Dinur | Optimized interpolation attacks on LowMC[END_REF][START_REF] Dobraunig | Higher-order cryptanalysis of LowMC[END_REF][START_REF] Rechberger | Cryptanalysis of low-data instances of full LowMCv2[END_REF]. More recently, a practical attack against Jarvis has been mounted [START_REF] Albrecht | Algebraic cryptanalysis of STARK-friendly designs: Application to MARVELlous and MiMC[END_REF], showing that some of these designs are probably not mature enough for practical applications and require a more in-depth security evaluation. In particular, several of these primitives are defined over an odd prime field, a setting in which most of the classical cryptanalytic tools, and therefore also related security arguments, do not apply directly. This includes linear cryptanalysis and its variants, integral attacks and higher-order differential or cube attacks.

Our contributions. This work analyses the security of two families of such primitives. To be concrete, we focus on the concrete proposals of STARK-friendly hash functions which have been specified in the context of a public competition launched by StarkWare Industries 8 . We aim to compare the security levels offered, for similar parameters, by two families of primitives: GMiMC [START_REF] Albrecht | Feistel structures for MPC, and more[END_REF][START_REF] Albrecht | Feistel structures for MPC, and more[END_REF] and HadesMiMC [START_REF] Grassi | Starkad and Poseidon: New hash functions for zero knowledge proof systems[END_REF][START_REF] Grassi | On a generalization of substitution-permutation networks: The HADES design strategy[END_REF]. More precisely, we evaluate the resistance of these two primitives against several general types of attacks: attacks exploiting differential properties, integral attacks and advanced algebraic attacks. As a result, we present low-complexity distinguishers against the GMiMC and HadesMiMC permutations for most parameters proposed in the challenges. In the more concrete setting of the sponge construction corresponding to the practical use in the ZK-STARK protocol, we describe a collision attack on a round-reduced version of GMiMC and a preimage attack on some instances of HadesMiMC. Our findings for the most efficient variants of the primitives are summarized in Table 1.

From a technical point, our results required to adapt and generalize several cryptanalytic techniques to fields of odd characteristic. In particular, for integral attacks, we demonstrate that instead of using sums over additive subgroups as usually done for ciphers over F n 2 , it is possible to use any multiplicative subgroup of F × q with similar impact. Interestingly, this seems to suggest that finite fields F q with a limited number of multiplicative subgroups might be preferable, i.e. one might want to avoid q -1 being smooth. This implies that the fields which are suitable for implementing FFT may be more vulnerable to integral attacks. We expect that these general insights have applications beyond our concrete cryptanalytic results.

An additional technical contribution of this paper is the use of algebraic techniques for ensuring that transitions of a differential characteristic for a hash function hold for many rounds without paying the typical expensive probabilistic cost. In particular, we exploit the algebraic structure of the hash function to penetrate deep into its state and represent the conditions for the differential transitions as algebraic equations that can be efficiently solved. We refer to these attacks as algebraically controlled differential attacks. Algebraic techniques have been previously used in combination with differential attacks (for example, in the recent cryptanalysis of SHA-1 [START_REF] Stevens | The first collision for full SHA-1[END_REF]). However, unlike prior work, in our setting each differential transition is very expensive to bypass probabilistically. Hence, our attacks are almost entirely algebraic and use dedicated techniques to ensure that the algebraic equations can be efficiently solved.

Organization of the paper. The following section describes the two STARKfriendly primitives considered in the paper and their concrete instances. Section 3 details how integral attacks can be mounted over finite fields of any characteristic. Following this new framework, Section 4 exhibits low-complexity integral distinguishers on the full GMiMC permutation. Several differential attacks on round-reduced GMiMC are then detailed in Section 5, including a practical collision attack on the corresponding hash function. Section 6 presents two attacks on HadesMiMC: a general integral distinguisher covering all but two rounds of the permutation, and a preimage attack on the hash function which applies in the specific case where the MDS matrix defining the linear layer has a low multiplicative order.

STARK-friendly primitives

This paper focuses on two families of primitives, which are recent evolutions of the block cipher MiMC designed by Albrecht et al. in 2016 [START_REF] Albrecht | MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity[END_REF], and offer much more flexibility than the original construction:

-GMiMC, designed by Albrecht et al. [START_REF] Albrecht | Feistel structures for MPC, and more[END_REF][START_REF] Albrecht | Feistel structures for MPC, and more[END_REF] Table 1: Distinguishers on the GMiMC and HadesMiMC permutations and attacks breaking the corresponding sponge hash functions. The variants aiming at 128-bit security operate on t = 12 elements in F q with q = 2 61 + 20 × 2 32 + 1.

The variants aiming at 256-bit security operate on t = 14 elements in F q with q = 2 125 + 266 × 2 64 + 1. The last attack ( * ) only applies when the linear layer has a low multiplicative order. Attacks on full versions are typeset in bold.

-HadesMiMC, proposed by Grassi et al. [START_REF] Grassi | Starkad and Poseidon: New hash functions for zero knowledge proof systems[END_REF][START_REF] Grassi | On a generalization of substitution-permutation networks: The HADES design strategy[END_REF], for which two versions are distinguished depending on the characteristic of the underlying field: Starkad over a field of characteristic 2, and Poseidon over a prime field.

Expected security level

GMiMC and HadesMiMC are two block ciphers but both of them can be turned into permutations by replacing the round-keys by fixed independent and randomly chosen round-constants. Based on these primitives, hash functions are obtained by applying the sponge construction [START_REF] Bertoni | Sponge functions[END_REF][START_REF] Bertoni | On the indifferentiability of the sponge construction[END_REF] depicted in Figure 1 and using the primitive as an inner permutation.

In the following, we extensively use the following notation: the sponge operates on a state composed of t elements in a finite field F q . The main parameters which determine the security level of the sponge construction with respect to generic attacks are its capacity c and the size of the underlying alphabet F q . Namely, a random sponge whose capacity consists of c elements in F q provides π M 0 , . . . , M 7 π M 8 , . . . , M [START_REF] Bertoni | On the indifferentiability of the sponge construction[END_REF] output a generic security level corresponding to c 2 log 2 q queries both for collision and (second)-preimage resistance [START_REF] Bertoni | Sponge functions[END_REF].

The primary cryptanalytic goal is to exhibit collision or preimage attacks on some weakened variants of the hash functions. However, the existence of a property which distinguishes a given cryptographic function from an ideal function of the same size is also commonly considered as a weakness (see e.g. [START_REF] Aumasson | The Hash Function BLAKE. Information Security and Cryptography[END_REF]Page 19] for a discussion). In our context, since our attacks do not make any assumptions about the round-constants in the inner permutations, our distinguishers are related to the known-key model for block ciphers [START_REF] Knudsen | Known-key distinguishers for some block ciphers[END_REF].

While a distinguisher on π cannot always be turned into a distinguisher for the hash function, it invalidates the security arguments provided by the indifferentiability proof of the sponge construction [START_REF] Bertoni | On the indifferentiability of the sponge construction[END_REF]. For this reason, the authors of Keccak advocate following the so-called hermetic sponge strategy [16, Page 13], i.e. using the sponge construction with an inner permutation that should not have any structural distinguisher (other than the existence of a compact description).

Concrete instances

The different members in each of these families are determined by the triple (c, t, q) representing respectively the number of words in the capacity, the number of words in the state and the field size. In the following, when referring to practical examples, we will focus on the values (c, t, q) considered in the Stark-Ware challenges given in Table 2. To each triple (c, t, q) correspond two variants: over a prime field and over a binary field, and the exact values of q are detailed in Table 2. Performance in terms of trace size, proving time, and verification cost, are essential criteria for choosing a STARK-friendly hash function. Implementation results show that, for each family of hash functions, the variant 128-d (for the target 128-bit security) is by far the most efficient [35]. For this reason, some attacks in the paper focus more specifically on this member in the three families, i.e., on sponges whose internal state consists of t = 12 words in a finite field F q Security level log 2 q q (prime) q (binary) of order close to 2 64 and with capacity c = 4. It is also worth noticing that, in terms of performance and suitability, odd prime fields are more STARK-friendly than binary fields for a given size.

Specifications of GMiMC

GMiMC is a family of block ciphers designed by Albrecht et al. in 2019 [START_REF] Albrecht | Feistel structures for MPC, and more[END_REF] based on different types of Feistel networks using x → x 3 over the field corresponding to the branch alphabet as the round function. Among the variants proposed by the designers, we focus on the one chosen in the StarkWare challenges and depicted in Figure 2, namely the variant using an unbalanced Feistel network with an expanding round function, named GMiMC erf . In the whole paper, the rounds (and round constants) are numbered starting from 1, and the branches are numbered from 1 to t where Branch 1 is the leftmost branch. For the sake of simplicity, this particular variant will be called GMiMC. A specificity of GMiMC is that the designers' security claims concern the primitive instantiated over a prime field. They mention that "even if GMiMC can be instantiated over F 2 n , [they] do not provide the number of rounds to guarantee security in this scenario".

In the block cipher setting with a key size equal to n = log 2 q bits, the key schedule is trivial, i.e. the master key is added to the input of the cube function at every round. This very simple key schedule is a major weakness [START_REF] Bonnetain | Collisions on Feistel-MiMC and univariate GMiMC[END_REF]. However, it seems difficult to leverage the underlying property in the hash function setting we are focusing on.

Specifications of HadesMiMC

HadesMiMC is a family of permutations described by Grassi et al. in [START_REF] Grassi | On a generalization of substitution-permutation networks: The HADES design strategy[END_REF] which follows a new design strategy for block ciphers called HADES. The HADES construction aims to decrease the number of Sboxes relative to a traditional Substitution-Permutation Network, while guaranteeing that the cipher still resists all known attacks, including differential and linear cryptanalysis and algebraic attacks. Reducing the number of Sboxes is especially important in many applications and this was traditionally achieved by using a partial substitutionlayer, i.e., an Sbox layer which does not operate on the whole internal state. However, several attacks on this type of constructions, e.g. [START_REF] Bar-On | Cryptanalysis of SP networks with partial non-linear layers[END_REF][START_REF] Dinur | Optimized interpolation attacks on LowMC[END_REF][START_REF] Dobraunig | Higher-order cryptanalysis of LowMC[END_REF][START_REF] Rechberger | Cryptanalysis of low-data instances of full LowMCv2[END_REF] show that it is much more difficult to estimate the security level of these constructions than that of classical SPNs. The basic principle of the HADES construction is then to combine both aspects: the inner rounds in the cipher have a partial Sbox layer to increase the resistance to algebraic attacks at a reduced implementation cost, whereas the outer rounds consist of traditional SPN rounds, with a full Sbox layer. The resistance against statistical attacks is analyzed by removing the inner rounds, while the resistance to algebraic attacks, e.g. the evolution of the algebraic degree over the cipher, involves the inner rounds. HadesMiMC [25, Section 3] is then a keyed permutation following the HADES construction dedicated to MPC applications or to STARK proof systems, where the Sbox is defined by the cube mapping over a finite field and the linear layer L corresponds to a (t × t)-MDS matrix. Two concrete instantiations of HadesMiMC are then detailed by Grassi et al. in [START_REF] Grassi | Starkad and Poseidon: New hash functions for zero knowledge proof systems[END_REF], namely:

-Starkad operates on t elements in a binary field of odd absolute degree (which guarantees that the cube mapping is bijective); -Poseidon operates on t elements in a prime field F p with p mod 3 = 1.

In both cases the partial rounds consist of a single Sbox operating on the last coordinate of the state. For all parameters we consider, the number of full rounds is equal to 8 and the number of partial rounds varies between 40 and 88.

Integral attacks over fields of any characteristic

The notion of integral attacks has been introduced by Knudsen and Wagner [START_REF] Knudsen | Integral cryptanalysis[END_REF] and captures several variants including saturation attacks and higher-order differential attacks. These attacks have been used for cryptanalyzing many ciphers, but to our best knowledge, all of them operate on a binary field. Indeed, the main property behind these attacks is that, for any F : F m 2 → F m 2 and for any affine subspace

V ⊂ F m 2 , x∈V F (x) = 0 when deg F < dim V .
This comes from the fact that the sum of the images by F of all inputs in V corresponds to a value of a derivative of F of order (dim V ) [START_REF] Lai | Higher order derivatives and differential cryptanalysis[END_REF]. It follows that this derivative has degree at most (deg(F )dim V ) and thus vanishes when deg F < dim V . It is then possible to saturate some input bits of F and to use as a distinguishing property the fact that the output bits are balanced, i.e. they sum to zero. The fact that the sum over all x ∈ V of F (x) corresponds to the value of a higher-order derivative does not hold anymore in odd characteristic, and the same technique cannot be applied directly. Higher-order differentials over F q then need to use a generalized notion of differentiation as analyzed in [START_REF] Sălăgean | Higher order differentiation over finite fields with applications to generalising the cube attack[END_REF] (see also [START_REF] Agnesse | Cube attack in finite fields of higher order[END_REF]). However, we can show that for the particular case of saturation attacks, the same technique can be used in the general case of a field F q -even in odd characteristic. Indeed, we can exploit the following result. Proposition 1. For any F :

F q → F q with deg(F ) < q -1, x∈Fq F (x) = 0 .
Proof. The result is due to following well-known property: for any exponent k with 1 ≤ k ≤ q -2,

x∈Fq x k = 0 .
Moreover, when k = 0, we have x∈Fq x 0 = q = 0.

Proposition 1 can be generalized to the multivariate case, i.e. to functions from F k q to F q , which can be expressed as polynomials in the ring

F q [x 1 , . . . , x k ]/ (x q 1 -x 1 , . . . , x q k -x k ) .
Corollary 1. For any F : F t q → F q with deg(F ) < k(q -1) and any affine subspace V ⊆ F t q of dimension at least k, x∈V F (x) = 0 .

Proof. Let V be an affine space of dimension κ ≥ k and A an affine permutation over F t q such that A(V ) = {(y, 0, . . . , 0) | y ∈ F κ q }. Then,

x∈V F (x) = x∈V (F • A -1 )(A(x)) = y1,...,yκ∈Fq
(F • A -1 )(y 1 , . . . , y κ , 0, . . . , 0).

Since deg(F • A -1 ) = deg F < k(q -1), (F • A -1
) consists of monomials of the form y i1 1 y i2 2 . . . y iκ κ with at least one exponent i j < q -1. Then, yj ∈Fq y ij j = 0, implying that y1,...,yκ∈Fq

y i1 1 y i2 2 . . . y iκ κ = 0, which leads to x∈V F (x) = 0.
Based on this observation, a saturation attack with data complexity q k can be mounted whenever the degree of F as a polynomial over F q is strictly less than k(q -1), even if F q is a field of odd characteristic. Now, we generalize the notion of integral distinguishers to multiplicative subgroups using the following property.

Proposition 2. Let G be a multiplicative subgroup of F × q . For any F :

F q → F q such that deg(F ) < |G|, x∈G F (x) -F (0) • |G| = 0 .
This is a strict generalization of Proposition 1, for which |G| = q -1.

Proof. The result is a direct consequence of the following well-known property: for any exponent k with

1 ≤ k ≤ |G| -1, x∈G x k = 0 .
Moreover, when k = 0, we have x∈G x 0 = |G|.

We also note that Corollary 1 can be straightforwardly adapted to multiplicative subgroups. The power of summing over multiplicative subgroups (rather than over the entire field F q ) comes from the fact that if F q contains small multiplicative subgroups (as for the fields used for the concrete instances specified in Table 2), the complexity of the attacks may be fine-tuned and significantly reduced. In the next sections, such attacks will be applied to both GMiMC and HadesMiMC.

4 Integral distinguishers on the full GMiMC

Integral distinguisher on GMiMC

Using Corollary 1, we can exhibit a distinguisher for (3t-4+ log 3 (q-2) ) rounds of GMiMC. A remarkable property is that this distinguisher holds for any finite field. It is obtained by saturating a single branch of the Feistel network and consequently has data complexity q. Indeed, we choose a set of inputs where the (t -2) leftmost branches are inactive, while the rightmost branch is determined by the value of Branch (t -1). More precisely, we consider a set of inputs of the form

X = {(α 1 , . . . , α t-2 , x, f (x)) | x ∈ F q } (1)
where the α i are arbitrary constants in F q and f is defined by

f (x) = -x + t-2 i=1 β i + RC t-1 3 -x -2 t-2 i=1 β i -RC t-1 -RC t
and β 1 , . . . , β t-2 are constant values derived from α 1 , . . . , α t-2 by

β 1 = (α 1 + RC 1 ) 3 and β i+1 = α i+1 + i j=1 β j + RC i+1 3 .
Let us first consider the first (t -2) rounds. We observe that, at Round i, 1 ≤ i ≤ t -2, the output of the Sbox corresponds to β i and is added to all branches except the leftmost branch of the input. It follows that the output of Round (t -2) corresponds to

(x + t-2 i=1 β i , f (x) + t-2 i=1 β i , γ 1 , . . . , γ t-2 )
where (γ 1 , . . . , γ t-2 ) are constants (see Figure 4). Therefore, if x denotes the value of Branch

1, i.e., x = x + t-2 i=1 β i , we have that Branch 2 corresponds to f x - t-2 i=1 β i + t-2 i=1 β i = -(x + RC t-1 ) 3 -x -RC t-1 -RC t .
The inputs of Round t are then

{(-x -RC t -RC t-1 , γ 1 + (x + RC t-1 ) 3 , . . . , γ t-2 + (x + RC t-1 ) 3 , x ) | x ∈ F q }
and the inputs of Round (t + 1) are

{(γ 1 , . . . , γ t-2 , x -(x + RC t-1 ) 3 , -x -RC t -RC t-1 ) | x ∈ F q } .
The following (t -2) rounds do not activate the Sbox, implying that the input set at Round (2t -1) has the form

{(x -(x + RC t-1 ) 3 + δ 1 , -x + δ 2 , δ 3 , . . . , δ t ) | x ∈ F q } (2) RC 1 x 3 RC 2 x 3 RC 3 x 3 RC 4 x 3 RC 5 x 3 RC 6 x 3 RC 7 x 3 α 1 α 2 x f (x) β 1 α 2 + β 1 γ 2 x + β 1 f (x) + β 1 α 1 β 2 x + β 1 + β 2 x f (x) + β 1 + β 2 α 1 + β 2 γ 1 γ 2 Round (t-1) (x + RC 3 ) 3 -x -RC 3 -RC 4 γ 1 + (x + RC 3 ) 3 γ 2 + (x + RC 3 ) 3 x -(x + RC 3 ) 3 γ 1 γ 2 x -(x + RC 3 ) 3 -x -RC 3 -RC 4 Round (t+1) γ 3 γ 2 x -(x + RC 3 ) 3 + γ 3 x -(x + RC 3 ) 3 + δ 1 -x + δ 2 δ 3 δ 4
Round (2t-1) for some fixed values δ 1 , . . . , δ t determined by the constants. Each coordinate of this input word can then be seen as a q-ary polynomial in x of degree at most three. It follows that, after r additional rounds, the set ( 2) is transformed into a set of elements (z 1 , . . . , z t ), whose coordinates have degree at most 3 r+1 . Prop. 1 then implies that all z i are balanced if

3 r+1 ≤ q -2, i.e., if r ≤ log 3 (q -2) -1.
Adding (t -1) rounds. We can add some more rounds by using the following relation over (t -1) rounds of GMiMC.

Proposition 3. Let (x 1 , . . . , x t ) and (y 1 , . . . , y t ) denote the input and output of (t -1) rounds of GMiMC.

t i=2 y i -(t -2)y 1 = t-1 i=1 x i -(t -2)x t . (3)
Proof. Let (x 1 , . . . , x t ) denote the input of Round . It can be observed that, for any i, j ∈ {1, . . . , t -1},

x i = x -1 i+1 + (x j -x -1 j+1 ) and x t = x -1 1 .
It follows that, for any j, 1 ≤ j ≤ (t -1),

t i=1 x i -(t -1)x j = t i=1 x -1 i -(t -1)x -1 j+1 .
By applying this equality (t -1) times, we deduce (3).

From the previous proposition, we deduce that after a total of

R = 3t -4 + log 3 (q -2) rounds, the output (v 1 , . . . , v t ) of GMiMC satisfies t i=2 v i -(t -2)v 1 = t-1 i=1 z i - (t -2)z t ,
which is a polynomial in x of degree at most (q -2). This leads to a distinguisher with complexity q on R rounds, i.e., 70 rounds for the parameters we focus on.

Zero-sum distinguishers on the full permutation

Saturating a single branch. Since we are analyzing a permutation (or a family of permutations parameterized by the round-constants), there is no secret material involved in the computation, implying that a distinguisher can be built from some internal states in the middle of the primitive, not only from inputs and outputs, exactly as in the known-key setting for block ciphers [START_REF] Knudsen | Known-key distinguishers for some block ciphers[END_REF]. This leads to zero-sum distinguishers, which were introduced by Aumasson and Meier [START_REF] Aumasson | Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[END_REF] and exhibited for several hash functions, including SHA-3 [START_REF] Aumasson | Distinguishers for the compression function and output transformation of Hamsi-256[END_REF][START_REF] Boura | Higher-order differential properties of Keccak and Luffa[END_REF].

The previously described distinguisher can be extended by (t -2 + log 3 (q -2) ) rounds backwards. This is realized by choosing the internal states after (t -2 + log 3 (q -2) ) rounds in X , as defined by [START_REF] Agnesse | Cube attack in finite fields of higher order[END_REF]. The inverse of one round of GMiMC is still a round of a Feistel network of the same form and it has degree three over F q . Then, the coordinates (y 1 , . . . , y t ) of the images of the elements in X by r backward rounds can be seen as univariate polynomials in x with degree at most 3 r+1 . Exactly as in the forward direction, after ( log 3 (q -2) -1) rounds, the degree of these polynomials cannot exceed (q -2).

Based on Prop. 3, we can then add (t -1) rounds backwards. Indeed, the input of the first round of the permutation (u 1 , . . . , u t ) is related to the output of Round (t -1), i.e. (y 1 , . . . , y t ), by

t i=2 y i -(t -2)y 1 = t-1 i=1 u i -(t -2)u t ,
and the left-hand term of this equation is a polynomial in x of degree at most (q-2), implying that

t-1 i=1 u i -(t -2)u t sum to zero.
Similarly, we can apply the previously described distinguisher in the forward direction, and deduce that the outputs (v 1 , . . . , v t ) of the permutation after (3t-4 + log 3 (q -2) ) additional rounds are such that

t i=2 v i -(t -2)v 1 sum to zero.
This leads to a distinguisher with complexity q for a total of 4t -6 + 2 log 3 (q -2) rounds, which is higher than the number of rounds proposed in all StarkWare challenges, except in the case where q exceeds the claimed security level (see Table 3).

Saturating two branches. When t ≥ 4, it is possible to exhibit a similar distinguisher on more rounds with complexity q 2 by saturating two branches. In this case, we start from Round m in the middle with a set of internal states

Y = {(α 1 , . . . , α t-4 , x, f (x), g(y), y) | x, y ∈ F q } where f (x) = -x + t-4 i=1 β i + RC m+t-4 3 -x -2 t-4 i=1 β i -RC m+t-4 -RC m+t-3 g(y) = (y + RC m-1 ) 3 -y -RC m-1 -RC m-2
and β 1 , . . . , β t-4 are defined as before by replacing RC i by RC m+i-1 .

Computing forwards. As depicted on Figure 5,the corresponding set at the input of Round (m + t -4) is then of the form

{(x , -(x + RC m+t-4 ) 3 -x -RC m+t-4 -RC m+t-3 , γ 1 (y), . . . , γ t-2 (y)) | x , y ∈ F q }
where (γ 1 , . . . , γ t-2 ) are some values which depend on y only. After two more rounds, we then get some internal states whose (t -2) leftmost branches do not depend on x . It follows that each coordinate of the input of Round (m + 2t -4) is a polynomial in x and y of degree at most three in x . After ( log 3 (q -2) -1) rounds, we get that each coordinate is a polynomial of degree at most (q -2) in x . Then, with the same technique as before, we can add (t -1) rounds and show that the output of the permutation (v 1 , . . . , v t ) is such that the linear combination Computing backwards. Starting from Round m and computing backwards, we get that the input of Round (m -1) is of the form

t-1 i=1 v i -(t -2)v t sums to zero after (3t -6 + log 3 (q -2) ) rounds. RC 1 x 3 RC 2 x 3 RC 3 x 3 RC 4 x 3 RC 5 x 3 RC 6 x 3 RC 7 x 3 δ 1 (x) -y + δ 2 (x) y + (y + RC 3 ) 3 + δ 3 (x) δ 4 (x) δ 4 (x) -y -RC 3 -RC 2 y + (y + RC 3 ) 3 α 1 x f (x) -(y + RC 3 ) 3 y α 1 -(y + RC 3 ) 3 x -(y + RC 3 ) 3 f (x) -(y + RC 3 ) 3 -y -RC 3 -RC 2 (y + RC 3 ) 3 α 1 x f (x) g(y) y β 1 Round m x + β 1 x f (x) + β 1 g(y) + β 1 y + β 1 α 1 (x + RC 5 ) 3 -x -RC 5 -RC 6 γ 1 (y) + (x + RC 5 ) 3 y + β 1 + (x + RC 5 ) 3 α 1 + (x + RC 5 ) 3 x -(x + RC 5 ) 3 γ 1 (y) γ 2 (y) α 1 x -(x + RC 5 ) 3 -x -RC 5 -RC 6
(y, α 1 -(y+RC m-1 ) 3 , . . . , x-(y+RC m-1 ) 3 , f (x)-(y+RC m-1 ) 3 , -y-RC m-1 -RC m-2 )
and the input of Round (m -2) equals

(-y -RC m-1 -RC m-2 , y + (y + RC m-1 ) 3 , α 1 , . . . , x, f (x)) .
Then, the following (t -2) rounds do not activate the Sbox, implying that all the coordinates of the input of Round (mt) are polynomials in x and y of degree at most three in y. We deduce that the input (u 1 , . . . , u t ) of Round (m -2t + 2log 3 (q -2) ) is such that the linear combination t-1 i=1 u i -(t -2)u t sums to zero. This zero-sum distinguisher then covers a total of 5t -8 + 2 log 3 (q -2) rounds, which is detailed in Table 3 for the relevant parameters. Table 3: Number of rounds of GMiMC covered by the zero-sum distinguishers of complexity q and q 2 .

Exploiting integral distinguishers over multiplicative subgroups

A noticeable shortcoming of the integral attacks over F q , as demonstrated by Table 3, is that they do not give any result for primitives over large fields F q (for which log 2 q ≈ 256). However, by exploiting integral distinguishers over multiplicative subgroups of F q (e.g., for the specific choice of q = 2 253 +2 199 +1), we obtain essentially the same results for GMiMC instances with large q as we obtain for instances with small q. For example, in Section 4.1 we derived an integral distinguisher on R = 3t -4 + log 3 (q -2) rounds, with complexity q. By exploiting any multiplicative subgroup of size |G| = 2 s for s ≤ 199 when q = 2 253 + 2 199 + 1, we obtain an integral distinguisher on

R = 3t -4 + log 3 (|G| -1) rounds, with complexity |G| + 1.
Moreover, even for smaller fields, we can fine-tune the size of G to reduce the complexity of the attack. This is relevant especially for cases where an attack with complexity q can reach more rounds than the ones used by the primitive (which is indeed the case, as shown in Table 3). For example, as derived in Section 4.2, we have a zero-sum property for 4t -6 + 2 log 3 (q -2) rounds, with complexity q. For the GMiMC variant with q = 2 61 + 20 × 2 32 + 1 and t = 12, we use a subgroup of size 2 33 • 167 • 211 ≈ 2 48 (which divides q -1), and obtain a zero-sum property for 4t -6 + 2 log 3 (2 48 -1) = 102 rounds, with complexity of about 2 48 (which covers the full permutation).

5 Differential attacks on round-reduced GMiMC

Impossible differential attacks

We present a new impossible differential for (3t -4) rounds, which improves the previous one for (2t -2) rounds presented by the designers [START_REF] Albrecht | Feistel structures for MPC, and more[END_REF]Page 46].

The previous impossible differential exploits the following probability one propagation for (t -1) rounds: (0, . . . , 0, α) → (α, 0, . . . , 0) where α is a nonzero difference. Hence, (0, . . . , 0, α) never propagates to (β, 0, . . . , 0) after 2t -2 rounds for any β. The designers concluded that conservatively 2t rounds are secure when the security level corresponds to the block size n.

We show that (0, . . . , 0, α 1 )

R 3t-4
(β 1 , 0, . . . , 0) is an impossible propagation, where α 1 , β 1 are non-zero differences satisfying α 1 = β 1 . That is, we include t-2 more rounds in the middle compared to the property presented by the designers.

The intuition for why the above differential is impossible is as follows. When (0, . . . , 0, α 1 ) is propagated, the output difference of the cube mapping is 0 for the first t -1 rounds and is unpredictable for the next t/2 -1 rounds. We denote them by α 2 , α 3 , . . . , α t/2 . Similarly, we extend (0, . . . , 0, β 1 ) by t/2 -1 rounds backwards, using the notation β 2 , β 3 , . . . , β t/2 . Here, to be a valid propagation, those differences must be equal in all the branches, which yields a system of t linear equations with 2(t/2 -1) = t -2 variables. By solving the system, we obtain that α 1 = β 1 is a necessary condition to obtain a valid differential propagation. In other words, for any α 1 , β 1 with α 1 = β 1 , the propagation is impossible. A detailed analysis of this property is provided in Appendix A.

A differential distinguisher

The original paper [4, Appendix D] analyzes the resistance of GMiMC against differential attacks. Most notably, the designers exhibit a differential characteristic over (t + 1) rounds with two active Sboxes, with probability 2 -(2n+2) where n = log 2 q and they conjecture that the corresponding differential is optimal. They deduce that

R = 2 + (t + 1) tn 2(n -1)
rounds are sufficient to resist differential cryptanalysis in the sense that the data complexity of the attack exceeds the size of the full codebook. For instance, when t = 12 and n = 61, this corresponds to 93 rounds out of 101.

A better differential. We exhibit another differential, over t rounds, which leads to a much more efficient attack. Let α and α be two differences in F q . Then, the difference (0, . . . , 0, α, α ) propagates through t rounds of the permutation as

(0, . . . , 0, α, α ) R t-2 -→ (α, α , 0 . . . , 0) R -→ (α + β, β, . . . , β, α) R -→ (β + β , . . . , β + β , α + β , α + β) ,
where α S → β denotes the Sbox transition occurring at Round (t-1) and α +β S → β the Sbox transition occurring at Round t.

It follows that, for any possible value of β, we obtain the following t-round differential as soon as β = -β, which occurs with probability 2 -n on average:

(0, . . . , 0, α, α ) R t -→ (0, . . . , 0, α -β, α + β) .
Since this probability does not depend on the choice of α and α , this differential can be iterated several times to cover more rounds.

For instance, when t = 12 and n = 61, the 101 rounds of GMiMC can be decomposed into 8 blocks of t = 12 rounds, followed by 5 rounds. We then get a differential of the form (0, . . . , 0, α, α ) -→ (0, 0, 0, 0, 0, γ, γ , 0, 0, 0, 0, 0) over the full cipher for some unknown γ, γ with probability at least

P = (2 -61 ) 8 = 2 -488
since the characteristic over the last 5 rounds has probability one. This leads to a differential distinguisher over the full permutation with complexity P -1 = 2 488 which is much lower than the size of the full codebook (2 732 ).

It is worth noticing that P is a lower bound on the probability of the 101round differential since we considered pairs following some specific characteristics by fixing the forms of some differences at intermediate rounds. Some additional input pairs may lead to an output difference of the same form but not to these specific intermediate differences.

Improving the complexity of the distinguisher with structures. The data complexity of the previous distinguisher can be improved by using structures of inputs. Here, a structure is a set of 2 2n inputs of the form S c = {(c 1 , . . . , c t-2 , x, y) | x, y ∈ F p }. The difference between any two elements in the same structure has the form (0, . . . , 0, α, α ). It follows that, from any structure, we can construct 2 4n-1 pairs of inputs whose difference conforms with the differential. Then, the number of structures required to obtain P -1 = 2 8n pairs with an appropriate difference is

2 8n-4n+1 = 2 4n+1 ,
leading to an overall data complexity of 2 6n+1 = 2 367 . The time complexity is equal to the data complexity here since the distinguisher consists in identifying the output pairs which coincide on all output words except the two in the middle. This does not require computing all pairs of elements in each structure, but only to store the values π(x), x ∈ S c according to their first coordinates. This differential distinguisher does not lead to an attack with complexity below the target security level. However, this must be considered as an unsuitable property since its complexity is much lower than what we expect for a randomly chosen permutation on a set of size 2 732 .

It is worth noticing that, if we restrict ourselves to distinguishers with complexity below the target security level of 128 bits, then we can use at most 2 128 /2 2n = 2 6 structures. Therefore, we can derive from these structures 2 6+4n-1 i.e. 2 249 pairs of inputs conforming with the differential. These pairs be can used to distinguish 4 blocks of t rounds since the differential has probability at least 2 -244 . Moreover, a valid pair propagates to a differential of the form (γ, γ , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) with probability one over (t -2) rounds, and we can extend it by a few more rounds by considering the number of state words that have the same difference. After another 6 rounds, the pair has a differential of the form (∆, ∆, ∆, ∆, ∆, ∆, * , * , * , * , * , * ), with probability one, where * is an unknown difference that we do not care about. This differential form has a constraint of the size 5n: the left-most six state words have an identical difference. The number of queries to satisfy the same property for a randomly chosen permutation is lower bounded by 2 5n/2 ≈ 2 152. 5 . This implies that we can distinguish 4t + (t -2) + (t -6) = 64 rounds of GMiMC from a randomly chosen permutation with complexity less than 2 128 . Improved distinguisher using three active words. If we consider a differential with only two active words, the biggest structure we can build is of size 2 2n , which limits the advantage of using structures in reducing the cost of the distinguishers.

Let us now consider the following differential: (0, . . . , 0, α, α , α ) As with the previous differential, if β + β + β = 0, which occurs with probability 2 -n on average, we have:

R t-3 -→ (α, α , α , 0 . . . , 0) R -→ (α + β, α + β, β, . . . , β, α) R -→ (α + β + β , β + β , β + β , . . . , β + β , α + β , α ) R -→ (β + β + β , . . . , β + β + β , α + β + β , α + β + β , α + β + β ) ,
(0, . . . , 0, α, α , α ) R t -→ (0, . . . , 0, α -β, α + β + β , α -β ) .
Again, the probability of this transition is independent of the values of α, α and α , so it can be iterated with probability 2 -n .

For this differential, we can build structures of size 2 3n . This will allow us to consider around 2 6n pairs with the required input differential, so we can expect to be able to iterate the characteristic for 6t rounds. The total distinguisher will cover 6t + (t -3) rounds. As for the previous one, we can add 4 more rounds, generating an output state with 8 words having the same difference with a cost of 2 3n , compared to a cost of 2 7n/2 for a random permutation. For GMiMC with t = 12, this allows to distinguish 85 rounds with a cost of 2 3n . By repeating this procedure 2 n times, we can expect t more round to be covered, and distinguish the whole permutation with 101 rounds with a complexity of 2 5n = 2 320 and having 9 words with a zero difference (as we do not need to add the final four rounds).

Let us point out that using four instead of three words would not improve the number of rounds attacked on GMiMC-128-d, as the cost of one structure is already the same as the cost of obtaining the 8 non-zero differences in the output for a random permutation. Nevertheless, in the case of the GMiMC variant 256-b with t = 14, if we use a similar differential with four active words, we can distinguish up to 8t + (t -4) = 122 rounds while finding 10 words with no difference and with a complexity of about 2 4n = 2 500 .

To determine whether further improvements of these differentials are possible, we have searched for other differential characteristics with a Mixed-Integer Linear Programming (MILP) model. We conclude that the previously described characteristics are essentially optimal for the defined search space, and refer Appendix B for details.

Algebraically controlled differential attacks

In this section, we show how to use algebraic techniques to efficiently find inputs that satisfy a given differential characteristic. The basic idea is to represent the initial state of the permutation symbolically by assigning variables to some of its branches, while the remaining branches are assigned constant values. We then compute the permutation symbolically for several rounds. Namely, for each round, we derive a polynomial expression for each branch of the internal state in terms of the allocated variables.

We repeat this process starting from two initial states (representing two inputs to the permutation), perhaps assigning them different variables. We can now represent the difference between the internal states at each round in these two computations using polynomial expressions in the allocated variables. In particular, each differential transition of the given differential characteristic (whose probability is smaller than one) is expressed as a polynomial equation in the variables. Collecting equations for all differential transitions, we obtain a system of polynomial equations, whose solution immediately gives two inputs to the permutation that satisfy the differential characteristic. For this approach to be useful, the equation system has to be efficiently solvable, which generally implies that we cannot allocate too many variables and need to minimize the algebraic degree of the polynomial equations.

Next, we discuss the complexity of solving equation systems of a specific form that we encounter in the remainder of this section. We then demonstrate the basic attack approach with an example and continue with more involved attacks.

Solving polynomial equation systems with few variables. Some of our attacks in the remainder of this section reduce to solving equation systems over F q . When possible, we solved the systems in practice using the MAGMA software. However, it is also important to understand the complexity of our attacks on stronger variants of the cryptosystem, where they become impractical. In this section, we will only consider systems with one or two variables and estimate the complexity of solving such systems below. We note that in Section 6.2 we encounter equation systems with more variables. Solving such equations is more involved and we will have to use a different estimation, which is heuristic (but standard).

Solving a univariate polynomial equation over F q of degree d is done by factoring the polynomial. Asymptotically, the best known algorithm for this problem was published in [START_REF] Kedlaya | Fast modular composition in any characteristic[END_REF] and has complexity of about d 1.5+o (1) bits operations. We note, however, that the o(1) expression in the exponent hides a non-negligible term. Solving two bivariate polynomial equations P 1 (x, y) = 0 and P 2 (x, y) = 0 of total degrees d 1 and d 2 (respectively) can be done by computing the resultant9 of the two polynomials, which is a univariate polynomial in x of degree

d 1 • d 2 .
We then compute the roots of the resultant (by factoring it) and for each such root x, we compute the common roots of P 1 (x, y) and P 2 (x, y) (using a GCD algorithm). In general, the heaviest step in this process is factoring the resultant. Satisfying 3t -2 rounds. We show how to efficiently satisfy 3t -2 rounds of the iterative differential characteristic of Section 5, (0, . . . , 0, µ 0 , µ 0 )

R t-2 -→ (µ 0 , µ 0 , 0 . . . , 0) R -→ (µ 0 + µ 1 , µ 1 , . . . , µ 1 , µ 0 ) R -→ (µ 1 + µ 1 , . . . , µ 1 + µ 1 , µ 0 + µ 1 , µ 0 + µ 1 ),
where we require that µ 1 + µ 1 = 0.

Consider an initial of the permutation of the form

X 0 = (α 1 , . . . , α t-2 , x, f (x)),
where the α i are constants in F q , x is a variable and the function f (x) is described in Section 4 (see ( 1)). Then, as described in Section 4, the internal state at Round (t -2) is described as

X t-2 = (x + t-2 i=1 β i , f (x) + t-2 i=1 β i , γ 1 , . . . , γ t-2
), while the state at Round (2t -2) is described as

X 2t-2 = (x -(x + RC t-1 ) 3 + δ 1 , -x + δ 1 , δ 2 , . . . , δ t ), where x = x + t-2 i=1 β i . Starting from Round (2t -2)
, the algebraic degree of the branches generally grows by a multiplicative factor of 3 per round, namely, the algebraic degree of Round (2t -2 + r) is at most 3 r+1 .

Next, consider another initial state of the permutation of the form

Y 0 = (α 1 , . . . , α t-2 , y, f (y)),
where the initial constants α i are identical to those of X 0 . Note that the initial difference between the states is of the form ∆ 0 = X 0 -Y 0 = (0, . . . , 0, µ 0 (x, y), µ 0 (x, y)).

Then, the state Y 2t-2 after Round (2t -2) is described as

Y 2t-2 = (y -(y + RC t-1 ) 3 + δ 1 , -y + δ 2 , δ 3 , . . . , δ t ).
Therefore, the choice of the initial states of the two inputs, assures that (2t -2) rounds of the differential characteristic are satisfied with probability one. At round 2t, we have

∆ 2t = X 2t -Y 2t = (µ 2 (x, y)+µ 2 (x, y), . . . , µ 2 (x, y)+µ 2 (x, y), µ 1 (x, y)+µ 2 (x, y), µ 1 (x, y)+µ 2 (x, y)),
and we require µ 2 (x, y) + µ 2 (x, y) = 0, which is a polynomial equation of degree 3 2+1 = 27 in the variables x, y. Since we have 2 variables and only one equation in F q , we can set one of the variables to an arbitrary constant and solve a univariate polynomial equation in the other variable. We expect one solution on average, which gives an input pair that satisfies the differential characteristic for 2t rounds. Since the next (t -2) rounds are satisfied with probability one, we can satisfy 3t -2 rounds at the cost of solving a univariate polynomial equation over F q of degree 27 (which has very low complexity).

Satisfying 4t -2 rounds in an inside-out setting. In an inside-out setting, the differential characteristic can be extended from (3t -2) rounds to (4t -2) rounds algebraically, by adding t rounds before the initial state. Indeed, since the initial state is described by polynomials of degree 3, the state at round (-2) can be described by polynomials of degree 27:

∆ -2 =X -2 -Y -2 = (µ -1 (x, y) + µ -1 (x, y), . . , µ -1 (x, y) + µ -1 (x, y), λ 1 (x, y) + µ -1 (x, y), λ 1 (x, y) + µ -1 (x, y)).
Thus, we require µ -1 (x, y) + µ -1 (x, y) = 0 in addition to µ 2 (x, y) + µ 2 (x, y) = 0. This defines a system of two equations of degree 27 in two variables. Any solution with x = y defines a pair of states that satisfies a differential characteristic from round (-t) to round (3t -2), because rounds (-t) to (-2) are satisfied with probability 1. To solve the system, we first divide each equation by (yx) to eliminate trivial solutions with x = y. Then we compute a Gröbner basis of the resulting system. Using the MAGMA software, this can be done in less than one minute on a standard PC (solving the system also has very low complexity by our theoretical estimate). Moreover, this can be extended to a distinguisher on 66 rounds by considering a truncated difference in the input and output. We give an example in Figure 6. load('GMiMC_erf.sage') # https://starkware.co/hash-challenge/ S128d_40 = GMiMCParams(field=F61, r=8, c=4, num_rounds=66) print ("Input diff : "+" ".join(["{:20}".format(u.lift()) for u in y-x])) x = erf_feistel_permutation(x, S128d_40) y = erf_feistel_permutation(y, S128d_40) print ("Output diff: "+" ".join(["{:20}".format(u.lift()) for u in y-x])) Satisfying 4t -4 rounds. If we want to use the differential in a collision attack, we must preserve the value of some initial state words, and we cannot use the inside-out technique. We describe an alternative technique, using a modified differential with four active state words:

(0, . . . , 0, µ 0 , 0 , µ 0 , µ 0 )

R t-4 -→ (µ 0 , µ 0 , µ 0 , µ 0 , 0 . . . , 0) R -→ (µ 0 + µ 1 , µ 0 + µ 1 , µ 0 + µ 1 , µ 1 , . . . , µ 1 , µ 0 ) R -→ (µ 0 + µ 1 + µ 1 , µ 0 + µ 1 + µ 1 , µ 1 + µ 1 , . . . , µ 1 + µ 1 , µ 0 + µ 1 , µ 0 + µ 1 ) R -→ (µ 0 + µ 1 + µ 1 µ 1 , µ 1 + µ 1 + µ 1 , . . . , µ 1 + µ 1 + µ 1 , µ 0 + µ 1 + µ 1 , µ 0 + µ 1 + µ 1 , µ 0 + µ 1 + µ 1 ) R -→ (µ 1 , . . . , µ 1 , µ 0 + µ 1 -µ 1 , µ 0 + µ 1 -µ 1 , µ 0 + µ 1 -µ 1 , µ 0 + µ 1 -µ 1 )
with

µ 1 = µ 1 + µ 1 + µ 1 + µ 1 .
As in Section 5.2, we require that µ 1 = 0. This happens with probability 2 -n , and results in an iterative truncated characteristic (0, . . . , 0, * , * , * , * )

R t -→ (0, . . . , 0, * , * , * , * ).
As in the previous attack, we build an initial state with special relations to control the first t rounds with probability one:

X 0 = (α 1 , . . . , α t-4 , x, f (x), y, f (y)).
This ensures that the state at Round (2t -4) is of the form: X 2t-4 = (x -(x +RC t-1 ) 3 +δ 1 , -x +δ 2 , y -(y +RC t-1 ) 3 +δ 3 , -y +δ 4 , δ 5 , . . . , δ t ).

Instead of considering two different states with this shape (with four unknown in total), we will consider one variable state and one fixed state with (x, y) = (0, 0). When we consider the state at Round (2t), we have

∆ 2t = X 2t -X 2t (0, 0) = (µ 2 , . . . , µ 2 , µ 1 + µ 2 -µ 2 , µ 1 + µ 2 -µ 2 , µ 1 + µ 2 -µ 2 , µ 1 + µ 2 -µ 2 )
Where (µ 1 , µ 1 , µ 1 , µ 1 ) are polynomials of degree 3, 1, 3, and 1 respectively (as seen in X 2t-4 ), and (µ 2 , µ 2 , µ 2 , µ 2 ) are polynomials of degree 9, 27, 81, and 243, with µ 2 = µ 2 + µ 2 + µ 2 + µ 2 . All polynomials have variables x and x , and X 2t (0, 0) is a vector of constants. We now require µ 2 (x, x ) = 0, and we can simplify the state using this assumption:

X 2t = X 2t (0, 0) + (0, . . . , 0, µ 1 -µ 2 , µ 1 -µ 2 , µ 1 -µ 2 , µ 1 + µ 2 + µ 2 + µ 2 ).
We obtain an expression of degree (0, . . . , 0, 9, 27, 81, 81).

When we focus on Round (3t), we can now express the condition of the differential as a polynomial of degree 729. Therefore, we have a system of two equations of degree 243 and 729 in two variables. To estimate the complexity of solving the system, recall that we factor the resultant of these polynomials in time d 1.5+o(1) bit operations. In our case, d = 243 • 729 = 177, 147.

Any solution with (x, y) = (0, 0) defines a state such that (X(x, y), X(0, 0)) satisfies the characteristic up to round (4t -4), because rounds (4t) to (4t -4) are satisfied with probability one.

Extending the differentials. All these attacks can be extended probabilistically by finding about q different input pairs that satisfy the differential characteristic (each pair is found by choosing different constants α i in the initial state). With high probability, one of these input pairs will also satisfy the next differential transitions, and follow the characteristic for t more rounds.

Reduced-round collision attacks

We can build collisions on a reduced number of rounds by using the same ideas as for the previous structural or algebraic differential distinguishers. The additional constraint that we have now compared to distinguishers is that any values that need to be chosen must be assigned to the rate part, i.e. the 8 left-most words in GMiMC-128-d, and the capacity part, i.e. the 4 right-most words in GMiMC-128-d, will be fixed to a known value we cannot choose.

Building collisions with structures. We won't use the 3-word differential but the 2-word one, as using the full 2n structure from the 2-word one already implies a complexity equivalent to that of a generic collision attack. Instead of having t = 12 free rounds at the beginning, we will have only 8, due to the 4 words reserved for the capacity. With a cost of 2 r•n we can then go through r • t rounds maintaining the same differential. Finally, we can freely add (t-2) rounds that preserve the differences in the rate part and, consequently, can finally be cancelled: (0, . . . , 0, α, α , 0, 0, 0, 0)

R t-6 -→ (α, α , 0 . . . , 0) R r•t -→ (β, β , 0 . . . , 0) ,
This differential has a probability of 2 -r•t , and would allow to build collisions up to 3t -6 rounds, so for 30 rounds for GMiMC-128-d. If we use structures we can improve this: if we build a structure of size 2 x , with the cost of the structure we can verify a probability up to 2 -2x . If we choose structures of size 2 3n/2 , we can consider r = 3. This would provide collisions for 4t -6 rounds. For GMiMC-128-d this implies collisions on 42 rounds with a cost of 2 92 , and for GMiMC-256 it implies collisions on 50 rounds with a complexity of 2 187 .

Building collisions with algebraically controlled techniques. To use the algebraically controlled techniques in a collision attack, we must not use any difference in the inner part of the sponge. As noted, in the case of GMiMC-128-d, we have c = 4, therefore, we start from a state X 0 = (α 1 , . . . , α 4 , x, f (x), y, f (y), α 9 , . . . , α 12 ) and we have a characteristic over 4t -4c = 40 rounds. In MAGMA, this takes a few minutes using less than 3GB of RAM. We give an example of a conforming pair in Figure 7, where all the α constants have been set to zero. This attack can be extended to t more probabilistically, with (asymptotic) complexity of q • d 1.5+o (1) bit operations. In our case, d = 177, 147 and we obtain an estimate of about 2 90 if we ignore the o(1) term. load('GMiMC_erf.sage') # https://starkware.co/hash-challenge/ S128d_40 = GMiMCParams(field=F61, r=8, c=4, num_rounds=40)

x = vector(F61, [0, 0, 0, 0, 0, 1265014881285225376, 0, 1323963633845726391, 0, 0, 0, 0]) y = vector(F61, [0, 0, 0, 0, 1687869230625042828, 1678073603247747657, 1246244071391540901, 1919915214622971772, 0, 0, 0, 0]) print ("Input diff : "+" ".join(["{:20}".format(u.lift()) for u in y-x])) x = erf_feistel_permutation(x, S128d_40) y = erf_feistel_permutation(y, S128d_40) print ("Output diff: "+" ".join(["{:20}".format(u.lift()) for u in y-x]))

Attacks on HadesMiMC

This section describes two types of attacks against HadesMiMC, which both exploit the propagation of affine subspaces over the partial rounds. The first one is an integral distinguisher covering all rounds except the first two rounds for most sets of parameters. The second one is a preimage attack on the full function which applies when the MDS matrix defining the linear layer has, up to multiplication by a scalar, a low multiplicative order. It is worth noticing that, while the designers of HadesMiMC do not mention any requirements on this MDS matrix, they provide several suggestions. For Starkad and Poseidon, Cauchy matrices are used [START_REF] Grassi | Starkad and Poseidon: New hash functions for zero knowledge proof systems[END_REF]. In Appendix C , we identify weak instances from this class of matrices. Alternatively, the HadesMiMC authors propose [25, Appendix B] the use of a matrix of the form A × B -1 where both A and B are Vandermonde matrices with generating elements a i and b i . In this case, if a i = b i + r for some r ∈ F q , then the resulting MDS matrix will be an involution for F q of characteristic two [START_REF] Sajadieh | On construction of involutory MDS matrices from Vandermonde matrices in GF(2 q )[END_REF]. Similarly, in characteristic p = 2, one obtains an involution whenever a i = -b i .

Integral distinguishers

In HadesMiMC, the number of rounds has been chosen by the designers in such a way that, when each coordinate of the output is expressed as a polynomial in t variables over F q , then the degree of this polynomial in each input is close to (q -1), which is the behaviour expected for a randomly chosen permutation.

Assuming that the degree grows as 3 r for r rounds (which is an upper bound), log 3 (t(q-1)) rounds are enough to get a polynomial of total degree (q-1)t. For the concrete parameters, i.e. t = 12 and q = 2 61 + 20 × 2 32 + 1 for Poseidon, we get that 41 rounds (out of 48 in total) are necessary to achieve maximal degree. For Starkad with t = 12 and q = 2 63 , 43 rounds (out of 51 in total) are necessary.

An integral property. Our idea to improve upon the trivial bound above by a few partial rounds is to choose a specific subspace of inputs. Indeed, we are going to construct a one-dimensional subspace V such that t -1 partial rounds will map any coset V + v 0 onto a coset of another one-dimensional subspace W . Adding at most log 3 (q -2) rounds (either full or partial), ensures that the conditions of Corollary 1 are satisfied and thus the outputs sum to zero.

V + v 0 R t-1 p -→ W + w 0 deg<q-1 -→ zero sum.
Let us denote by V a linear subspace of internal states after the Sbox layer of the last of the first R f /2 full rounds (see Figure 8). Then, this subspace leads to an affine subspace at the input of the first partial round, which is a coset of L(V ). The following lemma guarantees the existence of a nontrivial vector space L(V ) such that any coset of L(V ) is mapped to a coset of W = L t (V ) after t -1 partial rounds.

Lemma 1. Let F : F t q → F t q denote a permutation obtained from r ≥ 1 partial HadesMiMC rounds instantiated with linear layer L. If L has multiplicative order h up to multiplication by a scaler, then there exists a vector space V with dim V ≥ t -min{h, r} such that F (x + V ) ⊆ F (x) + L r (V ) for all x ∈ F t q .

Proof. Let V = δ t , L T (δ t ), . . . , (L T ) r-1 (δ t ) ⊥ where δ t = (0, . . . , 0, 1). Clearly, dim V satisfies the desired lower bound. It suffices to show that for all x ∈ F t q and v ∈ V ,

F (x + v) = F (x) + L r (v). Let F = R r • • • • • R 1 . Since the last coordinate of any v in V is zero, i.e. v ⊥ δ t , the image of x + V by the partial Sbox layer is a coset of V . It follows that R 1 (x + v) = R 1 (x) + L(v). Similarly, for Round i = 2, . . . , r, it holds that R i (x i + L i-1 (v)) = R i (x i ) + L i (v) if L i-1 (v) ⊥ δ t or equivalently v ⊥ (L ) i-1 (δ t ).
Let us consider any coordinate y of the output of the permutation after adding r additional (partial or full) rounds. When z 0 varies in V , these output words correspond to the images by the additional rounds of the elements z 1 in a coset of W = L t (V ), which we denote by γ +W (see Figure 8). As the polynomial corresponding to the r additional rounds has degree at most 3 r , it then follows using Corollary 1 that z0∈V y(z 0 ) = z1∈γ+W y(z 1 ) = x∈Fq P (x) = 0 , as long as r is at most log 3 (q -2) .

Thus, in total this covers (t -1) + log 3 (q -2) rounds, starting after the first full rounds. For most sets of concrete parameters, this actually exceeds the recommended number of rounds in the forward direction for both Poseidon and Starkad. Furthermore, Lemma 1 implies that if the linear layer L has multiplicative order less than t -1, then the distinguisher covers an arbitrary number of partial rounds. Zero-sum distinguishers over F q . By extending the above-mentioned approach in the backwards we can construct a zero-sum distinguisher with a (slightly) extended number of rounds as depicted on Figure 8. The problem is that contrary to the case of GMiMC, the inverse round function in HadesMiMC is very different from the round function itself, and it has a much higher degree. Indeed, the inverse of the cube mapping over F q is the power function x → x (2q-1)/3 . By using classical bounds on the degree, we cannot guarantee a degree lower than (q -2) for more than a single round backwards.

y z 0 = x u z 0 z 1 = γ + xw y < log 3 (q -2) full-or partial-rounds t -1 partial rounds
However, V being one dimensional allows to overcome one additional layer of Sboxes, and thus one additional round. Namely, as V is a one-dimensional space there exists a vector

v = (v 1 , . . . , v t ) ∈ F t q such that V = {(x v 1 , x v 2 , . . . , x v t ) | x ∈ F q }.
The image of V under the inverse of the full Sbox layer consists of all the vectors in F t q of the form

(x v 1 ) 1/3 , . . . , (x v t ) 1/3 = x 1/3 v 1/3 1 , . . . , v 1/3 t .
As a consequence, this image is again a one-dimensional vector space having the same form, namely U = {x (u 1 , . . . , u t ) | x ∈ F q } where u i = v 1/3 i for all 0 ≤ i < t. It is worth noticing that this particular structure does not propagate over more rounds because of the addition of a round constant. Then, any coordinate at the input of the previous round y is the image of an element z 0 = x u in U by an affine layer, followed by the inverse of Sbox, i.e., by x → x 1/3 (see Figure 8). We can then consider this mapping as a function of x ∈ F q , and express it as a polynomial Q with coefficients in F q . Since the degree of this polynomial is the degree of the inverse Sbox, it does not exceed (q -2). Using the notion from Figure 8, we then have

z0∈V y (z 0 ) = z 0 ∈U y (z 0 ) = x ∈Fq Q(x) = 0 .
For most sets of proposed parameters, this provides a zero-sum distinguisher with data complexity q on for all but the two initial rounds, i.e. for 2 + 4 full rounds (2 at the beginning and 4 at the end), and all partial rounds, as detailed in Table 4. Again, for instantiations of HadesMiMC with a linear layer of multiplicative order less than t -1, the distinguisher covers an arbitrary number of partial rounds.

Finding preimages by linearization of the partial rounds

This section shows that, when the linear layer in HadesMiMC has a low multiplicative order, the propagation of linear subspaces through all partial rounds leads to a much more powerful attack. Indeed, we now show that the existence of perfect linear approximations over the partial rounds of HadesMiMC, as detailed in Lemma 2, can be used to setup a simplified system of equations for finding preimages, leading to a full-round preimage attack.

Lemma 2. Let F : F t q → F t q denote a permutation obtained from r ≥ 1 partial HadesMiMC rounds instantiated with linear layer L and round constants c 1 , . . . , c r . Let V ⊂ F t q be the vector space V = L(δ t ), L 2 (δ t ), . . . , L r (δ t ) ⊥ , where δ t = (0, . . . , 0, 1). Then, for all x ∈ F t q and v ∈ V ,

v • F (x) = v • L r (x) + r i=1 v • L r+1-i (c i ),
where u • v denotes the usual scalar product in F t q . Furthermore, if L has multiplicative order h, then dim V ≥ t -min{h, r}.

Proof. Let F r = R r • R r-1 • • • • • R 1 , where R i denotes the ith partial round of HadesMiMC, namely R i (x) = L • S(x + c i ).
We proceed by induction on r. For r = 1, we have, for any v and x,

v • R 1 (x) = L T (v) • S(x + c 1 ) = L T (v) • (x + c 1 ) = v • L(x) + v • L(c 1 ) if the last coordinate of L T (v) is zero, or equivalently L T (v) • δ t = v • L(δ t ) = 0.
Let us now consider Round r and v ∈ L(δ t ), L 2 (δ t ), . . . , L r (δ t ) ⊥ . For any y ∈ F t q , we have

v • R r (y) = L T (v) • S(y + c r ) = L T (v) • (y + c r ) since L T (v) • δ t = v • L(δ t ) = 0. Letting y = F r-1 (x), it follows that v•F r (x) = L T (v)•F r-1 (x)+L T (v)•c r = L T (v)•L r-1 (x)+ r-1 i=1 L T (v)•L r-i (c i )+L T (v)•c r
where the last equality is deduced from the induction hypothesis using that L T (v) belongs to L(δ t ), . . . , L r-1 (δ t ) ⊥ . Finally, it is easy to see that the dimension of V ⊥ can be upper bounded as dim V ⊥ ≤ min{h, r, t}. Hence, dim V ≥ t -min{h, r}.

Suppose that L is such that the vector space V from Lemma 2 is of dimension d. It will be shown that, if d is sufficiently large, such an instantiation of HadesMiMC is vulnerable to preimage attacks for some choices of the rate and capacity parameters of the sponge construction. In particular, when the MDS matrix L is an involution, we obtain d = t -2.

By Lemma 2, there exists a matrix U 1 ∈ F d×t q such that U 1 F (x) = U 1 (L r (x)+ a) for a known constant a. Indeed, let the rows of U 1 be a basis for V . Furthermore, let U 2 ∈ F (t-d)×t q be a matrix with row space complementary to the row space of U 1 . For each x, it holds that

U 1 y = U 1 (L r (x) + r i=1 L r+1-i (c i )) U 2 y = U 2 F (x). (4)
Consider a HadesMiMC permutation in a sponge construction with rate k and capacity c = t-k. Computing preimages of a one-block message (y 1 , . . . , y k ) ∈ F k q then corresponds to solving the system of equations [F (x IV)] i = y i , i = 1, . . . , k in the unknowns x 1 , . . . , x k .

The idea of the attack is simple: for each guess of U 2 F (x) ∈ F t-d q , replace the equations for the partial rounds by the affine relations (4) and solve the resulting system of equations. In order to ensure that the ideal generated by these equations is zero-dimensional, we should have k ≤ d, which always holds when L is an involution unless c = 1. Note that we focus on the case where the number of output elements is equal to the rate. This is the most challenging setting. Indeed, if the output size is smaller than the rate -as in some of the StarkWare challenges -then the preimage problem will typically have many solutions. This allows the attacker to partially or completely avoid the guessing phase. If further degrees of freedom remain after fixing U 2 F (x) completely, one or more input elements may be fixed to an arbitrary value.

In Appendix D, we show that the total time cost of the attack can be estimated as

2γ (2π) -ω/2 k 2-ω/2 e ωk 3 (ωk+1)(R F -1) q t-d
where ω is the asymptotic exponent of the time complexity of matrix multiplication and γ is such that the cost of computing the row-reduced echelon form of an m × n matrix is γmn ω .

For example, for an involutive L, R F = 8 and an arbitrary number of partial rounds, Figure 9a shows for which choices of q and t an improvement over the generic security of the sponge construction is obtained. The insecure instances are shaded in grey. Note that this domain corresponds to a conservative estimate for the cost of row-echelon reduction, i.e. ω = 3 and γ = 3/2. The cost itself is shown in Figure 9b. We stress that these figures correspond to the most challenging case, i.e. assuming that the hash output is of length k and no shorter.

For the concrete Starkad and Poseidon instances specified in Table 2, we obtain better-than-generic attacks on some variants assuming that the hash output has length c ≤ k. Indeed, provided that c ≤ d/2 = t/2 -1, a sufficiently large number of preimages is likely to exist so that it is no longer necessary to guess U 2 F (x). In addition, input variables may be fixed until only c + td free variables remain. This leads to a computational cost of 2γ (2π) -ω/2 (c+2) 2-ω/2 e ω(c+2) 3 (ω(c+2)+1)(R F -1) . Note that, for these instances, we do not obtain relevant preimage attacks when the output size exceeds t/2-1. (a) Minimum t such that the cost is better than generic for some choice of k.

1 t/3 2t/3 t 0 log 2 q 4 log 2 q k log 2 (cost)
q min{k,c/2} log 2 q ≈ 128 log 2 q ≈ 256 log Table 5: Overview of the computational cost (measured in F q operations) of the preimage attack on different instances of Poseidon and Starkad, assuming an involutive linear layer. These estimates assume that the hash output has length c. For the variants 128-a, 128-b, 128-c, 128-d and 256-a, the attack does not improve over the generic security level of the sponge.

Conclusions

Our analysis of STARK-friendly primitives clearly shows that the concrete instances of GMiMC and HadesMiMC proposed in the StarkWare challenges present several major weaknesses, independently from the choice of the underlying finite field. At a first glance, the third contender involved in the challenges, namely Vision for the binary field and Rescue for the prime fields [START_REF] Aly | Design of symmetric-key primitives for advanced cryptographic protocols[END_REF], seems more resistant to the cryptanalytic techniques we have used against the other two primitives. This seems rather expected since Vision and Rescue follow a more classical SPN construction with full Sbox layers; for similar parameters, they include a larger number of Sboxes which may prevent them from the unsuitable behaviours we have exhibited on the other primitives.

Another important aspect of our work is the extension of higher-order differential and integral attacks to primitives operating on any finite field, even with odd characteristic, while these attacks were previously defined over binary fields only. This points out that the notion of symmetric primitives over a prime field, which has been introduced very recently, needs to be further analyzed in order to get a rigorous assessment on its security. While decades of research have produced efficient cryptanalytic tools and security criteria for primitives defined over F 2 , establishing the right tools to analyze primitives over F q for odd q raises many new and interesting open questions.

A Impossible differential attack on GMiMC

This section contains the technical details related to the impossible differential attack on GMiMC from Section 5.1.

Table 6 shows the differential propagation in the middle t -2 rounds for t = 12. It is valid only when the linear system of equations ( 5) has a nontrivial solution.

α 2 + α 3 + α 4 + α 5 + α 6 = -β 2 -β 3 -β 4 -β 5 α 2 + α 3 + α 4 + α 5 + α 6 = -β 2 -β 3 -β 4 -β 6 α 2 + α 3 + α 4 + α 5 + α 6 = -β 2 -β 3 -β 5 -β 6 α 2 + α 3 + α 4 + α 5 + α 6 = -β 2 -β 4 -β 5 -β 6 α 2 + α 3 + α 4 + α 5 + α 6 = β 1 -β 3 -β 4 -β 5 -β 6 α 2 + α 3 + α 4 + α 5 + α 6 = -β 2 -β 3 -β 4 -β 5 -β 6 α 1 + α 3 + α 4 + α 5 + α 6 = -β 2 -β 3 -β 4 -β 5 -β 6 α 2 + α 4 + α 5 + α 6 = -β 2 -β 3 -β 4 -β 5 -β 6 α 2 + α 3 + α 5 + α 6 = -β 2 -β 3 -β 4 -β 5 -β 6 α 2 + α 3 + α 4 + α 6 = -β 2 -β 3 -β 4 -β 5 -β 6 α 2 + α 3 + α 4 + α 5 = -β 2 -β 3 -β 4 -β 5 -β 6 . (5)
From the 1st and 2nd equations, we get β 5 = β 5 . Similarly, from the 2nd and 3rd, 3rd and 4th, and 5th and 6th equations, we get β 4 = β 5 , β 3 = β 4 , and

β 1 = -β 2 ,
respectively. From the 4th and 5th equations, we get β 1 + β 2β 3 = 0, which implies β 3 = 0. Similarly, we obtain α 5 = α 6 , α 4 = α 5 , α 3 = α 4 , α 1 = α 2 , α 1α 2 + α 3 = 0 by comparing two of the last 6 equations. Finally, by injecting those to the fifth equation, we get α 1 = β 1 , hence the differential is impossible when α 1 = β 1 .

B Optimality of the differential characteristics for GMiMC

To determine whether further improvements are possible compared to the differential characteristics we proposed in Section 5.2, we have searched for other differential characteristics with a Mixed-Integer Linear Programming (MILP) model. Note that our model only lower-bounds the probability of a fixed differential as done for the previously described characteristics and does not take the details of the initial structure or truncation of the output difference into account.

Previously proposed models for differential characteristics usually represent either each state word [?] or each bit [?] with a binary decision variable. Neither is well-suited for GMiMC over prime fields: with a word-wise model, we cannot identify whether two differences are identical and will thus find many invalid characteristics; with a bit-wise model, the model would be unpractically large due to the large state size and number of rounds. We thus model each state word with an integer variable x ∈ [-, ], and addition modulo q simply as x + y = z. The variable x in this relation does not define the value of the difference (except for x = 0), but only captures properties such as equality and additive relations. The bound limits the number of distinct difference values that can be modelled and also defines the helper constant M = 2 .

If x and y are the input and output of an S-box, we only require that x = 0 ⇔ y = 0. One direction x = 0 ⇒ y = 0 of this implication can be encoded using binary helper variables π i :

1 -π 1 M ≤ x ≤ -1 + π 2 M, 0 -π 3 M ≤ y ≤ 0 + π 4 M, 4 i=1 π i ≤ 2 .
Each Sbox is associated with a cost c ∈ {0, 1} (x = 0 ⇒ c = 1) as well as a gain g ∈ {0, 1}, where g = 1 means the output difference y = 0 is arbitrary and thus the transition does not reduce the success probability. We identify these cases by requiring that |y| is larger than any possible sum of defined differences z, bounded by 2 z (with helper variable g z ), including the permutation's input, output, and S-box outputs in the previous r rounds:

-c M ≤ x ≤ c M, y ≥ 2 z -(1-g z )M, y ≥ -2 z -(1-g z )M,
z g z ≥ g (2t+r). Finally, we require nontriviality, with helper variables π x , π x for each input x:

1 -π x M ≤ x ≤ -1 + π x M,
x π x + π x ≤ 2t -1 . The minimization objective is the sum of the cost minus the gain of each Sbox. This corresponds tolog q P , where P is the approximate probability of the differential with fixed input and output difference.

The structured characteristics we describe above yield a cost of k + 1 when the number of rounds is between k t -1 and (k + 1) t -2. We used the MILP model to look at all possible characteristics for up to 3 t rounds. The obtained bounds match our solutions except for k t -1 and k t rounds, where a small and general modification improves the cost to k instead of k + 1. We conclude that the previously described characteristic is essentially optimal with respect to the defined search space.

C Weak Cauchy matrices

The linear layers of Starkad and Poseidon are chosen such that L i,j = 1/(x i + x j + a) where x 1 , . . . , x t are distinct elements of F q [START_REF] Grassi | Starkad and Poseidon: New hash functions for zero knowledge proof systems[END_REF]. The following result shows that, for Starkad instances with t a power of two, there exist weak choices of x 1 , . . . , x t that enable the preimage attack from Section 6.2.

Theorem 1. Let G = {x 1 , . . . , x t } be an additive subgroup of F 2 n of order t and let a ∈ F 2 n \G. For the Cauchy matrix L ∈ F t×t 2 n defined by L i,j = 1/(x i +x j +a), it holds that L 2 = b 2 I with b = t i=1 1/(x i + a).

Proof. Observe that

(L 2 ) i,j = t k=1 1 x i + x k + a × 1 x j + x k + a = x∈a+G 1 x(x + x i + x j )
.

For i = j, the result is clear. It suffices to prove that (L 2 ) i,j = 0 for i = j. Since x i = x j for i = j, we have g = x i + x j ∈ G \ {0}. Finally, it holds that (L 2 ) i,j = D Cost of the preimage attack from Section 6.2

This section provides the details of the computational cost analysis of the preimage attack on HadesMiMC from Section 6.2. In addition, the set of vulnerable parameters is determined.

Recall that the cost of solving the system of equations using Gröbner basis techniques is dominated by two steps:

1. Computing a Gröbner basis with respect to a total degree term order such as the degree reverse lexicographic (degrevlex) order. For standard reduction algorithms such as Faugère's F4 and F5, the time required for this step can be upper bounded by [?]

T gb = O D + k D ω ,
for k variables and with D an upper bound on the degree of the Gröbner basis elements. Here, ω is the asymptotic exponent of the time complexity of matrix multiplication. 2. Converting the degrevlex Gröbner basis to a Gröbner basis with respect to a lexicographic order. For the FGLM algorithm, the cost of this step can be estimated as [?]

T fglm = O(k dim(F q [x 1 , . . . , x k ]/I) ω ),

where I is the ideal corresponding the equations.

The time required to factor the univariate polynomials in the lexicographic Gröbner basis can be assumed to be negligible. Hence, the time cost of the attack is dominated by q t-d (T gb + T fglm ).

To set up a system of preimage equations for HadesMiMC, two diametrical approaches may be considered. In the first strategy, one attempts to minimize the number of variables by setting up a system of high-degree polynomials relating the input and output of the permutation. In the second approach, intermediate variables are introduced at every round, leading to a system of many low-degree equations. The latter strategy is usually preferred, as it leads to a lower degree D. However, a routine calculation shows that reducing the number of variables is more important for the present attack. Hence, we opt for the former approach.

Clearly, the Sbox layer of the first round may be ignored in the analysis. Furthermore, since the HadesMiMC design strategy states that the last linear layer can be omitted, the last round could also be ignored. Nevertheless, this is not the case for Starkad and Poseidon, so we do not take this into account in the analysis in Appendix D.

For each guess of U 2 F (x), the outputs y 1 , . . . y k may be expressed directly as a polynomial in the input (after the first Sbox layer) of degree 3 R F -1 . In general, bounding D is highly nontrivial. However, for regular systems, Macaulay's bound [?,?] yields D ≤ (3 R F -1 -1)k + 1.

Furthermore, small-scale experiments suggest that this bound is tight for this particular system of equations. It is hard to obtain theoretical estimates of dim(F q [x 1 , . . . , x k ]/I), but small-scale experiments suggest that it scales as ∼ 3 k(R F -1) , which is consistent with recent results obtained by Faugère and Perret [?]. Since the FGLM algorithm is able to exploit sparse linear algebra methods [?], it is reasonable to assume that T fglm T gb .

Suppose that 3 R F -1 k. Following the reasoning in [?, §1.3], it holds that

T gb ≤ γ k (D -3 R F -1 + 1) k + D -1 D ω γ k 2 3 R F -1 k + D -1 D ω .
In the above, the parameters γ and ω are such that the computational cost of computing the row-reduced echelon form of an m × n matrix is γmn ω . Stirling's approximation yields the estimate

log k + D -1 D = log k3 R F -1 k ≈ k + k(R F -1) log 3 -log √ 2πk.
It follows that T gb γ (2π) -ω/2 k 2-ω/2 e ωk 3 (ωk+1)(R F -1) , assuming that computing the reduced row-echelon form of an m×n matrix takes time γmn ω . As discussed above, the total computational cost of the attack is then at most 2γ (2π) -ω/2 k 2-ω/2 e ωk 3 (ωk+1)(R F -1) q t-d .

Suppose that 2γ(2π) -ω/2 k 2-ω/2 < 3C for some absolute constant C. For the total cost (6) to be below the security level q min{k,c/2} , it suffices that log 3 C + R F + ωk(log 3 e + R F -1) + (td) log 3 q ≤ min{k, c/2} log 3 q.

Assuming q ≥ 3 ωR F we deduce the following lower bound for k: k ≥ (td) log 3 q + R F + log 3 C log 3 qω (R F + log 3 e -1) .

Since c = tk we also obtain log 3 C + R F + k[ω(log 3 e + R F -1) + (log 3 q)/2] ≤ (dt/2) log 3 q.

From this, we deduce the upper bound k ≤ (dt/2) log 3 q -R Flog 3 C 1/2 log 3 q + ω(R F + log 3 e -1) .

We conclude that the preimage attack improves over the q min{c/2,k} security level whenever (td) log 3 q + R F + log 3 C log 3 qω (R F + log 3 e -1) ≤ k ≤ (dt/2) log 3 q -R Flog 3 C 1/2 log 3 q + ω(R F + log 3 e -1) ,

where C is a constant close to one. If k ≤ 20, one can take C = 3.

Figure 1 :

 1 Figure 1: Sponge construction with inner permutation π, internal state with t = 12 words and capacity c = 4.

Figure 2 :

 2 Figure 2: One round of the GMiMC permutation with t = 12.

Figure 3 :

 3 Figure 3: The HadesMiMC construction with t = 6.

Figure 4 :

 4 Figure 4: First rounds of the integral distinguisher on GMiMC (with t = 4).

Figure 5 :

 5 Figure 5: Middle rounds of the zero-sum distinguisher on GMiMC (with t = 5).

  α + β S → β and α + β + β S → β denote the Sbox transitions occurring at Round (t -2), at Round (t -1) and at Round t.

Figure 6 :

 6 Figure 6: Sagemath code verifying a pair of inputs with a distinguishing property on 66 rounds of GMiMC-128-d: ∆ 0 [10] = ∆ 0[START_REF] Aumasson | The Hash Function BLAKE. Information Security and Cryptography[END_REF] and ∆ 65 [0] = ∆ 65[START_REF] Agnesse | Cube attack in finite fields of higher order[END_REF]

Figure 7 :

 7 Figure 7: Sagemath code verifying a pair of inputs following the characteristic for a 40-rounds collision attack of GMiMC-128-d.

Figure 8 :

 8 Figure 8: Zero-sum distinguisher against Poseidon and Starkad covering (2 + 4) full rounds and all partial rounds.

  2 q ≈ 512 (b) Cost for different values of the rate k with t = 12 and ω = 3.

Figure 9 :

 9 Figure9: Cost analysis of the preimage attack on HadesMiMC with an involutive linear layer and R F = 8. The shaded areas correspond to parameters for which the attack improves over the q min{k,c/2} security level.

A

  special case of Theorem 1 is discussed by Youssef et al. [?, §3.2]. For an extension F 2 (ζ) ⊃ F 2 of degree n, they show that the choice x i = log 2 t j=1 d j ζ j-1 with d 1 , . . . , d log 2 t the binary digits of i -1 results in a Cauchy matrix L such that L 2 = b 2 I for some b ∈ F 2 (ζ).

Table 2 :

 2 Parameters proposed for the permutation and sponge construction.

Table 4 :

 4 Number of rounds of HadesMiMC covered by the zero-sum distinguisher of complexity q.

Table 6 :

 6 Middle t -2 rounds of the new impossible differentials for 3t -4 rounds (t = 12). The first and last 11 rounds are trivial, thus omitted. The notation'α ijk••• ' denotes α i + α j + α k + • • • . 'β ijk••• ' is similarly defined, butbecause it is for the inverse direction, the sign of the term b i is plus for i = 1 and minus for other i. For example, β 13456 denotes +β 1β 3β 4β 5β 6 .

	r ∆S1 ∆S2 ∆S3 ∆S4 ∆S5 ∆S6 ∆S7 ∆S8 ∆S9 ∆S10 ∆S11 ∆S12
	11 α1	0	0	0	0	0	0	0	0	0	0	0
	12 α2	α2	α2	α2	α2	α2	α2	α2	α2	α2	α2	α1
	13 α23	α23	α23	α23	α23	α23	α23	α23	α23	α23	α13	α2
	14 α234 α234 α234 α234 α234 α234 α234 α234 α234 α134 α24	α23
	15 α2345 α2345 α2345 α2345 α2345 α2345 α2345 α2345 α1345 α245 α234 α234
	16 α23456 α23456 α23456 α23456 α23456 α23456 α23456 α13456 α2456 α2356 α2346 α2345
	16 β2345 β2346 β2356 β2456 β13456 β23456 β23456 β23456 β23456 β23456 β23456 β23456
	17 β234 β235 β245 β1345 β2345 β2345 β2345 β2345 β2345 β2345 β2345 β2345
	18 β23	β24 β134 β234 β234 β234 β234 β234 β234 β234 β234 β234
	19 β2	β13	β23	β23	β23	β23	β23	β23	β23	β23	β23	β23
	20 β1	β2	β2	β2	β2	β2	β2	β2	β2	β2	β2	β2
	21 0	0	0	0	0	0	0	0	0	0	0	β1

https://starkware.co/hash-challenge/

The resultant of two polynomials is itself a polynomial in their coefficients, whose zeroes coincide with the common roots of the two polynomials.

Acknowledgements. We thank Nathan Keller for pointing out an error in Section 6.2 of an earlier version of this paper. This research has received funding from StarkWare Industries and the Ethereum Foundation, as part of the process of selecting a STARK-friendly hash function. Tim Beyne is supported by a PhD Fellowship from the Research Foundation -Flanders (FWO). Itai Dinur is supported by the Israeli Science Foundation through grant no. 573/16. Part of this project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreements no. 714294 "QUASYModo", no. 757731 "LightCrypt", and no. 681402 "SOPHIA"). This work was partially supported by the German Federal Ministry of Education and Research (BMBF, project iBlockchain -16KIS0901K) and by DFG under Germany's Excellence Strategy -EXC 2092 CASA -390781972.