From Round Skipping to S-Box Skipping Attacking Poseidon's Partial Layer via Subspace Restriction

Amit Singh Bhati · Sundas Tariq · Tomer Ashur
3MI Labs, Leuven  ·  COSIC, KU Leuven

1Introduction

The algebraic security of Poseidon has been extensively studied through Gröbner bases analyses and ideal degree reduction techniques based on round skipping (which is a form of S-box skipping). Bariant, Bouvier, Leurent, and Perrin [6] introduced a reparametrization of the first two full rounds of Poseidon (excluding the second round's MDS matrix) that eliminates their degree contribution, reducing the remaining Constrained-Input Constrained-Output (CICO-1) problem to univariate root finding on all remaining rounds.

Reevaluating the initial security analysis given by the designers of Poseidon, Ashur, Buschman, and Mahzoun [3] refined the Gröbner bases complexity bounds for both Poseidon and Poseidon2. Subsequently, Grassi, Koschatko, and Rechberger [13] refined Gröbner basis attacks using finite subspace trails to linearize some partial rounds of fixed Poseidon, Poseidon2, and Neptune instances. Bak, Bariant, Boeuf, Briaud, Øygarden, and Phanse [4] presented the CheapLunch framework for multiple-output CICO-$k$ systems, proving that the ideal degree for Poseidon is upper bounded by $\alpha^{k\cdot R_F + R_P}$ without round skipping.

Recent efforts have further improved algebraic attacks on round-reduced instances. Reduced-round Poseidon and Poseidon2 bounty challenges were solved using resultants and univariate root finding [5]. Additionally, Zhao, Sanso, Vitto, and Ding [19] enhanced Graeffe-based root-finding techniques over NTT-friendly fields, while Sanso and Vitto [17] proposed the degree annihilation attack, which linearizes the first two partial rounds for the round-reduced KoalaBear instance $(t,\alpha,R_F,R_P) = (16,3,6,8)$ in the CICO-2 setting.

Most recently, Vitto [18] constructed a constrained input family alongside a round-constant-dependent MDS matrix to establish a finite trail that holds the active S-box coordinate constant across partial rounds. By applying a controlled reparametrization over the initial full rounds, the author bypassed 18 out of 28 rounds for CICO-2 on the KoalaBear instance $(t,\alpha,R_F,R_P) = (16,3,8,20)$. Consequently, this approach reduces the effective algebraic degree from $\alpha^{R_F+R_P} = 3^{28}$ down to $\alpha^{R_F-4+R_P-14} = 3^{10} = 59049$.

Our Contribution. We introduce GSR, a novel subspace restriction approach that generalizes S-box skipping for generic CICO-$k$ configurations ($k \geq 1$). Unlike prior methods confined to initial full rounds, GSR explicitly targets the S-boxes inside the partial rounds, neutralizing the dense algebraic mixing in the middle of the permutation. Our core contributions are threefold:

• We formulate a generalized S-box skipping gadget that deterministically absorbs $2t-2k$ total S-boxes across one initial full round and $t-2k$ partial rounds, strictly bounding the polynomial degree and variable count of the resulting algebraic ideal.
• For CICO-1 against Poseidon's KoalaBear instance ($t = 24$) with $(R_{f_0}, R_p, R_{f_1}) = (1,23,4)$, i.e., 28 out of the recommended 31 rounds, we show a simple recovery of multiple input-output states using optimized univariate solvers like the Cantor-Zassenhaus algorithm [15, 8].
• For CICO-2 against Poseidon's KoalaBear instance ($t = 24$) with $(R_{f_0}, R_p, R_{f_1}) = (1,20,4)$, i.e., 25 out of the recommended 31 rounds, we show an optimized CICO solution recovery using Sylvester matrix-based resultants [9, 11], projecting the bivariate system into a single dimension and completely bypassing the expected exponential memory bottlenecks of traditional multivariate Gröbner bases [7, 10].
• We extend this approach to $k > 2$ via a trivial pairwise resultant sequence (Sylvester matrix), generalizing the attack vector without relying on Gröbner basis extraction bottlenecks.
• We implemented the attack into an optimized C++ algebraic solver and successfully recovered valid input-output states of CICO-1 solutions over 28 out of 31 rounds, and the CICO-2 solutions over 25 out of 31 rounds, in negligible time for Poseidon's KoalaBear instance ($t = 24$).

2Formal Specification of Poseidon

Let $\mathbb{F}_p$ be a prime field of size $p$. The Poseidon permutation [12] operates on a state vector $S \in \mathbb{F}_p^t$, where the state size $t = c + r$ is the sum of the capacity $c$ and the rate $r$. The non-linear layer utilizes the S-box $S(x) = x^\alpha$, where $\gcd(\alpha, p-1) = 1$. The linear layer applies a Maximum Distance Separable (MDS) matrix $M \in \mathbb{F}_p^{t \times t}$ generated according to the conditions in [1].

A single round function (e.g., at position $i$) $R^{(i)}$ consists of the addition of round constants $C^{(i)} \in \mathbb{F}_p^t$, the S-box layer, and the matrix multiplication $M$. The permutation is structured in three consecutive phases:

1. Initial Full Rounds ($R_{f_0}$): The S-box is applied to all $t$ elements of the state.
2. Partial Rounds ($R_p$): The S-box is applied solely to the first state element at the index 0; all other elements pass through the identity function.
3. Final Full Rounds ($R_{f_1}$): The S-box is again applied to all $t$ elements of the state.

Poseidon instances in [12] are defined with $R_{f_0} = R_{f_1}$ and a single notation $R_F$ is used to denote their sum.

3Degrees of Freedom and Subspace Restriction

CICO-$k$ problem. A standard CICO-$k$ problem requires finding an initial state $S_{in} \in \mathbb{F}_p^t$ such that some predetermined $k$ input words and some $k$ predetermined output words of the permutation match predefined constants (typically zero). Because $k$ words of $S_{in}$ are strictly constrained, the system possesses $t-k$ free variables at the input, referred to as input degrees of freedom (DoF).

Subspace Restriction. A generic polynomial system representing the full cipher possesses a high polynomial degree and therefore is expected to exhibit a large solution space over the algebraic closure. By actively consuming degrees of freedom, i.e., fixing certain variables to strategically chosen constants (let's say, $\Delta$s), the global solution space can be artificially restricted, as a trade-off to easily find at least one valid solution.

More specifically, fixing the input of non-linear components i.e., S-boxes, allows us to evaluate them as lower-degree (e.g., linear) transformations. The objective then is to expend available DoFs to linearize partial rounds S-boxes (and therefore the partial rounds themselves), ensuring the restricted system is uniquely equivalent to a smaller, low-degree polynomial ideal. Hence, it becomes relatively easy to solve and find at least one valid solution.

Note that iterating over multiple $\Delta$ tuples allows us to generate distinct CICO-$k$ solutions each at the same order of cost, facilitating multi-target or collision attacks.

4State of the Art

The application of subspace restriction in Poseidon cryptanalysis was formalized by Bariant, Bouvier, Leurent, and Perrin [6], who utilized all DoFs in the hash's input to skip the first two full rounds of the cipher (excluding the second round's MDS matrix) for CICO-1 ($k = 1$).

In a CICO-1 instance, the attacker possesses $t-1$ input DoFs. Bariant, Bouvier, Leurent, and Perrin's methodology imposes constraints that force specific intermediate S-box inputs or outputs to cancel out during the MDS mixing. Consequently, the non-linear transition $x \mapsto x^\alpha$ acts as an affine transformation, circumventing degree growth in the resulting polynomials.

Mathematically, their technique expends $t-2k$ of the available $t-k$ input DoFs to bypass exactly $2t-k$ S-boxes across the initial full rounds. While $2t-k$ represents the theoretical maximum number of skipped S-boxes under this formulation, the attack remains structurally confined to the initial full round layers. Once the parameterization enters the partial layer, the MDS matrix densely mixes the remaining unconstrained variables, causing the polynomial degree to grow exponentially over all remaining unskipped rounds, i.e., partial rounds still contribute exponentially to the overall polynomial degree.

5The GSR Gadget: Targeting S-Boxes in the Partial Layer

We generalize round skipping into S-box skipping at two fronts: 1) we allow it to target the intermediate partial round S-boxes rather than exclusively the initial full rounds, and 2) in order to skip an S-box, we set the variable before it to a constant rather than introducing a new linear constraint among the variables of that round which depends not only on the MDS matrix and round constants but also limits the choices of $k$ to very small values. Consequently, we make the skipping free of these parameters and therefore applicable to arbitrary $k$ values. For context, existing skipping results [6, 17] have been limited to $k \in \{1,2\}$.

While [6] looks to maximize the absolute number of skipped S-boxes ($2t-k$) by skipping almost two full rounds, we reallocate the $t-2k$ consumable DoFs to skip the first full round and $t-2k$ partial rounds resulting in a polynomial system of much lower degree.

Overall, GSR skips $2t-2k$ total S-boxes; exactly $k$ fewer S-boxes than [6]'s theoretical bound. However, by projecting the constraints into the partial rounds, the dense algebraic mixing in the middle of the cipher is neutralized, where the degree growth per variable is otherwise harder to contain, strictly bounding the polynomial degree of the final system.

5.1 Setup

We start by shifting the geometric reference point. Rather than parameterizing $S_{in}$, we parameterize $X_1 \in \mathbb{F}_p^t$, defined as the state immediately before the partial round.

5.2 Forward Linearization of the Partial Round S-Boxes

We expend $t-2k$ of the $t-k$ initial DoFs to trace $X_1$ forward. Let $S^{(r)}$ denote the $r$th partial-round's state before the addition of the round constant $C^{(r)}$ generated using a random seed in the SHAKE-256 hash function [16]. For each of the first $t-2k$ partial rounds, let $\delta^{(r)} \in \mathbb{F}_p$ be an arbitrary constant chosen by the attacker. We constrain the input to the single active S-box at index 0 to equal $\delta^{(r)}$:

$(S^{(r)} + C^{(r)})[0] = \delta^{(r)}$

Consequently, the S-box output is deterministically the field element $(\delta^{(r)})^\alpha$. The transition to round $r+1$ is given by the affine mapping:

$S^{(r+1)} = M \cdot \left( S^{(r)} + C^{(r)} - \delta^{(r)}\cdot e_0 + (\delta^{(r)})^\alpha \cdot e_0 \right)$

where $e_0$ is the standard basis vector and $M$ is the MDS matrix that satisfies the three criteria given in [14]. Because the mapping is affine, every state $S^{(r)}$ with $1 \le r \le t-2k$ remains an affine combination of the variables in $X_1$. Enforcing this condition for $t-2k$ consecutive partial rounds generates exactly $t-2k$ strictly linear constraints on $X_1$.

Varying the target tuple $\Delta = (\delta^{(1)}, \ldots, \delta^{(t-2k)})$ generates distinct solution subspaces. The union of these disjoint affine subspaces spans the original, unconstrained solution space.

5.3 Backward Linearization of the Initial Full Round

To prepend GSR with an additional full round we consider the $t$ variables of $X_1$. The $k$ predefined input constraints of the CICO-$k$ problem must be satisfied. Tracing backward, the state before the first MDS matrix is $M^{-1}X_1$. The state at the beginning of the round is:

$S_{in}[j] = (M^{-1}X_1)[j]^{1/\alpha} - C^{(0)}[j]$

To enforce the constraint $S_{in}[j] = 0$ for $k$ indices, we require:

$(M^{-1}X_1)[j] = (C^{(0)}[j])^\alpha$

Evaluating the known constant $(C^{(0)}[j])^\alpha$ circumvents the non-linear compositional inverse power map $x^{1/\alpha}$ of the S-box. This yields exactly $k$ more strictly linear equations in terms of $X_1$.

In total, we consume $t-2k$ DoFs in $X_1$ and leave it reduced to a linear combination of $k$ variables. Since there are exactly $k$ output constraints to satisfy, the system becomes determined (i.e., a zero-dimensional ideal) and is expected to have one valid solution.

6Using GSR to Attack Poseidon

By successfully bounding the polynomial degree through the GSR gadget, we translate the Poseidon's CICO-$k$ solution recovery problem into a highly constrained system of low-degree multivariate polynomials. This system only consists of the remaining unskipped partial and full rounds. Depending on the subspace dimension $k$, we deploy specific algebraic techniques to extract the roots, thereby recovering the complete initial state.

6.1 A $k$-Dimensional Distinguishing Attack for $t-2k+1$ Rounds

We have imposed $t-2k$ forward constraints and $k$ backward constraints on $X_1$. The total number of linear constraints is $k + (t-2k) = t-k$. Subtracting these constraints from the $t$ variables of $X_1$ leaves $k$ degrees of freedom. The solution space of $X_1$ forms a $k$-dimensional affine subspace:

$X_1(v_1,\ldots,v_k) = Z_{base} + \sum_{i=1}^{k} v_i B_i$

where $Z_{base} \in \mathbb{F}_p^t$ is a particular solution to the linear system, $B_i \in \mathbb{F}_p^t$ are the basis vectors of the null space, and $v_i$ are the $k$ free variables. This parameterization traverses one full round and $t-2k$ partial rounds with a polynomial degree of exactly 1. Solving this system requires negligible effort and forms a distinguisher for the middle $t-2k+1$ rounds of Poseidon. To the best of our knowledge, this is the longest distinguisher found for Poseidon.

Antonio Sanso revealed to the authors in private communications that he had also identified a similar distinguisher a couple of months earlier but did not pursue it on account of the distinguisher being "not interesting".

6.2 Attacking More Rounds and with $k \ge 1$

The GSR gadget allows, in simple terms, to express the last few rounds of the permutation as a linear combination of the rounds preceding the gadget. Effectively, as virtually all real-world instances of Poseidon consist of eight full rounds with a variable number of partial rounds, the gadget shrinks the original polynomial system significantly. Formally, the degree of the polynomial system reduces from $\alpha^{R_{f_0}+R_p+R_{f_1}}$ to $\alpha^{R_{f_0}+R_p+R_{f_1}-1-t+2k}$ using GSR.

6.2.1 Univariate Interpolation ($k = 1$, $R_{f_0} = 1$)

For $k = 1$ and $R_{f_0} = 1$, the target is parameterized by a single variable $v_1$, forming a univariate polynomial $f(v_1) = 0$. The forward cipher trajectory is evaluated from $S_{in}$ over $d+1$ numeric points in $\mathbb{F}_p$, and $f(v_1)$ is recovered via Lagrange interpolation. The roots are extracted using the Cantor-Zassenhaus algorithm. The degree of this univariate polynomial is strictly bounded by the remaining unskipped rounds i.e., $d \le \alpha^{R_p + R_{f_1} - t + 2k}$.

6.2.2 Bivariate Interpolation using Sylvester matrix ($k = 2$, $R_{f_0} = 1$)

For $k = 2$ and $R_{f_0} = 1$, the CICO system is parameterized by exactly two free variables, yielding a bivariate polynomial system $g_1(v_1,v_2) = 0$ and $g_2(v_1,v_2) = 0$ representing the two output constraints. Both $g_1$ and $g_2$ have degree $d \le \alpha^{R_p+R_{f_1}-t+2k}$. Such a system can be solved using the determinant of the Sylvester matrix [9, 11]. By treating $g_1$ and $g_2$ as polynomials in $v_2$ with coefficients in $\mathbb{F}_p[v_1]$, we compute the determinant of their Sylvester matrix (denoted $\mathrm{Res}(g_1,g_2,v_1)$), which by definition is equal to zero iff the two polynomials share common roots. This eliminates $v_2$, producing a univariate polynomial $\mathrm{Res}(g_1,g_2,v_1) = 0$ of degree $\le d^2$. Standard univariate root-finding algorithms can then be used to extract the valid candidates for $v_1$. Back-substituting these roots into $g_1$ yields a smaller $d$-degree univariate polynomial in $v_2$ which can be similarly solved, allowing us to perfectly recover the constrained initial state.

6.2.3 Generalizing $k > 2$ via Trivial Pairwise Resultants

For generalized instances where $k > 2$ and $R_{f_0} = 1$, we can iteratively apply the pairwise resultants over the output constraint equations. Let the $k$ output equations be $g_1, g_2, \ldots, g_k$ defined over $k$ variables $v_1, \ldots, v_k$. We group them in pairs and compute the resultants to eliminate $v_k$:

$h_i = \mathrm{Res}(g_i, g_{i+1}, v_k)$   for $i \in \{1, \ldots, k-1\}$

This yields $k-1$ equations in $k-1$ variables. Recursively applying this trivial pairwise elimination collapses the system into a single univariate polynomial in $v_1$. The roots are then extracted using the Cantor-Zassenhaus algorithm and iteratively back-substituted to solve the entire system.

However, we note that this trivial approach, despite being simple and computationally stable, is far from being optimal. The expected degree of the $k$-variate system with each polynomial of degree $d \le \alpha^{R_p+R_{f_1}-t+2k}$ is $\le d^k$, but this method will result in a univariate polynomial with degree $d^{2^{k-1}}$. Therefore for a given multivariate system defining a CICO-$k$ instance, one can find a threshold on $k$ after which the required complexity exceeds that of exhaustive search.

7Complexity Analysis and Comparison

We evaluate the computational advantage of the GSR gadget by analyzing the maximum algebraic degree of the polynomials in the reduced system. We contrast the complexity of solving the system naively (without partial round subspace restrictions) against our GSR-optimized approach.

7.1 Theoretical Degree Bounds

Baseline (Naive). Without S-box skipping in the partial rounds, the dense MDS matrix mixing ensures the degree rises by a factor of $\alpha$ per round. For $R_{f_0} = 1$, the maximum degree bounds strictly to $d_{naive} = \alpha^{1+R_p+R_{f_1}}$.

GSR. Applying the subspace restriction maintains a degree of exactly 1 through $R_{f_0}$ and the first $t-2k$ partial rounds. Degree growth only activates in the remaining unskipped partial rounds and the final full rounds. Thus, the degree is strictly truncated to $d_{opt} = \alpha^{R_p+R_{f_1}-t+2k}$.

7.2 Complexities of the Used Techniques

For the root extraction of a $d$-degree univariate polynomial with coefficients in $\mathbb{F}_p$, we use the Cantor-Zassenhaus [8, 15] algorithm that has practical bit complexity of $O(d^2 \log p)$ in runtime and $O(d \log p)$ in memory.

For two given $d$-degree multivariate polynomials over the same set of variables, the cost of computing their Sylvester matrix and defining the determinant as another $d^2$-degree multivariate polynomial (with strictly one less variable) is $\tilde{O}(d^3)$ bit operations in runtime and $O(d^2 \log p)$ bits in memory [11]. Iteratively, if we nest Sylvester resultant computation from $k$ $k$-variate polynomials all the way down to one univariate polynomial, the degree of the polynomial blows from $d$ to $d^{2^{k-1}}$ and cost of solving for a root becomes time $O(d^{2^k}\log p)$ and memory $O(d^{2^{k-1}}\log p)$.

7.3 State-of-the-Art vs. GSR on KoalaBear

We instantiate the bounds using Poseidon's KoalaBear parameters adopted by the Ethereum ecosystem: $p \approx 2^{31}$, $\alpha = 3$, and $t = 24$. Table 1 contrasts the computational complexity of extracting valid CICO solutions between the state-of-the-art approaches (no partial layer subspace restriction) and our proposed GSR framework using the combination of Sylvester resultant and Cantor-Zassenhaus, denoted SyCZ. Paired entries $(x,y)$ denote the time and memory bit-complexities, respectively.

Target	$(R_{f_0},R_p,R_{f_1})$	Brute-force	SyCZ (baseline)	SyCZ (GSR)
CICO-1 (k=1)	(1, 23, 4) = 28	$2^{31}$	$(2^{93.7}, 2^{49.3})$	$(2^{20.8}, 2^{12.9})$
CICO-2 (k=2)	(1, 23, 4) = 28	$2^{62}$	$(2^{182.5}, 2^{93.7})$	$(2^{49.3}, 2^{27.1})$
CICO-2 (k=2)	(1, 20, 4) = 25	$2^{62}$	$(2^{163.4}, 2^{84.2})$	$(2^{30.3}, 2^{17.6})$
CICO-3 (k=3)	(1, 18, 4) = 23	$2^{93}$	$(2^{296.6}, 2^{150.8})$	$(2^{55.7}, 2^{30.3})$
CICO-4 (k=4)	(1, 16, 4) = 21	$2^{124}$	$(2^{537.5}, 2^{271.2})$	$(2^{106.4}, 2^{55.7})$
CICO-5 (k=5)	(1, 14, 2) = 17	$2^{155}$	$(2^{867.2}, 2^{436.1})$	$(2^{106.4}, 2^{55.7})$
CICO-6 (k=6)	(1, 12, 1) = 14	$2^{186}$	$(2^{1425.1}, 2^{715.0})$	$(2^{106.4}, 2^{55.7})$
CICO-7 (k=7)	(1, 10, 1) = 12	$2^{217}$	$(2^{2439.4}, 2^{1222.2})$	$(2^{207.8}, 2^{106.4})$

Table 1: Complexity comparison of CICO-$k$ solution recovery on Poseidon's KoalaBear instance ($t = 24$, $\alpha = 3$). For $k \ge 5$, $R_{f_1}$ is successively reduced to 2 and then to 1 to show the $R_{f_1}$ threshold where SyCZ-with-GSR remains faster than the respective $2^{31k}$ brute-force bound.

Analysis for $k=1$. The baseline algebraic degree scales up to $d_{naive} = 3^{28} \approx 2^{44.4}$, giving $(2^{93.7}, 2^{49.3})$ — heavily inferior to the simple $2^{31}$ brute-force cost. With GSR we systematically skip $t-2k = 22$ partial rounds, leaving only $23-22 = 1$ active partial round. The degree bound drops sharply to $d_{opt} = 3^{1+4} = 3^5 \approx 2^{7.9}$, and the extraction complexity to just $(2^{20.8}, 2^{12.9})$, executing entirely in milliseconds.

Analysis for $k=2$. For the $(1,20,4)$ instance, root finding without structural restriction projects a huge degree of $(3^{25})^2 = 3^{50} \approx 2^{79.3}$ for the Sylvester resultant univariate polynomial, dictating $(2^{163.4}, 2^{84.2})$. Against a $2^{62}$ brute-force cost, the naive approach therefore provides no practical attack vector. With GSR we absorb exactly $t-2k = 20$ partial rounds, leaving $20-20 = 0$ active partial rounds. The equation degree drops to $d_{opt} = 3^{0+4} = 3^4 \approx 2^{6.3}$, and the Sylvester matrix projection computes the roots with a final complexity of $(2^{30.3}, 2^{17.6})$ — an attack that runs within a minute and handily beats generic $2^{62}$ brute-force.

8Conclusion

In this paper, we introduced Generalized S-Box Skipping via Subspace Restriction (GSR), a novel algebraic technique that significantly advances the cryptanalysis of the Poseidon hash function. By strategically targeting S-boxes within the partial layer rather than confining the restriction to the initial full rounds, GSR effectively neutralizes the dense MDS mixing that typically drives exponential polynomial degree growth.

This structural exploitation allowed us to translate the mathematically challenging CICO-$k$ problem into tractable, low-degree polynomial systems. We practically demonstrated the power of this approach by recovering valid CICO-1 and CICO-2 solutions over 28 and 25 rounds, respectively, (out of the recommended 31) of Poseidon's KoalaBear instance in negligible time.

In summary, GSR exposes a critical vulnerability in the partial layer of Poseidon (and related AO ciphers), emphasizing the need for a rigorous reevaluation of its algebraic security margins.

Responsible Disclosure. This work was supported by the Ethereum Foundation Grant program through grant number FY26-2457 and the VLAIO Baekeland mandate under project number HBC.2024.0256. The results were disclosed to the Ethereum Foundation prior to their public dissemination.

Rendered as an annotated reading of ePrint 2026/1692. Prose is the authors'; the side notes are commentary and are not part of the paper.