Algebraic Attacks on ZK-Friendly Hash Functions

Introduction

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 $(P_i, C_i)$ and enable to recover key $K$ 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 $E_k : \mathbb F_q \rightarrow \mathbb F_q$ be an encryption function. For a fixed key $k$, the polynomial $E_k(x)$ can be constructed using Lagrange interpolation --- for example, when we consider two rounds of MiMC, $E_k(x) = ((x+k)^3 + k + c_1)^3 + k$. This is a polynomial with degree $9$ in terms of $x$.

Once the attacker constructs the polynomial $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 $k$ from $E_k(x)$ because the coefficients of $x^8$ is $9k$.

When a polynomial has a degree of $d$, the complexity of constructing a Lagrange interpolation polynomial is $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 $r$ is determined as $r = \lceil \log_3 q \rceil$ to ensure that the degree $d$ attains the maximum degree of $q-1$.

An interpolation attack targets a univariate equation in terms of plaintext. If the plaintext is $\mathbb F_q^m$ instead of $\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 $K$. We denote the encryption function as $E(K, x)$. For the plaintext-ciphertext pair $(x, y)$, we have $E(K, x) - y = 0$ for $K = k$. Now, let’s consider two polynomials derived from the two pairs $(x_1, y_1)$ and $(x_2, y_2)$. Both $E(K, x_1) - y_1$ and $E(K, x_2) - y_2$ have a common factor of $(K-k)$, because $E(k, x_1) - y_1 = E(k, x_2) - y_2 = 0$. ($K$ denotes the variable of the key, and $k$ 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 $d$ is $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 $\mathbb F_q^m$ instead of $\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 $\mathbb F\_{2^n}$ and $\mathbb F\_{2^m}$ is a subfield of $\mathbb{F}\_{2^n}$. This implies that $m$ divides $n$. If all the round constants $c_i$ and the key $k$ in MiMC are in the subfield $\mathbb F\_{2^m}$, an adversary can ensure that $E_k(x) \in \mathbb F\_{2^m}$ by selecting a plaintext $x \in \mathbb F\_{2^m}$, and this reduces the possible key space $2^n$ to $2^m$ for an attacker --- for example, in MiMC, if the field is $\mathbb F\_{2^{128}}$ and all round constants $c_i$ and the key $k$ are in the $\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 $\mathbb F\_{2^{64}}$ if the plaintext is in $\mathbb F\_{2^{64}}$. Therefore, an attacker is trying to test only $2^{64}$ key candidates instead of $2^{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

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

$$\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,

$$\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 $n$ be a number of unique monomials and $m$ be a number of equations. To solve given equations using linearization, $n \leq m$ must be hold, and the time complexity is $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 $\omega = 2$. And the current state-of-the-art↗ algorithm is $\omega = 2.371866$. To show a resistance on the linearization, the designer should claim the number of monomials $n$ is enough that attack complexity is higher than expected security parameters.

For example, for $\mathbb F_q$ with $q \approx 2^{128}$, let key be $k = (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)$ has a max degree $2^{48}-1$, then the number of monomials that can be constructed from the equation is approximately $2^{48 \times 3} = 2^{144}$, since the degrees of $k_1, k_2, k_3$ vary $0$ to $2^{48}$. Then the linearization time complexity is $O((2^{144})^\omega) \geq O(2^{288})$, even if we assume that $\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 $I_1$ and $I_2$ be the outputs of the first and second S-boxes, respectively.

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

$$\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 + 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, 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:

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

We can find another multivariate equation that has the same solutions as the above multivariate system by calculating $f' = m_1 \cdot f_1 + m_2 \cdot f_2$, where $m_1$ and $m_2$ are monomials. For example, we choose $m_1 = y$ and $m_2 = x$. Then $f_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 ${f_1, f_2}$ is also the solution of $f_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 ${f_1, f_2}$ is ${g_1 = x + y^4 - y^3 + y^2 - y - 1, g_2 = y^5 - 2y^4 + 2y^3 - 2y^2 - y + 1 }$. Since $g_2$ is the univariate equation for $y$, $y$ is recovered from $g_2$. After that, $x$ is recovered by substituting $y$ into the obtained solution. The $(x, y)$ recovered from the Gröbner basis are also solutions of the original system.

The red (resp. blue) line denotes the zeroes of $g_1$ (resp. $g_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 $L$ equations with degrees $d_1, \dots, d_L$ over $n$ variables, we define $P(x) = \frac{\prod_i(1-x^{d_i})}{(1-x)^n}.$

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

This value may not be intuitive, but it can be understood that as the number of variables $n$ decrease, the number of equations $L$ increase, and the degree of equations $d_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 $r$ rounds of MiMC, the degree $d$ of the interpolation polynomial is $d = 3^r$. An attacker would need at least $3^r+1$ pairs to construct this polynomial, with a time complexity of $d\log d$. Furthermore, the memory complexity $(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 $2^{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 $3^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 $k$ can be determined as the second highest-term, $3^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 $2^{n-1}$ chosen data for binary field $\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 $\mathbb F\_{2^n}$ is defined as $inv(x) = x^{2^n-2}$. If $x = 0$, then $inv(x) = 0$, and $x \times inv(x) = 1$ otherwise.

The structure of Jarvis is relatively simple. The round function is composed of the inverse S-box, degree $4$ polynomials $B$ and $C$. $B(x)$ and $C(x)$ are formed as follows: $B(x) = b_4 \cdot x^4 + b_2 \cdot x^2 + b_1 \cdot x^1 + b_0 \cdot x^0$ and $C(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 $\textsf{Jarvis}\_i(s) = C(B^{-1}(inv(s))) + K_r$, where $i$ represents the round number index.

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

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(1-xy) = 0$ and $y(1-xy) = 0$ is sufficient to check for $y = inv(x)$. The authors considered several attacks and suggested using 10, 11, 12, and 14 rounds for $n = 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, $x_i = B^{-1}(inv(s))$ is considered as a variable.

The following equations are given:

• $(C(x_i) + k_i) \cdot B(x\_{i+1}) = 1$: $r-1$ equations of degree $8$.
• $B(x_1) \cdot (p + k_0) = 1$: One equation of degree $5$.
• $C(x_r) = c + k_r$: One equation of degree $4$.
• $(k\_{i+1}+c_i) \cdot k_i = 1$: $r$ equations of degree $2$.

There are $2\cdot r+1$ variables $x_1, \dots, x_r$ and $k_0, \dots, k_r$ with $2\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.

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] = \frac{1}{x_i + y_j}$ for the entries of ${x_i}\_{1 \leq i \leq m}$ and ${y_i}\_{1 \leq i \leq m}$, which are pairwise distinct, and $x_i + y_j \neq 0$, where $i \in {1, \dots, m}$ and $j \in {1, \dots, m}$. To generate the sequences ${x_i}\_{1 \leq i \leq m}$ and ${y_i}\_{1 \leq i \leq m}$, a constant $r$ and a starting point $x_0$ are first chosen. The variables $x_i$ and $y_i$ are defined as follows: $x_i = x_0 + i - 1$ and $y_i = x_i + r$. The matrix is generated and fixed once, and the designers choose $x_0 = 0$ and $r = m$, where $m$ 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 $R_P$ rounds linear, as noted in the attack paper↗. More precisely, for a certain invariant subspace $V$, if $\Delta \in V$ and $x \oplus y = \Delta$, then $F(x) \oplus F(y) = L(\Delta)$, where $F$ represents the middle layer and $L$ 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 $m$ that is not divisible by 4 or by choosing another secure MDS matrix, designers decided to dismiss Starkad and let only Poseidon remain.

Conclusion

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.