Skip to main content
Table of contents

Algebraic Attacks on ZK-Friendly Hash Functions

A cryptographic deep dive into mathematical attacks on ZK hash functions
Article heading


In our last post, we discussed the design rationale and performance of various ZK-friendly hash functions. These include MiMC, Poseidon, Vision, and Rescue. Although the structures may differ slightly, the underlying concept remains the same: representing the circuit as simple expressions in a large field, it allows efficient proof in terms of both prover execution time and proof size. However, the question remains: Are they truly secure enough to be entrusted with billions of dollars? Let’s dive into the attacks that are particularly effective against ZK-friendly hash functions.

ZK-Friendly Hash Functions

From a high-level perspective, ZK-friendly hash functions are constructed using algebraically simple keyed permutations, called arithmetization-oriented ciphers (AOCs). AOCs are based on either SPN or Feistel networks. Then the permutations are transformed into hash functions using the sponge framework.

(In addition, new permutations have been proposed recently, such as this and this. Both were accepted to CRYPTO 2023. We recommend checking out these papers because they offer significant performance benefits.)

As keyed permutations are structured as multiple rounds of linear and nonlinear operations, the higher the round count, the more secure the hash function but the worse the performance. The designers must consider every possible attack and determine the lower bounds of the round count required to mitigate them.

Maturation Takes Time, Including AOCs

Unfortunately, although the designers carefully consider every possible attack and even add security margins, this is not strong evidence that the structure is safe. As we will see in the examples presented in this post, even if the designer has done their best, there may be new attacks that the designer has not considered. Even peer-reviewed papers published in top conferences can be vulnerable to attacks. For instance, a cipher targeting homomorphic encryption named Chaghri was published in ACM CCS 2022, but an attack was discovered only three months after its publication.

New primitives often become adopted by industry after enough time has passed since their publication. This is independent of the claims made in the original paper and is instead based on the fact that enough people have analyzed them to determine that they are mature enough for practical use.

And from a designer’s perspective, it is important to consider a variety of attacks, including those we will discuss as well as those evolving, to create a robust security design.

In this post, we will discuss algebraic attacks that are particularly efficient against ZK-friendly hash functions and should be taken into consideration, including attacks on the actual proposed primitive. Although you do not extensive ZK knowledge to understand this article, you may check out our latest ZK related blog post if you are a beginner to ZK.

Algebraic Attacks

Before starting to introduce algebraic attacks, we should clarify targets of attacks. The basic secure properties of hash functions are preimage resistance, second-preimage resistance, and collision resistance. Therefore, the attacker’s primary goal is to recover preimages or find collision pairs. However, from the point of view of designers, it is hard to convince someone that a their hash function satisfies security properties.

Meanwhile, ZK hash functions are usually based on the block ciphers. Once the key is fixed, the block cipher becomes a permutation, and these permutations are transformed into hash functions using the sponge framework. It is mathmetically proven that the hash function derived from sponge construction is secure if the permutation is secure. Therefore, instead of demonstrating security for the hash function directly, designers show that a block cipher used inside the sponge construction is secure. Conversely, an attacker would like to show that the block cipher is insecure. For example, if attacker is given plaintext-ciphertext pairs (Pi,Ci)(P_i, C_i) and enable to recover key KK faster than testing all the possible key candidates, it is called key-recovery attack. If the block cipher is insecure, it weakens the designer’s claim that the hash function created from the block cipher is secure.

ZK-friendly hash functions are represented by simple expressions in a large field. In traditional cipher design, the strongest attacks are considered to be statistical attacks called differential and linear cryptanalysis. However, when the field is large, these attacks are not suitable even for a small number of rounds. On the other hand, targeting low arithmetic complexity in attacks is effective.

Interpolation Attack

An interpolation attack is an attack that constructs a polynomial corresponding to the encryption function without knowing the key. Let Ek:FqFqE_k : \mathbb F_q \rightarrow \mathbb F_q be an encryption function. For a fixed key kk, the polynomial Ek(x)E_k(x) can be constructed using Lagrange interpolation --- for example, when we consider two rounds of MiMC, Ek(x)=((x+k)3+k+c1)3+kE_k(x) = ((x+k)^3 + k + c_1)^3 + k. This is a polynomial with degree 99 in terms of xx.

Once the attacker constructs the polynomial Ek(x)E_k(x), then can obatin ciphertext of any plaintext, which has the same effect as knowing the key. Moreover, the attacker may extract key kk from Ek(x)E_k(x) because the coefficients of x8x^8 is 9k9k.

When a polynomial has a degree of dd, the complexity of constructing a Lagrange interpolation polynomial is O(dlogd)O(d\log d). Therefore, the degree of the polynomial used to represent the encryption function should be high enough. For instance, in the MiMC, the round number rr is determined as r=log3qr = \lceil \log_3 q \rceil to ensure that the degree dd attains the maximum degree of q1q-1.

An interpolation attack targets a univariate equation in terms of plaintext. If the plaintext is Fqm\mathbb F_q^m instead of Fq\mathbb F_q, then this attack cannot be applied directly.

GCD Attack

The GCD attack is a key recovery attack that involves computing the GCD. In the GCD attack, the variable is the key KK. We denote the encryption function as E(K,x)E(K, x). For the plaintext-ciphertext pair (x,y)(x, y), we have E(K,x)y=0E(K, x) - y = 0 for K=kK = k. Now, let’s consider two polynomials derived from the two pairs (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2). Both E(K,x1)y1E(K, x_1) - y_1 and E(K,x2)y2E(K, x_2) - y_2 have a common factor of (Kk)(K-k), because E(k,x1)y1=E(k,x2)y2=0E(k, x_1) - y_1 = E(k, x_2) - y_2 = 0. (KK denotes the variable of the key, and kk is the actual value of the key.) This common factor can be determined by computing the GCD.

The complexity of finding the GCD of two polynomials with a degree of dd is O(dlog2d)O(d\log^2d). Therefore, keeping the maximum degree also thwarts this attack. Fortunately, degree grows exponentially as the number of rounds increases, so designers can build defenses against interpolation attacks and GCD attacks without much difficulty.

The GCD attack targets a univariate equation in terms of a key. If the key is in Fqm\mathbb F_q^m instead of Fq\mathbb F_q, then this attack cannot be applied directly.

Invariant Subfields Attack

If the round constants or linear layers are poorly chosen, the ciphertext range may be limited to the subfields. For instance, consider the case where the field is F_2n\mathbb F\_{2^n} and F_2m\mathbb F\_{2^m} is a subfield of F_2n\mathbb{F}\_{2^n}. This implies that mm divides nn. If all the round constants cic_i and the key kk in MiMC are in the subfield F_2m\mathbb F\_{2^m}, an adversary can ensure that Ek(x)F_2mE_k(x) \in \mathbb F\_{2^m} by selecting a plaintext xF_2mx \in \mathbb F\_{2^m}, and this reduces the possible key space 2n2^n to 2m2^m for an attacker --- for example, in MiMC, if the field is F_2128\mathbb F\_{2^{128}} and all round constants cic_i and the key kk are in the F_264\mathbb F\_{2^{64}}. Then, if the attack setting is chosen as a plaintext attack, an attacker may notice that the ciphertext is always in F_264\mathbb F\_{2^{64}} if the plaintext is in F_264\mathbb F\_{2^{64}}. Therefore, an attacker is trying to test only 2642^{64} key candidates instead of 21282^{128}.

This attack can be easily prevented by selecting a random round constant, such as a nothing-up-my-sleeve number. In other words, if an implementation utilizes custom round constants and the rationale behind their selection is undisclosed, there may be vulnerabilities to an invariant subfield attack. Please note that the invariant subfield attack is only effective on binary fields, as prime fields do not have subfields.


Linearization is a technique that represents multivariate equations as linear equations by transforming every monomial as new variables. Consider below the multivariate equations in F_11\mathbb F\_{11}:

x1+x2x3=6x1x2+x1x3+x1=3x2x3+x2=2x1x2+x1+x3=8x1x2+x1x3+x3=7x2x3+x1+x2=2.\begin{aligned} x_1 + x_2x_3 = 6\\ x_1x_2 + x_1x_3 + x_1 = 3\\ x_2x_3 + x_2 = 2\\ x_1x_2 + x_1 + x_3 = 8\\ x_1x_2 + x_1x_3 + x_3 = 7\\ x_2x_3 + x_1 + x_2 = 2 \end{aligned}.

Then, by replacing every monomial to new variables like so,

x1=y1x2=y2x3=y3x1x2=y4x1x3=y5x2x3=y6,\begin{aligned} x_1 = y_1\\ x_2 = y_2\\ x_3 = y_3\\ x_1x_2 = y_4\\ x_1x_3 = y_5\\ x_2x_3 = y_6 \end{aligned},

the equations become a system of linear equations, and they can be easily solvable by Gaussian elimination.

Let nn be a number of unique monomials and mm be a number of equations. To solve given equations using linearization, nmn \leq m must be hold, and the time complexity is O(nω)O(n^\omega), where ω\omega is the minimum exponent for the complexity of matrix multiplication. At least every element in the matrix should be checked before multiplication, lower bounds of ω=2\omega = 2. And the current state-of-the-art algorithm is ω=2.371866\omega = 2.371866. To show a resistance on the linearization, the designer should claim the number of monomials nn is enough that attack complexity is higher than expected security parameters.

For example, for Fq\mathbb F_q with q2128q \approx 2^{128}, let key be k=(k0,k1,k2)Fq3k = (k_0, k_1, k_2) \in \mathbb F_q^3. The designer wants to show this primitive has 128-bits security. If E(k,x)E(k, x) has a max degree 24812^{48}-1, then the number of monomials that can be constructed from the equation is approximately 248×3=21442^{48 \times 3} = 2^{144}, since the degrees of k1,k2,k3k_1, k_2, k_3 vary 00 to 2482^{48}. Then the linearization time complexity is O((2144)ω)O(2288)O((2^{144})^\omega) \geq O(2^{288}), even if we assume that ω=2\omega = 2. Therefore, this primitive is secure against linearization.

Meanwhile, the important question is of whether all the monomials can actually appear. If the expression is sparse and most of the monomials don’t actually occur, then the attack may be possible. Therefore, the designer should claim that most of monomials have appeared theoretically, or experimentally shown using toy parameters.

Gröbner Basis Attack

The Gröbner basis attack is a method for solving a multivariate system by computing the Gröbner basis. Algebraic structures of AOCs allow us to build multivariate equations for key and intermediate values. For example, let’s consider three rounds of MiMC. Let I1I_1 and I2I_2 be the outputs of the first and second S-boxes, respectively.

Then, given plaintext-ciphertext pair (x,y)(x, y), we have a multivariate system:

(x+k)3I1=0(I1+k+c1)3I2=0(I2+k+c2)3ky=0\begin{aligned} (x+k)^3 - I_1 = 0\\ (I_1 + k + c_1)^3 - I_2 = 0\\ (I_2 + k + c_2)^3 - k - y = 0\\ \end{aligned}

The benefits of this multivariate system compared to the univariate system y=(((x+k)3+k+c1)3+k+c2)3+ky = (((x+k)^3 + k + c_1)^3 + k + c_2)^3 + k is that the degree of the equations are much lower. If we can solve this multivariate system for k,I1,I2k, I_1, I_2, then the key is recovered. However, while univariate equations are easily solvable using well-studied algorithms like the Kaltofen-Shoup algorithm if the degree is not that high, there is no efficient algorithm for a multivariate system.

Instead of solving a multivariate system directly, the Gröbner basis of multivariate equations always contains a univariate equation. Once we find the Gröbner basis of the given equations, we obtain a univariate equation that we can solve.

So, what is the Gröbner basis? Understanding the Gröbner basis requires a very high level of mathematical proficiency; therefore, we would like to provide only a brief sketch and omit the details. For a deeper understanding of the technical knowledge, we recommend referring to this paper.

Let’s consider the following multivariate system:

f1:x2y3y1=0f2:xy+xy=0\begin{aligned} f_1 &: x^2 - y^3 - y - 1 = 0\\ f_2 &: -xy + x - y = 0 \end{aligned}

The red (resp. blue) line denotes the zeroes of f_1 (resp. f_2). Image created from WolframAlpha.

We can find another multivariate equation that has the same solutions as the above multivariate system by calculating f=m1f1+m2f2f' = m_1 \cdot f_1 + m_2 \cdot f_2, where m1m_1 and m2m_2 are monomials. For example, we choose m1=ym_1 = y and m2=xm_2 = x. Then f3=m1f1+m2f2=y(x2y3y1)+x(xy+xy)=y4y2y+x2xyf_3 = m_1 \cdot f_1 + m_2 \cdot f_2 = y(x^2 - y^3 - y - 1) + x(-xy + x - y) = -y^4 - y^2 - y + x^2 - xy. It is clear that the solution of the system f1,f2{f_1, f_2} is also the solution of f3f_3.

The Gröbner basis of the given multivariate system is earned by repeating the above calculations appropriately. The Gröbner basis has important characteristics:

  1. The solutions of the system derived from the Gröbner basis are the same as the original multivariate system, and
  2. The Gröbner basis has a univariate equation.

For example, the Gröbner basis of f1,f2{f_1, f_2} is g1=x+y4y3+y2y1,g2=y52y4+2y32y2y+1{g_1 = x + y^4 - y^3 + y^2 - y - 1, g_2 = y^5 - 2y^4 + 2y^3 - 2y^2 - y + 1 }. Since g2g_2 is the univariate equation for yy, yy is recovered from g2g_2. After that, xx is recovered by substituting yy into the obtained solution. The (x,y)(x, y) recovered from the Gröbner basis are also solutions of the original system.

The red (resp. blue) line denotes the zeroes of g1g_1 (resp. g2g_2). Images created from WolframAlpha.

To summarize, the Gröbner basis attack follows the following steps.

  1. Calculate a Gröbner basis.

  2. Identify a univariate polynomial in the given basis and solve for its roots.

  3. Substitute this solution into the Gröbner basis and repeat Step 2.

Let’s consider the time complexity of a Gröbner basis attack. For LL equations with degrees d1,,dLd_1, \dots, d_L over nn variables, we define P(x)=i(1xdi)(1x)n.P(x) = \frac{\prod_i(1-x^{d_i})}{(1-x)^n}.

The degree of regularity DrD_r is defined as the degree of the term with the first nonpositive coefficient in P(x)P(x). The time complexity of calculating a Gröbner basis is estimated as (n+DrDr)ω,\binom{n + D_r}{D_r}^\omega, where nn is the number of variables and DrD_r is the degree of regularity.

This value may not be intuitive, but it can be understood that as the number of variables nn decrease, the number of equations LL increase, and the degree of equations did_i decrease, the system becomes easier to attack.

Attack Examples

Generally, designers consider all of the above attacks in their primitives and choose their round numbers. However, there might be variants for each of these structures, and attackers try to find them to break the primitives.

We will introduce several attacks for the ZK-friendly hash functions. These attacks result in specification changes or design withdrawals.

Interpolation Attacks on MiMC

The first attack is an interpolation attack on MiMC, which was proposed by Chaoyun Li and Bart Preneel (in this paper). We have discussed that for rr rounds of MiMC, the degree dd of the interpolation polynomial is d=3rd = 3^r. An attacker would need at least 3r+13^r+1 pairs to construct this polynomial, with a time complexity of dlogdd\log d. Furthermore, the memory complexity (3r+1)F(3^r + 1) \cdot \|\mathbb F\| represents the total memory required to store each coefficient. MiMC designers claim that if memory complexity is limited, then the number of rounds can be reduced. For example, the author suggests that 38 rounds are sufficient for MiMC-129/129 when the available bytes are limited to 2642^{64} bytes.

However, Li and Preneel found novel attacks that construct partial polynomials. This attack uses only a negligible amount of memory. Although an attacker may have access to 3r+13^r+1 data points, it is impossible to recover the exact polynomial due to memory limitations. However, it is possible to recover only the second-highest term of the interpolated polynomial. (Please refer to section 3.3 in the paper for more information.) Once the second-highest term is recovered from the interpolation, the value of key kk can be determined as the second highest-term, 3rk3^r \cdot k.

This attack indicates that for MiMC-129/129, the full 82 rounds are necessary, even with restrictions on the memory available to the attacker. However, these results do not affect the security claims of the full round MiMC.

There is an another attack against MiMC that aims the full round MiMC using higher-order differential cryptanalysis (read more here). However, this attack is faster than a brute-force attack but requires 2n12^{n-1} chosen data for binary field F_2n\mathbb F\_{2^n}. Therefore, it is not considered as a realistic threat.

Gröbner Basis Attack on Jarvis and Friday

Jarvis and Friday are a ZK-friendly block cipher and a hash function, respectively (read more here). Since Friday is the Merkle-Damgård construction of Jarvis, it is enough to discuss the structures of Jarvis only. Similar to the S-box used in AES, Jarvis employs an inverse S-box as a nonlinear layer. The inverse S-box in the field F_2n\mathbb F\_{2^n} is defined as inv(x)=x2n2inv(x) = x^{2^n-2}. If x=0x = 0, then inv(x)=0inv(x) = 0, and x×inv(x)=1x \times inv(x) = 1 otherwise.

The structure of Jarvis is relatively simple. The round function is composed of the inverse S-box, degree 44 polynomials BB and CC. B(x)B(x) and C(x)C(x) are formed as follows: B(x)=b4x4+b2x2+b1x1+b0x0B(x) = b_4 \cdot x^4 + b_2 \cdot x^2 + b_1 \cdot x^1 + b_0 \cdot x^0 and C(x)=c4x4+c2x2+c1x1+c0x0C(x) = c_4 \cdot x^4 + c_2 \cdot x^2 + c_1 \cdot x^1 + c_0 \cdot x^0. These equations are the same as those used in Vision. Finally, one round of Jarvis can be represented as Jarvis_i(s)=C(B1(inv(s)))+Kr\textsf{Jarvis}\_i(s) = C(B^{-1}(inv(s))) + K_r, where ii represents the round number index.

One round of Jarvis. Image from Jarvis paper

The inverse S-box is also utilized in their key schedule, as shown below.

One round of the key schedule of Jarvis --- C\_{i+1} is a round constant. Image from Jarvis paper.

Even with just one or two inverse S-boxes, it is possible to achieve maximum degrees. Moreover, the cost for SNARK/STARK is relatively low because only verifying x(1xy)=0x(1-xy) = 0 and y(1xy)=0y(1-xy) = 0 is sufficient to check for y=inv(x)y = inv(x). The authors considered several attacks and suggested using 10, 11, 12, and 14 rounds for n=128,160,192,256n = 128, 160, 192, 256, respectively.

However, they did not consider Gröbner basis attacks, and according to this paper, Jarvis is vulnerable to such attacks.

If only the key is treated as a variable, then the equation is univariate. However, the degree is high, making it difficult to recover the key. However, if we add every intermediate value as variables, the system becomes multivariate. With these intermediate values, the degree becomes dramatically lower and allows to mount Gröbner basis attacks.

For each round, xi=B1(inv(s))x_i = B^{-1}(inv(s)) is considered as a variable.

Intermediate state x_i in one round of the encryption path. Image from the attack paper.

The following equations are given:

  • (C(xi)+ki)B(x_i+1)=1(C(x_i) + k_i) \cdot B(x\_{i+1}) = 1: r1r-1 equations of degree 88.
  • B(x1)(p+k0)=1B(x_1) \cdot (p + k_0) = 1: One equation of degree 55.
  • C(xr)=c+krC(x_r) = c + k_r: One equation of degree 44.
  • (k_i+1+ci)ki=1(k\_{i+1}+c_i) \cdot k_i = 1: rr equations of degree 22.

There are 2r+12\cdot r+1 variables x1,,xrx_1, \dots, x_r and k0,,krk_0, \dots, k_r with 2r+12\cdot r+1 equations. Unfortunately this breaks only a reduced round of Jarvis, but with the optimizations suggested in the paper, the number of variables are decreased and succeed in attacking the full round of Jarvis (see section 4.2 of the paper).

From this attack, we realized that with intermediate variables, the expression could be represented in a different form to make the attack possible. In particular, ZK-friendly hash functions often allow expressions to be represented in low degrees if they are well-transformed for efficiency, but care must be taken not to make them vulnerable to a Gröbner basis attack.

Invariant Subspace Attacks on Starkad

Starkad is a ZK-friendly hash function that has the same structure as Poseidon, with the only difference being that Starkad uses binary fields while Poseidon uses prime fields. The authors of Poseidon initially proposed both Starkad and Poseidon, but they have since withdrawn Starkad.

Let’s review the structures of Starkad. The S-box layer in the middle is made of partial S-box layers. This would reduce the R1CS or AET cost.

Construction of Starkad, which is same as Poseidon. R_F = 2 \cdot R_f is the number of the full S-box rounds, and R_P is the number of the partial S-box rounds. Image from the Poseidon paper.

The purpose of the linear layer is to spread local changes onto the entire state. In Starkad, the linear layer is a Cauchy matrix, which is defined by M[i,j]=1xi+yjM[i,j] = \frac{1}{x_i + y_j} for the entries of xi_1im{x_i}\_{1 \leq i \leq m} and yi_1im{y_i}\_{1 \leq i \leq m}, which are pairwise distinct, and xi+yj0x_i + y_j \neq 0, where i1,,mi \in {1, \dots, m} and j1,,mj \in {1, \dots, m}. To generate the sequences xi_1im{x_i}\_{1 \leq i \leq m} and yi_1im{y_i}\_{1 \leq i \leq m}, a constant rr and a starting point x0x_0 are first chosen. The variables xix_i and yiy_i are defined as follows: xi=x0+i1x_i = x_0 + i - 1 and yi=xi+ry_i = x_i + r. The matrix is generated and fixed once, and the designers choose x0=0x_0 = 0 and r=mr = m, where mm represents the number of words in each layer.

However, this MDS matrix allows for large invariant subspaces that pass through the entire middle partial S-box rounds without activating any S-boxes. This renders the middle RPR_P rounds linear, as noted in the attack paper. More precisely, for a certain invariant subspace VV, if ΔV\Delta \in V and xy=Δx \oplus y = \Delta, then F(x)F(y)=L(Δ)F(x) \oplus F(y) = L(\Delta), where FF represents the middle layer and LL represents a linear transformation. This affects security in terms of both statistical and algebraic cryptanalysis.

Although this attack can be mitigated by selecting a value for mm that is not divisible by 4 or by choosing another secure MDS matrix, designers decided to dismiss Starkad and let only Poseidon remain.


In this post, we’ve discussed several algebraic attacks and their usages in the primitives. When designing new AOCs, be sure to consider whether they are secure against attacks like the ones mentioned in this post. This is an active area of research, so it is recommended to periodically check places like the Cryptology ePrint Archive for new attacks.

About us

Zellic specializes in securing emerging technologies. Our security researchers have uncovered vulnerabilities in the most valuable targets, from Fortune 500s to DeFi giants.

Developers, founders, and investors trust our security assessments to ship quickly, confidently, and without critical vulnerabilities. With our background in real-world offensive security research, we find what others miss.

Contact us for an audit that’s better than the rest. Real audits, not rubber stamps.