New Algebraic Attacks on Grendel with the Strategy of Bypassing SPN Steps

I.   Introduction

With the rapid development of new applications such as zero-knowledge (ZK), secure multi-party computation (MPC), fully homomorphic encryption (FHE), some efficient symmetric schemes suitable for these scenarios have been proposed in recent years. Different from traditional symmetric ciphers, the design goal of such ciphers is not to reduce execution time, energy consumption, memory footprint, etc. Instead, they optimize the algebraic complexity, i.e., they attempt to minimize the number of non-linear operations in their natural algorithm description. Therefore, they are often referred to as arithmetization-oriented (AO) ciphers.

Since the cipher LowMC [1] was proposed at Eurocrypt 2015 by Albrecht et al., which is friendly to MPC and FHE, an increasing number of AO symmetric-key primitives have been raised, including FLIP [2], Kreyvrium [3], Rasta [4], MiMC [5], Feistel-MiMC [5], GMiMC [6], Ciminion [7], Poseidon [8], and Neptune [9]. Most of them use low-degree nonlinear functions such as $x\rightarrow x^d$.

However, for some use cases of ZK proof systems, it is feasible to reach efficiency with high-degree nonlinear functions. In such a use case, the complexity of proving/verifying a given statement $y = F(x)$ for a certain function $F$ is considered. Instead of proving/verifying $y = F(x)$ directly, proving/verifying an equivalent relation $G(x,y) = c$ may be more efficient. This approach is used in Vision [10], Rescue-Prime [11] and Grendel [12]. In Vision, a high-degree function $x\rightarrow x^{-1}$ is used. In Rescue-Prime, a low-degree function $x\rightarrow x^d$ and a high-degree function $x\rightarrow x^{\frac{1}{d}}$ are used. In Grendel, the nonlinear layer uses the Legendre symbol as a component, which is a function of high degree $\frac{p-1}{2}$ over an odd prime field $\mathbb{F}_p$.

On the other side, these AO symmetric primitives propose new challenges for cryptanalysts to analyze their security. And as designing symmetric ciphers in this domain is reasonably new and not well-studied, some fatal errors may be neglected at the design phase. For instance, soon after the publication of LowMC, a higher-order differential cryptanalysis [13] and an optimized interpolation cryptanalysis [14] were given, which made LowMC move to LowMC v2. Later the difference enumeration technique [15] was proposed, which made LowMC v2 move to LowMC v3. However, the recent attacks [16]–[19] have demonstrated that some instances in LowMC v3 are still insecure.

In order to better evaluate the security of AO hash functions, Ethereum Foundation put forward a challenge ¹ to analyze the constrained input/constrained output (CICO) problem for some round-reduced versions of permutations underlying several sponge-based AO hash functions, including Feistel-MiMC, Poseidon, Rescue-Prime and Reinforced Concrete [20]. Later, the work done by Bariant et al. [21] showed that the security cryptanalysis presented by the challenge’s authors or designers of three such primitives (i.e., Feistel-MiMC, Poseidon and Rescue-Prime) was too optimistic.

In this paper, we evaluate the security of the AO cipher Grendel [12]. Grendel defines a family of permutations, which are used to obtain hash functions by applying the sponge construction [22]–[24]. At FSE 2022, Grassi et al. [25] proposed the first preimage attack on some original full GrendelHash instances. This attack considered the case where the output of GrendelHash consists of one field element. It used the strategy that if let the input state only have one unknown field element (denoted by $x$) and all Legendre symbols in the scheme be fixed, then the output of GrendelHash can be written as a univariate polynomial in terms of $x$, of which the degree may be low. As a countermeasure, the designer adds this attack into the security analysis and updates the formula to derive the secure number of rounds.

Our contributions In our work, we propose three new algebraic attacks on GrendelHash and consider the case where the digest consists of one field element. In the work done by Bariant et al. [21] at FSE 2023, the strategy of bypassing substitution-permutation networks (SPN) steps was used to solve the CICO problem for the cryptographic permutations which are intended for use in a sponge construction to build hash functions. We give a generalization of this strategy such that it can be used to deal with more than just CICO problem. Our results are detailed as follows:

1) With bypassing one SPN step, we can find a preimage with a lower complexity than previous attacks for some round-reduced instances.

2) Regarding the special case where the sponge capacity consists of one field element, with bypassing two SPN steps, a) For the preimage attack, the complexity can be reduced further and we can attack one more round than previous attacks for some round-reduced instances; b) By solving the CICO problem for the underlying permutations, we propose the first collision attack on some round-reduced instances.

The results are summarized in Tables 1–3. The complexity of original preimage attack is derived from the formula presented in Scetion V in [25]. The complexity of designer’s attack is derived from the formula presented in Table 1 in [12].

Table  1.  A summary of the attacks on GrendelHash instances with parameters $\alpha=2,\lambda=128, \log_2(p)\approx256$

Instance $(\alpha, m, c, R)$	$N$	Type	Complexity	Ref.
$(2,4,1,31)$	$23$	Preimage	$2^{138.34}$	Original [25]
			${\boldsymbol{2^{123.05}}}$	Designer’s [12]
			${\boldsymbol{2^{119.64}}}$	Section VI.2
	$24$	Preimage	$2^{143.49}$	Original [25]
			$2^{128.17}$	Designer’s [12]
			${\boldsymbol{2^{124.74}}}$	Section VI.2
	$24$	Collision	${\boldsymbol{2^{124.74}}}$	Section VI.3
$(2,8,1,17)$	$13$	Preimage	$2^{134.35}$	Original [25]
			${\boldsymbol{2^{123.40}}}$	Designer’s [12]
			${\boldsymbol{2^{122.50}}}$	Section V
			${\boldsymbol{2^{112.32}}}$	Section VI.2
	$14$	Preimage	$2^{143.61}$	Original [25]
			$2^{132.61}$	Designer’s [12]
			${\boldsymbol{2^{121.50}}}$	Section VI.2
	$14$	Collision	${\boldsymbol{2^{121.50}}}$	Section VI.3
$(2,12,1,12)$	$9$	Preimage	$2^{129.05}$	Original [25]
			${\boldsymbol{2^{122.34}}}$	Designer’s [12]
			${\boldsymbol{2^{117.71}}}$	Section V
			${\boldsymbol{2^{103.54}}}$	Section VI.2
	$10$	Preimage	$2^{142.43}$	Original [25]
			$2^{135.64}$	Designer’s [12]
			${\boldsymbol{2^{116.71}}}$	Section VI.2
	10	Collision	${\boldsymbol{2^{116.71}}}$	Section VI.3
Note: The complexity is estimated in field operations. R denotes the secure number of rounds; N denotes the number of attacked rounds; Bold numbers indicate the attacks are valid.

 | Show Table

DownLoad: CSV

Table  2.  A summary of the attacks on GrendelHash instances with parameters $\alpha=3,\lambda=128, \log_2(p)\approx256$

Instance $(\alpha, m, c, R)$	$N$	Type	Complexity	Ref.
$(3,8,1,16)$	$12$	Preimage	$2^{133.70}$	Original [25]
			$\boldsymbol{2^{121.19}}$	Designer’s [12]
			$\boldsymbol{2^{120.70}}$	Section V
			$\boldsymbol{2^{109.92}}$	Section VI.2
	$13$	Preimage	$2^{143.56}$	Original [25]
			$2^{131}$	Designer’s [12]
			$\boldsymbol{2^{119.70}}$	Section VI.2
	$13$	Collision	$\boldsymbol{2^{119.70}}$	Section VI.3
$(3,12,1,12)$	$9$	Preimage	$2^{135.94}$	Original [25]
			$\boldsymbol{2^{127.60}}$	Designer’s [12]
			$\boldsymbol{2^{123.29}}$	Section V
			$\boldsymbol{2^{108.43}}$	Section VI.2
	$10$	Preimage	$2^{149.90}$	Original [25]
			$2^{141.49}$	Designer’s [12]
			$\boldsymbol{2^{122.29}}$	Section VI.2
	$10$	Collision	$\boldsymbol{2^{122.29}}$	Section VI.3
$(3,12,2,12)$	$9$	Preimage	$2^{135.94}$	Original [25]
			$\boldsymbol{2^{126.60}}$	Designer’s [12]
			$\boldsymbol{2^{123.29}}$	Section V
Note: The complexity is estimated in field operations. R denotes the secure number of rounds; N denotes the number of attacked rounds; Bold numbers indicate the attacks are valid.

 | Show Table

DownLoad: CSV

Table  3.  A summary of the attacks on GrendelHash instances with parameters $\alpha=5,\lambda=128, \log_2(p)\approx256$

Instance $(\alpha, m, c, R)$	$N$	Type	Complexity	Ref.
$(5,8,1,15)$	$11$	Preimage	$2^{133.24}$	Original [25]
			$\boldsymbol{2^{119.46}}$	Designer’s [12]
			$\boldsymbol{2^{119.06}}$	Section V
			$\boldsymbol{2^{107.53}}$	Section VI.2
	$12$	Preimage	$2^{143.87}$	Original [25]
			$2^{130.03}$	Designer’s [12]
			$\boldsymbol{2^{118.06}}$	Section VI.2
	$12$	Collision	$\boldsymbol{2^{118.06}}$	Section VI.3
$(5,12,1,11)$	$8$	Preimage	$2^{129.18}$	Original [25]
			$\boldsymbol{2^{119.58}}$	Designer’s [12]
			$\boldsymbol{2^{115.37}}$	Section V
			$\boldsymbol{2^{99.74}}$	Section VI.2
	$9$	Preimage	$2^{143.91}$	Original [25]
			$2^{134.24}$	Designer’s [12]
			$\boldsymbol{2^{114.37}}$	Section VI.2
	$9$	Collision	$\boldsymbol{2^{114.37}}$	Section VI.3
$(5,12,2,11)$	8	Preimage	$2^{129.18}$	Original [25]
			$\boldsymbol{2^{118.58}}$	Designer’s [12]
			$\boldsymbol{2^{115.37}}$	Section V
Note: The complexity is estimated in field operations. R denotes the secure number of rounds; N denotes the number of attacked rounds; Bold numbers indicate the attacks are valid.

 | Show Table

DownLoad: CSV

Organization of the paper In Section II, we give some notations and related definitions. Besides, we give a brief description of Grendel and the algorithm for solving univariate system. In Section III, we revisit the original preimage attack on GrendelHash. In Section IV, we give a generalization of the strategy of bypassing SPN steps. In Section V, we introduce our first preimage attack. In Section VI, we introduce our second preimage attack and the first collision attack. The experimental results of our attacks are given in Section VII. Finally, the paper is concluded in Section VIII.

II.   Preliminaries

In this section, we will first give some notations and related definitions. Then, we will give a brief description of Grendel [12]. Finally, we will describe the algorithm [21] for solving univariate system.

1   Notations and related definitions

In the following content of this paper, $p$ denotes an odd prime. $\mathbb{F}_p$ denotes the finite field with $p$ elements. For ${\boldsymbol{x}}=(x_0,\dots,x_{a-1})\in\mathbb{F}_p^a$ and ${\boldsymbol{y}}=(y_0,\dots,y_{b-1})\in\mathbb{F}_p^b$, the concatenation of ${\boldsymbol{x}}$ and ${\boldsymbol{y}}$ is denoted by ${\boldsymbol{x}}\parallel {\boldsymbol{y}}$, i.e., ${\boldsymbol{x}}\parallel {\boldsymbol{y}}=(x_0,\dots,x_{a-1},y_0,\dots,y_{b-1})\in \mathbb{F}_p^{a+b}$.

Definition 1 The hash function $H$ is $\lambda$-bit secure against preimage attack if no algorithm has an expected complexity less than $2^\lambda$ for finding $u$ given $h$ such that $H(u)=h$.

Definition 2 The hash function $H$ is $\lambda$-bit secure against collision attack if no algorithm has an expected complexity less than $2^\lambda$ for finding $u_1, u_2$ such that $H(u_1)=H(u_2)$ and $u_1\neq u_2$.

Definition 3 Let $F:\mathbb{F}_p^n\rightarrow \mathbb{F}_p^n$ be a permutation. ${\cal{Z}}_t$ is the set of all elements of $\mathbb{F}_p^n$ such that their last $t$ coordinates are equal to $0$. The CICO problem is finding ${\boldsymbol{x}}\in\mathbb{F}_p^n$ such that ${\boldsymbol{x}}\in{\cal{Z}}_t$ and $F({\boldsymbol{x}})\in{\cal{Z}}_t$.

2   Description of Grendel

Grendel [12] defines a family of permutations with SHARK-like constructions [26]. Based on the Grendel permutation, the Grendel hash function is obtained by applying the sponge construction [22]–[24] and using the primitive as an inner permutation. The different permutations in the family are determined by the triple $(p,m,c,\lambda)$ representing respectively the size of the field over which the primitive’s operations are defined, the number of field elements in the state, the number of field elements in the sponge capacity and the target security level. The secure number of rounds $R$ can be obtained from these parameters as follows:

where

In other words, $R$ is set to the smallest integer such that the complexities of all attacks presented in Table 1 in [12] are at least $2^{1.25\lambda}$.

Grendel permutation uses the Legendre symbol as a component. Therefore we first introduce the definition of the Legendre symbol.

Definition 4 The Legendre symbol is a function $(\dfrac{\cdot}{p}):\mathbb{F}_p\rightarrow \mathbb{F}_p$ defined as

where $\mathrm{QR}_p=\{b^2\vert b \in \mathbb{F}_p\backslash \{0\} \}$.

Grendel permutation $P:\mathbb{F}_p^m\rightarrow \mathbb{F}_p^m$ $(m\ge2)$ iterates a round function $R$ times. At the $i$-th $(0\le i\le R-1)$ round the round function consists of the following operations, as depicted in Figure 1.

Figure  1.  The Grendel round function.

DownLoad: Full-Size Img PowerPoint

1) SboxLayer (SB): A S-box $S: \mathbb{F}_p\rightarrow \mathbb{F}_p$ is applied to the $m$ elements of the state in parallel. The S-box is defined as $S(x)=x^\alpha\times(\frac{x}{p})$, where if $p\equiv 3\; {\rm{mod}}\; 4$ then $\alpha=2$ and if $p\equiv 1\; {\rm{mod}}\;4$ then $\alpha\ge 3$ is the smallest integer such that ${\rm gcd}(\alpha,p-1)=1$.

2) LinearLayer (L): The state vector is multiplied with an MDS matrix ${\boldsymbol{M}}$ of size $m\times m$.

3) ConstantAddition (AC): The round constant $C_{im+j}\in\mathbb{F}_p$ is added to the $j$-th element of the state, where $j\in\{0,1,\dots,m-1\}$.

By using the Grendel permutation in a sponge construction, the Grendel hash function is obtained. Specifically, $r$ and $c$ denote the number of field elements in the sponge rate and the sponge capacity respectively. And the number of field elements in the digest is denoted by $l$. Then for the input consisting of elements of $\mathbb{F}_p$, the procedure for computing its digest consists of the following operations, as depicted in Figure 2.

Figure  2.  The absorbing and squeezing phases.

DownLoad: Full-Size Img PowerPoint

1) Padding: If the input length is variable, then the input is padded as follows: first append a single 1 to the input, and then append zeros until the total length is a multiple of $r$. If the input length is fixed, then the input does not need to be processed in this phase. Then divide the result into blocks ${\boldsymbol{m}_0},{\boldsymbol{m}_1},\dots,{\boldsymbol{m}_{k-1}}$, where each block ${\boldsymbol{m}_i}$ $(0\le i\le k-1)$ consists of $r$ elements of $\mathbb{F}_p$.

2) Initializing: The state is initialized to ${\boldsymbol{IV}}=(0, 0,\dots,0)\in\mathbb{F}_p^m$.

3) Absorbing: The blocks ${\boldsymbol{m}_0},\,{\boldsymbol{m}_1},\,\dots,\,{\boldsymbol{m}_{k-1}}$ are added into the top $r$ elements of the state, interleaved with applications of the permutation $P$. When all blocks are processed, switch to the squeezing phase.

4) Squeezing: First extract ${\rm min}(l,r)$ elements from the top $r$ elements of the state. If $l>r$, then apply $P$ to the state and extract ${\rm min}(l-r,r)$ elements from the top $r$ elements of the state. Repeat this process until the number of extracted elements reach $l$.

In addition, for the target security level $\lambda$-bit, the number of field elements in the sponge capacity $c$ and the number of field elements in the digest $l$ should satisfy $\frac{c\log_2(p)}{2}\ge\lambda$ and $\frac{l\log_2(p)}{2}\ge\lambda$.

3   Solving univariate system

In this part, we will introduce the algorithm [21] for solving univariate system. Let $g(x)\in\mathbb{F}_p[x]$ and $d$ denote the degree of $g(x)$. Our goal is to find the roots of $g(x)$ in $\mathbb{F}_p$. The algorithm consists of the following steps.

1) Use repeated squaring algorithm [27] in $\mathbb{F}_p[x]/ \langle g(x)\rangle$ to compute $q(x)=x^p\; {\rm{mod}}\;g(x)$.

2) Compute $r(x)=\gcd(q(x)-x,g(x))$.

3) Factor $r(x)$.

Complexity evaluation The algorithm’s complexity given in [21] is ${\cal{O}}(d\log_2(d)(\log_2(d) + \log_2(p))\log_2(\log_2(d)))$ field operations.

Specifically, multiplying two polynomials of degree $n$ by using an FFT algorithm needs ${\cal{O}} (n \log_2(n) \log_2(\log_2(n)))$ field operations. ${\cal{O}} (d \log_2(p) \log_2(d) \log_2(\log_2(d)))$ field operations are needed in step 1); ${\cal{O}} (d(\log_2(d))^2 \log_2(\log_2(d)))$ field operations are needed in step 2). In general, the degree of $r(x)$ is only one or two because $g(x)$ has few roots in $\mathbb{F}_p$. Thus, the complexity of the third step is negligible.

We note that this algorithm was also used in the original preimage attack [25] and had a different complexity evaluation. However, the complexity given in [21] is sharper, which will be used in our work.

III.   The Original Preimage Attack

In this section, we will briefly revisit the original preimage attack [25] on $N$-round GrendelHash instances, of which the number of field elements in the digest $l$ is 1. And the number of field elements in the sponge rate $r\ge2$.

Given a digest $h\in\mathbb{F}_p$, the overall procedure for finding a preimage can be separated into the following steps, as depicted in Figure 3.

Figure  3.  Introduce the steps of the original preimage attack, where the unknown Legendre symbols are colored in yellow and the known intermediate values are colored in gray.

DownLoad: Full-Size Img PowerPoint

1) Choose ${\boldsymbol{u}}=(u_1,\dots,u_{r-1})\in\mathbb{F}_p^{r-1}$ randomly. Let the input of GrendelHash be $x\parallel {\boldsymbol{u}}\in\mathbb{F}_p^r$, where $x$ is an unknown variable.

2) Guess the values (only 1 or −1) of the $L=1+ m(N-1)$ unknown Legendre symbols (i.e., the yellow states in the Figure 3) in the $N$ rounds. Then write the first element in the output state of $N$-round Grendel permutation $P$ as a polynomial in terms of $x$, which is denoted by $p(x)$ and has a degree of $\alpha^N$.

3) Solve the equation $p(x)-h=0$ in $\mathbb{F}_p$. For each solution $x^*$, if all computed Legendre symbols equal the guessed ones, then the solution is valid and return $x^*\parallel {\boldsymbol{u}}$. If all solutions we find are not valid, then go to step 2) and guess the Legendre symbols with values we have not tried before.

4) If all possible guesses are traversed and no valid solution is found, then go to step 1) and try again with a different ${\boldsymbol{u}}$.

Success probability For a random ${\boldsymbol{u}}\in\mathbb{F}_p^{r-1}$, it can be expected that there is a value $x_0\in\mathbb{F}_p$ such that the digest of $x_0\parallel {\boldsymbol{u}}$ equals $h$. The probability that a Legendre symbol is equal to 1 is $\frac{p-1}{2p}$, the probability that a Legendre symbol is equal to −1 is $\frac{p-1}{2p}$, and the probability that a Legendre symbol is equal to 0 is $\frac{1}{p}$. As for $x_0$, the probability that the L Legendre symbols are different from $0$ is $(1-\frac{1}{p})^L$, which is extremely close to 1 for the parameters considered in the attack. Therefore, the $x_0$ can be found successfully with a high enough probability. In order to increase the success probability of the attack, try twice with different ${\boldsymbol{u}}$.

As a countermeasure, the designer added this attack into the security analysis. The total complexity is estimated as $2^{Nm-c}\cdot\alpha^N\cdot N^2$ by the designer in [12].

IV.   A Generalization of the Strategy of Bypassing SPN Steps

In this section, we will give a generalization of the strategy of bypassing SPN steps, which was originally proposed by Bariant et al. [21] to solve the CICO problem (in the case where ${\cal{Z}}_t={\cal{Z}}_1$).

Let $F=F_1\circ F_0$ be a permutation of $\mathbb{F}_p^n$ with a SPN construction. Let ${\cal{B}}\subseteq\mathbb{F}_p^n$ and ${\cal{H}}_j^b=\{(y_1,y_2,\dots,y_n)\in$ $\mathbb{F}_p^n\vert y_j=b\}$, where $1\le j\le n$ and $b\in\mathbb{F}_p$. Our problem is finding ${\boldsymbol{x}}\in\mathbb{F}_p^n$ such that ${\boldsymbol{x}}\in{\cal{B}}$ and $F({\boldsymbol{x}})\in{\cal{H}}_j^b$.

If we find an affine space ${\cal{W}}=\{s{\boldsymbol{\beta}}+{\boldsymbol{\gamma}}\vert s\in\mathbb{F}_p\}$ in which ${\boldsymbol{\beta}}=(\beta_0,\dots,\beta_{n-1}),\; {\boldsymbol{\gamma}}=(\gamma_0,\dots,\gamma_{n-1})\in\mathbb{F}_p^n$ such that $F_0^{-1}({\cal{W}})\subseteq {\cal{B}}$, then we will handle the permutation $F_1$ rather than the full permutation $F$. It could be easier to solve the problem. The detailed procedure can be separated into the following steps, as depicted in Figure 4.

Figure  4.  Bypass SPN steps.

DownLoad: Full-Size Img PowerPoint

1) Let the output state of $F_0$ (i.e., the input state of $F_1$) be $z{\boldsymbol{\beta}}+{\boldsymbol{\gamma}}=(\beta_0z+\gamma_0,\ldots,\beta_{n-1}z+\gamma_{n-1})$, where $z$ is an unknown variable.

2) Write the $j$-th element in the output state of $F_1$ as a polynomial in terms of $z$, which is denoted by $f_1^j(z)$.

3) Find a root $z_0$ in $\mathbb{F}_p$ for the polynomial $f_1^j(z)-b$.

4) Compute ${\boldsymbol{x}_0}=F_0^{-1}(z_0{\boldsymbol{\beta}}+{\boldsymbol{\gamma}})$ and return ${\boldsymbol{x}_0}$.

V.   Our First Preimage Attack

In this section, we will introduce our first preimage attack on $N$-round GrendelHash instances. The number of field elements in the output $l=1$, the number of field elements in the sponge rate $r\ge2$, and $\log_2(p)\ge2\lambda$. In the following, each SPN step consists of one round of Grendel.

1   Bypass one SPN step

Let ${\cal{B}}_1$ be the set of all elements of $\mathbb{F}_p^m$ such that their last $c$ coordinates are equal to $0$, i.e., ${\cal{B}}_1=\{(x_0,x_1, \dots,x_{m-1})\in \mathbb{F}_p^m\vert x_i=0, m-c\le i\le m-1\}$. For a given digest $h\in\mathbb{F}_p$, if we find ${\boldsymbol{x}}\in\mathbb{F}_p^m$ such that ${\boldsymbol{x}}\in{\cal{B}}_1$ and $P({\boldsymbol{x}})\in{\cal{H}}_1^h$, where $P$ is the underlying $N$-round Grendel permutation, then we will find a preimage. Therefore, we can exploit the strategy of bypassing SPN steps presented in Section IV in this attack.

Let $N$-round Grendel permutation be $P=P_{N-1}\circ P_1$, where $P_1$ consists of one SPN step of Grendel, i.e., the operations in the $0$th round. Let the MDS matrix ${\boldsymbol{M}}$ be

Choose ${\boldsymbol{w}}=(w_1,\dots,w_{r-1})\in\mathbb{F}_p^{r-1}$. Let ${\boldsymbol{\beta}}=(a_{0,0}, a_{1,0},\dots,a_{m-1,0})$ and ${\boldsymbol{\gamma}}=(\sum_{i=1}^{r-1}a_{0,i}w_i + C_0, \sum_{i=1}^{r-1}a_{1,i}w_i + C_1,\ldots, \sum_{i=1}^{r-1}a_{m-1,i}w_i+C_{m-1})$. Then the affine space ${\cal{W}}=\{s{\boldsymbol{\beta}}+{\boldsymbol{\gamma}}\vert s\in\mathbb{F}_p\}$ satisfies $P_1^{-1}({\cal{W}})\subseteq{\cal{B}}_1$, as depicted in Figure 5.

Figure  5.  Bypass one SPN step.

DownLoad: Full-Size Img PowerPoint

Therefore, the remaining task is to find $z_0$ in $\mathbb{F}_p$ such that $P_{N-1}(z_0{\boldsymbol{\beta}}+{\boldsymbol{\gamma}})\subseteq {\cal{H}}_1^h$.

2   The steps of our first preimage attack

In the following, we will introduce our first preimage attack in detail. Let the input state of $P_{N-1}$ be $z{\boldsymbol{\beta}}+{\boldsymbol{\gamma}}$, where $z$ is an unknown variable. Denote the first coordinate in $P_{N-1}(z{\boldsymbol{\beta}}+{\boldsymbol{\gamma}})$ by $f_{N-1}^1(z)$. In order to find $z_0$ in $\mathbb{F}_p$ such that $P_{N-1}(z_0{\boldsymbol{\beta}}+{\boldsymbol{\gamma}})\subseteq {\cal{H}}_1^h$, instead of solving the equation $f_{N-1}^1(z)=h$ in $\mathbb{F}_p$ directly, we exploit the strategy that was used in the original preimage attack [25].

Specifically, the procedure for finding a preimage in this attack can be separated into the following steps (as shown in Algorithm 1).

1) Choose ${\boldsymbol{w}}=(w_1,\dots,w_{r-1})\in\mathbb{F}_p^{r-1}$ randomly. Let ${\boldsymbol{\beta}}=(a_{0,0},a_{1,0},\dots,a_{m-1,0})$ and ${\boldsymbol{\gamma}}=(\sum_{i=1}^{r-1}a_{0,i}w_i+C_0, \sum_{i=1}^{r-1}a_{1,i}w_i+C_1,\ldots,\sum_{i=1}^{r-1}a_{m-1,i}w_i+C_{m-1})$.

2) Let the input of $P_{N-1}$ be $z{\boldsymbol{\beta}}+{\boldsymbol{\gamma}}$, where $z$ is an unknown variable.

3) Guess the values (only 1/−1) of the $L_1=m(N - 1)$ unknown Legendre symbols in $P_{N-1}$. And write the first element in the output state of $P_{N-1}$ as a polynomial in terms of $z$, which is denoted by $p_1(z)$.

4) Solve the equation $p_1(z)-h=0$ in $\mathbb{F}_p$. For each solution $z^*$, if all computed Legendre symbols equal the guessed ones in the $N-1$ rounds, then the solution is valid and return the first $r$ elements in $P_1^{-1}(z^*{\boldsymbol{\beta}}+{\boldsymbol{\gamma}})$. If all solutions we find are invalid, then go to step 3) and guess the Legendre symbols with values we have not tried before.

5) If all possible guesses are traversed and no valid solution is found, then go to step 1) and try again with a different ${\boldsymbol{w}}$.

Success probability For a random ${\boldsymbol{w}}\in\mathbb{F}_p^{r-1}$, it can be expected that there is a value $z_0$ in $\mathbb{F}_p$ such that $P_{N-1}(z_0{\boldsymbol{\beta}}+{\boldsymbol{\gamma}})\subseteq{\cal{H}}_1^h$. As for $z_0$, the probability that the $L_1$ Legendre symbols in $P_{N-1}$ are different from $0$ is equal to $(1-\frac{1}{p})^{L_1}$, which is extremely close to 1 for the parameters considered in our attack. Thus, $z_0$ can be found successfully with a high enough probability. Similarly to that in the original preimage attack, we try twice with different ${\boldsymbol{w}}$ to increase the success probability of the attack.

Complexity evaluation For each guess, we need to find the roots of the polynomial $p_1(z)-h$ in $\mathbb{F}_p$ and it can be expected that the number of roots in $\mathbb{F}_p$ is 1. Since the degree $D_1$ of $p_1(x)-h$ is $\alpha^{N-1}$, then as shown in Section II.3, the complexity of solving the equation $p_1(z)-h=0$ is equal to

For the solution, when verifying whether it is valid, we need to compute the Legendre symbols forwards until there is a computed value that do not match the guessed one. The expected number of Legendre symbols that need to be computed is equal to

In addition, the complexity of computing a Legendre symbol [28] is equal to

Hence, the expected complexity of our first preimage attack on $N$-round GrendelHash is

The results of our first preimage attack on some instances are summarized in Tables 1–3.

Remark In our first preimage attack, the reasons for the reduced complexity compared to the original preimage attack [25] are as follows. First, the number of Legendre symbols needed to be guessed is reduced by 1. Second, the degree of univariate polynomial needed to be solved after guessing the values of the unknown Legendre symbols is $\alpha^{N-1}$, which is $\alpha$ times lower than that in the original preimage attack. Third, for the algorithm of solving univariate system, we use the complexity evaluation given in [21] at FSE 2023, which is better than that used in [25].

VI.   For the Special Case Where c = 1

In this section, we will introduce our second preimage attack and the first collision attack on some $N$-round GrendelHash instances. The number of field elements in the output $l=1$, the number of field elements in the sponge rate $r\ge2$, the number of field element in the sponge capacity $c=1$, and $\log_2(p)\ge2\lambda$.

1   Bypass two SPN steps

Let ${\cal{B}}_2$ be the set of all elements of $\mathbb{F}_p^m$ such that their last coordinate is equal to 0, i.e., ${\cal{B}}_2=\{(x_0,x_1, \ldots,x_{m-1})\in\mathbb{F}_p^m\vert x_{m-1}=0\}$. Let the underlying permutation be $P=P_{N-2}\circ P_2$, where $P_2$ consists of two SPN steps of Grendel, i.e., the operations in the $0$th round and the 1st round. Let the inverse of ${\boldsymbol{M}}$ be

Let ${\boldsymbol{\beta'}}=(S(A_0),S(A_1),\dots,S(A_{m-2}),0)$ and ${\boldsymbol{\gamma'}}=(0, 0,\ldots,0,g)$, where $A_i$ $(0\le i\le m-2)$ and $g$ are constants in $\mathbb{F}_p$ that satisfy the following conditions:

And let ${\boldsymbol{\tilde{\beta}}}^{\rm{T}} = {\boldsymbol{M}}\cdot {\boldsymbol{\beta'}}^{T}$ and ${\boldsymbol{\tilde{\gamma}}}^{\rm{T}} = {\boldsymbol{M}}\cdot{\boldsymbol{\gamma'}}^{\rm{T}} + (C_m,C_{m+1}, \ldots, C_{2m-1})^{\rm{T}}$. Then the affine space ${\cal{W}}_1=\{s{\boldsymbol{\tilde{\beta}}} + {\boldsymbol{\tilde{\gamma}}}\vert s{\in}\mathbb{F}_p\}$ satisfies that $P_2^{-1}({\cal{W}}_1)\subseteq {\cal{B}}_2$, as depicted in Figure 6.

Figure  6.  Bypass two SPN steps.

DownLoad: Full-Size Img PowerPoint

2   Our second preimage attack

In the following, we will describe the steps of our second preimage attack. For a given digest $h\in\mathbb{F}_p$, in order to find $z_1$ in $\mathbb{F}_p$ such that $P_{N-2}(z_1{\boldsymbol{\tilde{\beta}}}+{\boldsymbol{\tilde{\gamma}}})\subseteq {\cal{H}}_1^h$, we also exploit the strategy that was used in the original preimage attack [25].

Specifically, the procedure for finding a preimage in this attack can be separated into the following steps (as shown in Algorithm 2).

1) Let the input state of $P_{N-2}$ be $z{\boldsymbol{\tilde{\beta}}}+{\boldsymbol{\tilde{\gamma}}}$, where $z$ is an unknown variable.

2) Guess the values (only 1/−1) of the $L_2 = m(N - 2)$ unknown Legendre symbols in the $P_{N-2}$. And write the first element in the output of $P_{N-2}$ as a polynomial in terms of $z$, which is denoted by $p_2(z)$.

3) Solve the equation $p_2(z)-h=0$ in $\mathbb{F}_p$. For each solution $z^*$, if the computed Legendre symbols equal the guessed ones, then the solution is valid and go to step 4). If all solutions are invalid, then go to step 2) and guess the Legendre symbols with values we have not tried before.

4) Compute ${\boldsymbol{x}}=P_2^{-1}(z^*{\boldsymbol{\tilde{\beta}}}+{\boldsymbol{\tilde{\gamma}}})$ and return the first $r$ elements of ${\boldsymbol{x}}$.

Success probability It can be expected that there is a value $z_1\in\mathbb{F}_p$ such that the first element in $P_{N - 2}(z_1{\boldsymbol{\tilde{\beta}}}+ {\boldsymbol{\tilde{\gamma}}})$ equals the given digest $h$. As for $z_1$, the probability that the $L_2$ Legendre symbols are different from $0$ is equal to $(1-\frac{1}{p})^{L_2}$, which is extremely close to $1$ for the parameters considered in our attack. Therefore, we can find a preimage for a given digest $h$ with a high enough probability.

Complexity evaluation In this attack, for each guess, the degree $D_2$ of $p_2(z)-h$ is $\alpha^{N-2}$. Then the complexity of solving the equation $p_2(z)-h=0$ is equal to

Therefore, the expected complexity of our second preimage attack on $N$-round GrendelHash is

The results of our second preimage attack on some instances are summarized in Tables 1–3.

3   The first collision attack

In the following, we will present our collision attack by solving the CICO problem (in the case where ${\cal{Z}}_t={\cal{Z}}_1$) for the underlying permutation $P$. The procedure for finding a solution to the CICO problem is almost the same as the steps of our second preimage attack. After finding a solution ${\boldsymbol{x}}=(x_0,x_1,\ldots,x_{r-1},0)$ to the CICO problem, where $P({\boldsymbol{x}})=(y_0,y_1\ldots,y_{r-1},0)$, let ${\boldsymbol{m}} = (x_0,x_1, \ldots,x_{r-1})$ and ${\boldsymbol{m'}}=(x_0-y_0,x_1-y_1,\ldots,x_{r-1}-y_{r-1})$. Then ${\rm{GrendelHash}} ({\boldsymbol{m}})= {\rm{GrendelHash}} ({\boldsymbol{m}}\|{\boldsymbol{m'}})$.

Specifically, the procedure for the collision attack can be separated into the following steps (as shown in Algorithm 3).

1) Let the input state of $P_{N-2}$ be $z{\boldsymbol{\tilde{\beta}}}+{\boldsymbol{\tilde{\gamma}}}$, where $z$ is an unknown variable.

2) Guess the values (only 1/−1) of the $L_2 = m(N - 2)$ unknown Legendre symbols in the $P_{N-2}$. And write the last element in the output of $P_{N-2}$ as a polynomial in terms of $z$, which is denoted by $p_3(z)$.

3) Solve the equation $p_3(z)=0$ in $\mathbb{F}_p$. For each solution $z^*$, if the computed Legendre symbols equal the guessed ones, then the solution is valid and go to step 4). If all solutions are invalid, then go to step 2) and guess the Legendre symbols with values we have not tried before.

4) Compute ${\boldsymbol{x}} = P_2^{-1}(z^*{\boldsymbol{\tilde{\beta}}} + {\boldsymbol{\tilde{\gamma}}})$ and ${\boldsymbol{y}} = P_{N-2}(z^*{\boldsymbol{\tilde{\beta}}}+ {\boldsymbol{\tilde{\gamma}}})$. Denote ${\boldsymbol{x}} = (x_0,x_1,\dots,x_{r-1},$ $0)$ and ${\boldsymbol{y}} = (y_0,y_1,\dots, y_{r-1},0)$. Let ${\boldsymbol{m}}=(x_0,x_1,\dots,x_{r-1})$ and ${\boldsymbol{m}}'=(x_0-y_0, x_1-y_1,\dots,x_{r-1}-y_{r-1})$. Return ${\boldsymbol{m}}$ and ${\boldsymbol{m}}\|{\boldsymbol{m'}}$.

We note that the success probability and expected complexity of our collision attack are the same as those of our second preimage attack that presented in Section VI.2. The results of our collision attack on some instances are summarized in Tables 1–3.

VII.   Experiments

In order to verify the feasibility of our methods, we made experiments for our three new algebraic attacks on the round-reduced GrendelHash instance with parameters $(p,m,r,c,\lambda)=(2^{64}-59,3,2,1,32)$. And the number of attacked round $N=6$. We provide our code at https://github.com/wxqiao/New-algebraic-attacks-on-Grendel. Let the prime field $\mathbb{F}_p=\{0,1,\dots,p-1\}$.

First, we performed $100$ tests for our first preimage attack. By using the Algorithm 1, $83$ tests of them can be attacked successfully. For instance, for a given digest $h_1=4509062438608773474\in\mathbb{F}_p$, we found a preimage

Second, we performed $1000$ tests for our second preimage attack. By using the Algorithm 2, $608$ tests of them can be attacked successfully. For instance, for a given digest $h_2=14681296474556465288\in\mathbb{F}_p$, we found a preimage

Third, for our collision attack, by using the method presented in Section VI.3, we found a solution ${\boldsymbol{x}}=$ $(3978053920827369818, 11054388833269671370, 0)\in\mathbb{F}_p^3$ to the CICO problem for the underlying Grendel permutation $P$ successfully, where $P({\boldsymbol{x}}) = (12866554063376284852, 7184824262592905636,0) \in \mathbb{F}_p^3$. Let ${\boldsymbol{m}} = (397805392082736 9818, 11054388833269671370) \in$ $\mathbb{F}_p^2$ and

Then, a collision ${\rm{GrendelHash}} ({\boldsymbol{m}}) = {\rm{GrendelHash}}({\boldsymbol{m}}\|{\boldsymbol{m'}})$ is obtained for this round-reduced GrendelHash instance successfully.

VIII.   Conclusion

In this paper, we analyze the security of AO cipher Grendel. We propose three algebraic attacks on some GrendelHash instances. As a result, we can find a preimage with a lower complexity or attack one more round than previous attacks [12], [25] for some GrendelHash instances. In addition, we present the first collision attack on some round-reduced GrendelHash instances by solving the CICO problem for the underlying permutations.