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

Abstract

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.

Keywords. Hash functions · integrity proof systems · Integral attacks · GMiMC · HadesMiMC.

1 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 [Kat19] 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 [ARS+15]. 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 [BBHR18], 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 [Aly+19] 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 [ARS+15], FLIP [Mea+16], Kreyvium [Can+18] and Rasta [Dob+18], some MPC-friendly block ciphers such as MiMC [AGR+16] and its variants [Alb+19b,GKK+19], and some primitives dedicated to proof systems such as the functions from the Marvellous family, including Jarvis, Friday [AD18], Vision and Rescue [Aly+19].

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 [DLMW15,DEM16,Rec+18]. More recently, a practical attack against Jarvis has been mounted [Alb+19a], 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. We aim to compare the security levels offered, for similar parameters, by two families of primitives: GMiMC [4,5] and HadesMiMC [28,29]. 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 \mathbb{F}_2^n, it is possible to use any multiplicative subgroup of \mathbb{F}_q^{\times} with similar impact. Interestingly, this seems to suggest that finite fields \mathbb{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 [Ste+17]). 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 STARK-friendly 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.

2 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 [AGR+16], and offer much more flexibility than the original construction:

• GMiMC, designed by Albrecht et al. [4,5]
• HadesMiMC, proposed by Grassi et al. [28,29], 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.

2.1 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 [16,17] 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 \mathbb{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 \mathbb{F}_q. Namely, a random sponge whose capacity consists of c elements in \mathbb{F}_q provides a generic security level corresponding to \frac{c}{2} \log_2 q queries both for collision and (second)-preimage resistance [Ber+07].

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. [12, 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 [KR07].

While a distinguisher on \pi 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 [Ber+08]. For this reason, the authors of Keccak advocate following the so-called hermetic sponge strategy [18, 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).

2.2 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.

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.

2.3 Specifications of GMiMC

GMiMC is a family of block ciphers designed by Albrecht et al. in 2019 [Alb+19b] based on different types of Feistel networks using x \mapsto 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, namely the variant using an unbalanced Feistel network with an expanding round function, named \mathsf{GMiMC}_{\mathsf{erf}}. 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 \mathbb{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 [Bon19]. However, it seems difficult to leverage the underlying property in the hash function setting we are focusing on.

2.4 Specifications of HadesMiMC

HadesMiMC is a family of permutations described by Grassi et al. in [GLR+20] which follows a new design strategy for block ciphers called HADES. The HADES construction aims to decrease the number of S-boxes 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 S-boxes is especially important in many applications and this was traditionally achieved by using a partial substitution layer, i.e., an S-box layer which does not operate on the whole internal state. However, several attacks on this type of constructions, e.g. [13,22,24,38] 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 S-box 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 S-box 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 [29, Section 3] is then a keyed permutation following the HADES construction dedicated to MPC applications or to STARK proof systems, where the S-box is defined by the cube mapping over a finite field and the linear layer L corresponds to a (t \times t)-MDS matrix. Two concrete instantiations of HadesMiMC are then detailed by Grassi et al. in [GKK+19]:

• 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 \mathbb{F}_p with p \bmod 3 \neq 1.

In both cases the partial rounds consist of a single S-box 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.

3 Integral Attacks over Fields of Any Characteristic

The notion of integral attacks has been introduced by Knudsen and Wagner [KW02] 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 : \mathbb{F}_2^m \to \mathbb{F}_2^m and for any affine subspace V \subset \mathbb{F}_2^m,

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) [Lai94]. The fact that the sum over all x \in 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 \mathbb{F}_q then need to use a generalized notion of differentiation as analyzed in [Sal+17] (see also [AP11]). 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 \mathbb{F}_q – even in odd characteristic. Indeed, we can exploit the following result.

Proof. The result is due to the following well-known property: for any exponent k with 1 \le k \le q-2,

Moreover, when k = 0, we have \sum_{x \in \mathbb{F}_q} x^0 = q = 0.

Proposition 1 can be generalized to the multivariate case, i.e. to functions from \mathbb{F}_q^k to \mathbb{F}_q, which can be expressed as polynomials in the ring

Proof. Let V be an affine space of dimension \kappa \geq k and A an affine permutation over \mathbb{F}_q^t such that A(V) = \{(y, 0, \dots, 0) \mid y \in \mathbb{F}_q^{\kappa}\}. Then,

Since \deg(F \circ A^{-1}) = \deg F < k(q-1), (F \circ A^{-1}) consists of monomials of the form y_1^{i_1} y_2^{i_2} \dots y_{\kappa}^{i_{\kappa}} with at least one exponent i_j < q-1. Then, \sum_{y_j \in \mathbb{F}_q} y_j^{i_j} = 0, implying that

which leads to \sum_{x \in 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 \mathbb{F}_q is strictly less than k(q-1), even if \mathbb{F}_q is a field of odd characteristic.

Now, we generalize the notion of integral distinguishers to multiplicative subgroups using the following property.

Proof. The result is a direct consequence of the following well-known property: for any exponent k with 1 \le k \le |\mathbb{G}| - 1,

Moreover, when k = 0, we have \sum_{x \in \mathbb{G}} x^0 = |\mathbb{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 \mathbb{F}_q) comes from the fact that if \mathbb{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

4.1 Integral Distinguisher on GMiMC

Using Corollary 1, we exhibit a distinguisher for (3t-4+\lfloor\log_3(q-2)\rfloor) rounds of GMiMC, holding for any finite field with data complexity q. We consider inputs

where f is defined by

and \beta_1 = (\alpha_1 + \mathsf{RC}_1)^3, \beta_{i+1} = (\alpha_{i+1} + \sum_{j=1}^i \beta_j + \mathsf{RC}_{i+1})^3. After (t-2) rounds, coordinates become degree 3^{r+1} polynomials after r additional rounds. Adding (t-1) rounds via Proposition 3 gives R = 3t - 4 + \lfloor \log_3(q-2) \rfloor rounds (70 for the main parameters).

4.2 Zero-Sum Distinguishers on the Full Permutation

Single branch. In the known-key setting [KR07], the distinguisher extends to 4t - 6 + 2\lfloor\log_3(q-2)\rfloor rounds. Two branches. For t \geq 4, complexity q^2 covers 5t - 8 + 2\lfloor\log_3(q-2)\rfloor rounds.

4.3 Exploiting Multiplicative Subgroups

For q = 2^{61} + 20 \times 2^{32} + 1, t = 12, a subgroup of size \approx 2^{48} gives a zero-sum on 102 rounds (full permutation) at complexity \approx 2^{48}.

5 Differential Attacks on Round-Reduced GMiMC

5.1 Impossible Differential Attacks

We show (0, \ldots, 0, \alpha_1) \not\to (\beta_1, 0, \ldots, 0) is impossible over 3t-4 rounds when \alpha_1 \neq \beta_1, improving the (2t-2)-round result [Alb+19c]. See Appendix A.

5.2 A Differential Distinguisher

The t-round differential (0, \ldots, 0, \alpha, \alpha') \xrightarrow{\mathcal{R}^t} (0,\ldots,0,\alpha-\beta,\alpha'+\beta) holds when \beta' = -\beta (probability 2^{-n}). Iterating 8 times for t=12, n=61 gives probability 2^{-488}. Using structures reduces data complexity to 2^{367}. Three active words distinguish the full 101 rounds at 2^{320}.

5.3 Algebraically Controlled Differential Attacks

Representing the state symbolically: 3t-2 rounds via a degree-27 univariate equation; 4t-2 rounds (inside-out) via two degree-27 bivariate equations (under 1 minute in MAGMA); 4t-4 rounds via degrees 243 and 729. All extend by t rounds at cost q.

5.4 Reduced-Round Collision Attacks

Structures: collisions on 4t-6 rounds — 42 rounds at 2^{92} (GMiMC-128-d), 50 rounds at 2^{187} (GMiMC-256). Algebraic: practical collision on 40 rounds, extensible to 52 rounds at \approx 2^{90}.

6 Attacks on HadesMiMC

6.1 Integral Distinguishers

This covers (t-1) + \lfloor\log_3(q-2)\rfloor rounds. The backwards extension gives a zero-sum on all but the first two rounds.

6.2 Finding Preimages by Linearization

Guessing U_2 F(x) and solving via Gröbner bases gives total cost

7 Conclusions

The concrete instances of GMiMC and HadesMiMC present major weaknesses. Vision/Rescue [Aly+19] appears more resistant due to full S-box layers. The extension of integral attacks to odd characteristic raises many open questions.

Acknowledgements. Funding from StarkWare Industries and the Ethereum Foundation. Tim Beyne (FWO), Itai Dinur (ISF grant 573/16). ERC grants 714294, 757731, 681402.

References

• [Abd+17] Abdelkhalek, A. et al.: MILP modeling for S-boxes. IACR Trans. Symm. Cryptol. 2017(4) (2017)
• [AP11] Agnesse, A., Pedicini, M.: Cube attack in finite fields of higher order. AISC 2011 (2011)
• [Alb+19a] Albrecht, M.R. et al.: Algebraic cryptanalysis of STARK-friendly designs. ASIACRYPT 2019 (2019)
• [Alb+19b] Albrecht, M.R. et al.: Feistel structures for MPC. ESORICS 2019 (2019) [page on this site]
• [Alb+19c] Albrecht, M.R. et al.: Feistel structures for MPC. ePrint 2019/397 (2019) [page on this site]
• [AGR+16] Albrecht, M.R. et al.: MiMC. ASIACRYPT 2016 (2016)
• [ARS+15] Albrecht, M.R. et al.: Ciphers for MPC and FHE. EUROCRYPT 2015 (2015)
• [Aly+19] Aly, A. et al.: Design of symmetric-key primitives. ePrint 2019/426 (2019)
• [AD18] Ashur, T., Dhooghe, S.: MARVELlous. ePrint 2018/1098 (2018)
• [Aum+10] Aumasson, J.P. et al.: Distinguishers for Hamsi-256. ACISP 2010 (2010)
• [AM09] Aumasson, J.P., Meier, W.: Zero-sum distinguishers for reduced Keccak-f. CHES 2009 (2009)
• [Aum+14] Aumasson, J. et al.: The Hash Function BLAKE. Springer (2014)
• [Bar+15] Bar-On, A. et al.: Cryptanalysis of SP networks. EUROCRYPT 2015 (2015)
• [Bar+15b] Bardet, M. et al.: On the complexity of F5. J. Symbolic Computation 70 (2015)
• [BBHR18] Ben-Sasson, E. et al.: Scalable computational integrity. ePrint 2018/046 (2018)
• [Ber+07] Bertoni, G. et al.: Sponge functions. ECRYPT Hash Workshop (2007)
• [Ber+08] Bertoni, G. et al.: On the indifferentiability of the sponge. EUROCRYPT 2008 (2008)
• [Ber+09] Bertoni, G. et al.: Keccak sponge function family. NIST (2009)
• [Bon19] Bonnetain, X.: Collisions on Feistel-MiMC. ePrint 2019/951 (2019) [page on this site]
• [Bou+11] Boura, C. et al.: Higher-order differential properties of Keccak. FSE 2011 (2011)
• [Can+18] Canteaut, A. et al.: Stream ciphers for homomorphic compression. J. Cryptology 31(3) (2018)
• [DLMW15] Dinur, I. et al.: Optimized interpolation attacks on LowMC. ASIACRYPT 2015 (2015)
• [Dob+18] Dobraunig, C. et al.: Rasta. CRYPTO 2018 (2018)
• [DEM16] Dobraunig, C. et al.: Higher-order cryptanalysis of LowMC. ICISC 2015 (2016)
• [FGM+93] Faugère, J.C. et al.: Zero-dimensional Gröbner bases. J. Symbolic Computation 16(4) (1993)
• [FM11] Faugère, J.C., Mou, C.: Change of ordering of Gröbner bases. ISSAC 2011 (2011)
• [FP19] Faugère, J.C., Perret, L.: Algebraic attacks against STARK-friendly ciphers. (2019)
• [GKK+19] Grassi, L. et al.: Starkad and Poseidon. ePrint 2019/458 (2019) [page on this site]
• [GLR+20] Grassi, L. et al.: The HADES design strategy. ePrint 2019/1107 (2019) [page on this site]
• [Kat19] Katz, J.: Secure computation. CRYPTO 2019 invited talk (2019)
• [KU08] Kedlaya, K.S., Umans, C.: Fast modular composition. 49th FOCS (2008)
• [KR07] Knudsen, L.R., Rijmen, V.: Known-key distinguishers. ASIACRYPT 2007 (2007)
• [KW02] Knudsen, L.R., Wagner, D.: Integral cryptanalysis. FSE 2002 (2002)
• [Lai94] Lai, X.: Higher order derivatives and differential cryptanalysis. (1994)
• [Mac02] Macaulay, F.S.: Some formulae in elimination. Proc. London Math. Soc. (1902)
• [Mea+16] Méaux, P. et al.: Stream ciphers for FHE. EUROCRYPT 2016 (2016)
• [Mou+11] Mouha, N. et al.: Differential and linear cryptanalysis using MILP. Inscrypt 2011 (2011)
• [Rec+18] Rechberger, C. et al.: Cryptanalysis of LowMCv2. IACR Trans. Symm. Cryptol. 2018(3) (2018)
• [Saj+12] Sajadieh, M. et al.: Involutory MDS matrices. Designs, Codes and Cryptography 64(3) (2012)
• [Sal+17] Sălăgean, A. et al.: Higher order differentiation over finite fields. Designs, Codes and Cryptography 84(3) (2017)
• [Sta19] StarkWare Industries: Personal communication (2019)
• [Ste+17] Stevens, M. et al.: The first collision for full SHA-1. CRYPTO 2017 (2017)
• [You+96] Youssef, A. et al.: Linear transformations for SPNs. SAC 1996 (1996)

A Impossible Differential Attack on GMiMC

The middle t-2 rounds yield a linear system giving \alpha_1 = \beta_1 as a necessary condition, so the differential is impossible when \alpha_1 \neq \beta_1.

B Optimality of the Differential Characteristics for GMiMC

An MILP model confirms that the proposed characteristics are essentially optimal. Structured characteristics yield cost k+1 for kt-1 to (k+1)t-2 rounds.

C Weak Cauchy Matrices

Proof. For i \neq j, (L^2)_{i,j} = \frac{1}{g}\sum_{x \in a+G}(\frac{1}{x} + \frac{1}{x+g}) = 0 where g = x_i + x_j.

D Cost of the Preimage Attack from Section 6.2

Cost dominated by T_{\mathrm{gb}} = \mathcal{O}(\binom{D+k}{D}^{\omega}) and T_{\text{fglm}} = \mathcal{O}(k\,\dim(\mathbb{F}_q[x_1,\dots,x_k]/\mathcal{I})^{\omega}). Via Stirling:

The attack improves over q^{\min\{c/2,k\}} when