A Full-Round Collision in Poseidon

Anthropic’s HAWK post showed that LLMs can do actual cryptanalysis research. Since then, we have been exploring LLM-based cryptanalysis across a range of targets.

With ChatGPT Pro, we constructed a full 28-round collision for the Poseidon Cryptanalysis Initiative’s Poseidon1 Collision challenge. Two distinct messages with the required prefix produce identical 16-word outputs under the challenge’s reference implementation.

The challenge

In this challenge, the Poseidon function operates over the prime field $\mathbb F_p$, where $p=2^{31}-2^{24}+1$, with a 16-word state in $\mathbb F_p^{16}$. Its 28 rounds consist of four full rounds, twenty partial rounds, and four more full rounds.

If $x_r$ is the state entering round $r$, then

$$x_{r+1}=M S_r\left(x_r+c^{(r)}\right),$$

where $c^{(r)}$ is the public round constant and $S_r$ is the full or partial S-box layer.

A full-round S-box layer cubes every coordinate, whereas a partial-round layer cubes only coordinate 0.

Write $P_M$ for the complete 28-round permutation. The challenge uses feed-forward compression:

$$H_M(X)=P_M(X)+X.$$

The full-collision goal is to find two distinct inputs $X^+$ and $X^-$ such that

$$X_0^+=X_0^-=\texttt{0xc09de4}, \qquad H_M(X^+)=H_M(X^-).$$

The challenge allowed submitters to choose the MDS matrix $M$. We designed the collision first and the matrix second: we constructed two state trajectories that collide, then solved for the linear map $M$ that realizes them.

Decoupling midpoint and difference

Let $x_r^+$ and $x_r^-$ be the two states entering round $r$, with $x_0^+=X^+$ and $x_0^-=X^-$. Define their midpoint $m_r$ and half-difference $d_r$ by

$$m_r=\frac{x_r^++x_r^-}{2}, \qquad d_r=\frac{x_r^+-x_r^-}{2}.$$

Equivalently, $x_r^+=m_r+d_r$ and $x_r^-=m_r-d_r$.

If the permutation ends with

$$m_{28}=0, \qquad d_{28}=-d_0,$$

then $P_M(X^+)=-d_0$ and $P_M(X^-)=d_0$. Feed-forward gives

$$H_M(X^+)=m_0+d_0-d_0=m_0, \qquad H_M(X^-)=m_0-d_0+d_0=m_0,$$

so $H_M(X^+)=H_M(X^-)$.

Our construction uses two mechanisms:

1. reset the midpoint to zero;

2. keep control of the half-difference and return it with the opposite sign.

Together, these two mechanisms give 16 linear constraints on the same matrix $M$: 14 from the midpoint reset and 2 from controlling the half-difference. These 16 constraints uniquely determine $M$.

Mechanism 1: Resetting the midpoint

The first key intuition is to constrain $M$ so that the midpoint ($m_r$) at every even round entry becomes zero. This is possible because the cubic S-box is odd: if its two inputs are exact opposites, its outputs are also exact opposites, so their midpoint is zero.

After adding $c^{(r)}$, the midpoint immediately before the first S-box is $s_r=m_r+c^{(r)}$. Let the midpoint after that S-box be

$$u_r=\frac{S_r(s_r+d_r)+S_r(s_r-d_r)}{2}.$$

If the matrix satisfies

$$Mu_r=-c^{(r+1)},$$

then the midpoint after $M$ is $-c^{(r+1)}$. Adding $c^{(r+1)}$ turns it into $0$.

The second S-box therefore sees exact opposites. Cubing preserves that relation, and multiplying by $M$ preserves it again, so the block ends with

$$m_{r+2}=0.$$

There are fourteen two-round blocks, so the reset eventually gives fourteen requirements

$$Mu_0=-c^{(1)},\quad Mu_2=-c^{(3)},\quad \ldots,\quad Mu_{26}=-c^{(27)}.$$

At this point, these are only requirements. The vectors $u_r$ depend on the half-differences entering the blocks, so they cannot be computed until the difference has been designed. We therefore leave the matrix aside and determine the half-differences first.

Mechanism 2: Keeping the difference on one coordinate

We force the half-difference at every even-round boundary to be nonzero only in coordinate 1:

$$d_r=\beta_r e, \qquad e=(0,1,0,\ldots,0),$$

where $\beta_r$ is the scalar amplitude of the half-difference.

During the twenty partial rounds, we keep the even-round half-difference equal to $-ae$ for one nonzero field element $a$. The key is to arrange the twenty partial rounds so that the same two-round differential pattern can be repeated throughout.

Choose a vector $v=(v_0,\ldots,v_{15})$ with

$$v_i\in\{a^{-1},-a^{-1}\}\qquad(i=1,\ldots,15),$$

while $v_0$ remains free. Let $w$ be the vector determined by what the second partial S-box does when the midpoint is zero:

$$-av\xrightarrow{\text{partial S-box}}-aw.$$

This mechanism contributes exactly two constraints on $M$:

$$Me=v,\qquad Mw=e.$$

The same two constraints will be reused in every pair of partial rounds.

Now we can see the pattern of half-difference during one pair of partial rounds:

$$\boxed{ -ae \xrightarrow{\text{partial S-box}} -ae \xrightarrow{M} -av \xrightarrow{\text{partial S-box}} -aw \xrightarrow{M} -ae. }$$

The full two-round blocks work similarly. The half-difference remains on coordinate 1, but its amplitude changes.

Building the trajectories

$m_r$ and $d_r$ determine $x_r^{+}, x_r^{-}$, and we already know $m_2 =m_4 = \cdots =m_{28} = 0$ and $d_r$ is determined by $\beta_r$. Therefore, we will build the solution by fixing $\beta_r$.

First, choose a nonzero field element $a$ at random and set $\beta_4=\beta_6=\cdots=\beta_{24}=-a$. We can show that once $a$ is chosen, $\beta_{26}$ and $\beta_{28}$ are already fixed as well. Also, feed-forward requires the initial amplitude to be the negative of the final one, so

$$\beta_0=-\beta_{28}.$$

We then solve for the amplitude immediately before the partial rounds. For the block covering rounds 2 and 3, the following relation must hold:

$$\beta_2^3 +3\left((c^{(2)})_1\right)^2\beta_2 =-a.$$

A root in $\mathbb F_p$ gives $\beta_2$. Finally, the first block has both endpoint amplitudes determined, $\beta_0$ and $\beta_2$. Its equation determines the required coordinate-1 value of the initial midpoint $m_0$.

The resulting sequence is shown below.

If one of the required root conditions fails, we try another $a$. The remaining coordinates of $m_0$, the active coordinate $v_0$, and the passive signs of $v$ are still available when constructing the matrix.

Constructing the matrix

Now all conditions are known. At even rounds $2,\ldots,26$, the midpoint is zero, and every half-difference is the known value $\beta_r e$. Together with the selected initial midpoint, this determines the midpoint immediately after the first S-box in every block.

The fourteen midpoint requirements and the two difference requirements are

$$Mu_r=-c^{(r+1)} \quad (r=0,2,\ldots,26), \qquad Me=v, \qquad Mw=e.$$

Collect their sixteen source vectors and targets as the columns of two $16\times16$ matrices:

$$U=\left[\,u_0\mid u_2\mid\cdots\mid u_{26}\mid e\mid w\,\right],$$ $$V=\left[\,-c^{(1)}\mid-c^{(3)}\mid\cdots\mid-c^{(27)}\mid v\mid e\,\right].$$

The first fourteen columns encode the midpoint resets, while the last two encode difference control.

All requirements are contained in $MU=V$. If $U$ is invertible, exactly one matrix satisfies them:

$$M=VU^{-1}.$$

Note: $M$ is not automatically MDS (equivalently, every square submatrix is nonsingular), nor is it guaranteed to pass the linear-layer checks. Those properties are filters. When we experimented with random $a$, more than 30% of attempts produced a valid trajectory (that is, the equations had a solution) and an MDS matrix that passed the Initiative’s checks.

Verification

We verified that the witness passes the Initiative’s verifier, and independently checked that $M$ is MDS. The GitHub repository contains the matrix, both inputs, and the verification code.

The construction relies on choosing $M$. After reviewing this class of custom-matrix submissions, the Poseidon Group said that these submissions were outside the intended scope of the main bounty. They nevertheless described the submissions as highlighting a previously unexplored attack vector and offered us a special US$10,000 ex gratia payment.

What the construction shows

This is a failure mode of adaptive parameter selection. The round constants are not individually weak, and the matrix passes the required matrix-level checks. The collision comes from their correlation: the matrix was constructed as a function of the already specified round constants.

This does not apply when the matrix is specified, as in deployed Poseidon instances. A related parameter-selection viewpoint appeared independently in Slipway through a different Poseidon attack mechanism.

Takeaway

Since then, we have kept working on cryptanalysis using LLMs and found several meaningful results: Witness Encryption Scheme Based on Affine Determinant Programs, a major witness-encryption candidate, and A Key-Recovery Attack on TALUS v4, a candidate for the NIST post-quantum threshold call.

Cryptography broadly is moving fast right now. The McEliece cryptosystem, unbroken for nearly 50 years, is now under real cryptanalytic pressure. A claimed polynomial-time quantum algorithm for the Dihedral Coset Problem, which would have broken the lattice assumptions behind ML-KEM and ML-DSA, was soon refuted. Three independent teams found new attacks on Poseidon within weeks of each other.

At the same time, AI-assisted research is making SHA/BLAKE proving much faster, as Flock and the SNARK.fast challenge demonstrate. Justin Drake announced Ethereum’s planned move from Poseidon to SHA/BLAKE at L1. With LLMs, more efficient cryptography will emerge and will be contested super hard, and only the safe ones will survive.