Problem analysis
As a complement to this problem analysis, I strongly recommend to read this article (full quote at the end of the write-up) at least until the section 4 (not included). Moreover, results of this article will be used to solve this challenge.
We have a function called $AOP: \mathbb{F}_p^5 \to\ \mathbb{F}_p^5$ ($p$ is a 64 bit prime), we want to find a $X = (X_1, \ldots, X_5)\in \mathbb{F}_p^5$ such that $X_1 = 0$ and $Y = (Y_1, \ldots, Y_5) = AOP(X)$ such that $Y_1 = 0$.
This problem is called a CICO (Constrained Input, Constrained Output) problem.
In a more formal way, let $\mathbb{F}_q$ be a field. We define a vector space $\mathbb{F}_q^n$ spanned by the basis $(e_1, \ldots, e_n)$ where $e_i$ is the vector with all coefficients set to zero except the i-th one that is set to one. We define $\mathcal{F}_k = Vec(e_k, \ldots, e_n)$.
Let $f : \mathbb{F}_q^n \to \mathbb{F}_q^n$, then the CICO problem is about finding a $x\in\mathcal{F}_k$ such that $f(x) \in \mathcal{F}_k$.
Let see in details the round function :
$\sigma_r(X_1, \ldots, X_5) = (X_1^e, X_2, \ldots, X_5)$ where $e = 3^{-r} \mod p-1$.
So, for the $r$-th round, we have a invertible matrix $M \in \mathcal{M}_{5,5}(\mathbb{F}_p)$ a function $\sigma_r$ and a vector of round constants $R_r \in \mathbb{F}_p^5$.
For an input vector $I = (X_1, \ldots, X_5)$, the round is the function $Q_r = \sigma_r(MI + C)$.
Note that this round function can be expressed with five polynomials $P_{1,r}, \ldots, P_{5,r} \in \mathbb{F}_p[X_1, \ldots X_5]$ such that:
$Q_r = (P_{1,r}, P_{2,r}, P_{3,r}, P_{4,r}, P_{5,r})$.
This representation will be useful to solve the challenge. Indeed, it allows to represent an arbitrary number of round of $AOP$ as five multivariate polynomials in $X_1,\ldots,X_5$, i.e the input vector of $AOP$.
As an example, let $(X_1, \ldots, X_5)$ be the input vector.
- The output of the first round of $AOP$ is $Y = Q_1(X_1, \ldots, X_5) = (Y_1, \ldots, Y_5) = (P_{1,1}(X_1, \ldots, X_5), \ldots, P_{5, 1}(X_1, \ldots, X_5))$
- The output of the second round is $Z = Q_2(Y_1, \ldots, Y_5) = (Z_1, \ldots, Z_5) = (P_{1, 2}(Y_1, \ldots, Y_5), \ldots, P_{5, 2}(Y_1, \ldots, Y_5))$
- And so on,….
Potential attacks
Let try to figure out how to handle this challenge.
- Can we brute-force it ? While all computations can be done offline, we work over $\mathbb{F}_p^5$ with $p$ a 64 bits prime. According to the paper, by choosing random candidates for the CICO problem,this can be done in $\mathcal{O}(p)$. This is way too big regarding that $p$ is 64 bits.
- We can try to do better than brute-force. We can find the polynomial $P\in\mathbb{F}_p[X_1, \ldots, X_5]$ that represents the first coefficient of the output of $AOP$ regarding the input vector $(X_1, \ldots, X_5)$ and trying to compute its roots.
- Pray to find the right paper.
Polynomial representation of $AOP$
This is an important step, because our solution will surely involve a polynomial representation of $AOP$.
Unfortunatly, I can’t represent more than four rounds of $AOP$ (there is 9 rounds in total) using sage because the degree is too high. To lower the degree of the representation, we can instead consider the inverse of $AOP$ (let call this $AOP^{-1}$), that has a degree way lower than $AOP$. The problem remains the same, found $Y\in\mathcal{F}_k$ such that $AOP^{-1}(Y) \in \mathcal{F}_k$. However, it is not sufficient to represent the full $AOP^{-1}$, the degree is still too high.
This is where we read again the paper that I mentioned in the problem analysis section.
This paper explains two things about (a generalized version of) the problem we’re facing :
- How to find a solution of the CICO problem by solving a univariate polynomial equation instead of a multivariate one,
- How to bypass some rounds, allowing to lower the degree of the polynomial.
Full solve
Recall that we want to find a vector $X \in \mathcal{F}_1$ such that $AOP^{-1}(X) \in \mathcal{F}_1$.
First, let’s define the parameters in sage :
# Parameters of AOP
p = 18446744073709551557
t = 5
r = 9
# We work in F_p
F = GF(p)
# The round constants
RC = [
vector([ F(int.from_bytes(sha256(b"FCSC2024#" + str(t*j + i).encode()).digest())) for i in range(t) ])
for j in range(r)
]
# The diffusion matrix
M = Matrix(F, [
[ pow(i, j, p) for i in range(1, t + 1) ]
for j in range(t)
])
M_inv = M.inverse()
Then write the round function of $AOP$ and $AOP^{-1}$ in sage :
# The round function
# exp parameter will be useful
def round_f(state, r, exp=True):
# state <- state * M
state = state * M
# state <- state + RC[r]
state += RC[r]
# state <- state ** e
if exp:
e = pow(3, -r, p-1)
state[0] = state[0] ^ e
return state
# The inverse round function
def round_f_inv(state, r):
# state <- state ** (1/e)
if exp:
e = pow(3, -r, p-1)
e_inv = pow(e, -1, p-1)
state[0] = state[0] ^ e_inv
# state <- state - RC[r]
state -= RC[r]
# state <- state * M^{-1}
state = state * M_inv
return state
Now we are able to represent round by round $AOP$ and $AOP^{-1}$ using polynomials.
What’s next ? Well, we need to take a look at the article because it explains how to both skip rounds of our challenge and also to solve a univariate system rather than a multivariate one.
As explained in the article [1] at Section 4.2, we can bypass at least one round (the first one) by expressing $AOP^{-1}$ as $AOP^{-1} = \pi_0\circ\pi_1$ where $\pi_0$ is the first round of $AOP^{-1}$ and $\pi_1$ the remaining rounds of $AOP^{-1}$.
Here’s the trick :
- we search for two vectors $G, V\in\mathbb{F}_p^5$ with $V = (0, V_2, V_3, V_4, V_5)$ and $G = (G_1, 0, \ldots, 0)$ such that $\forall x \in \mathbb{F}_p, \pi_0^{-1}(xV + G) \in \mathcal{F}_1$.
- Once this step is done, we have fixed vectors for $V$ and $G$ and only one unkown : $x$. We solve $\pi_1(xV + G) = 0$ (which is equivalent to find a root of a univariate polynomial over $\mathbb{F}_p[X]$)
First part of the trick :
# At first, g1, v2, ..., v5 are unknowns
R.<x, g1, v2, v3, v4, v5> = PolynomialRing(F)
# For when we will go to univariate
R2.<y> = PolynomialRing(F)
# state_m1 = pi_0^{-1}(XV + G)
state_m1 = round_f(
state=vector([g1, v2*x, v3 * x, v4 * x, v5 * x]),
r=8,
exp=False # avoid exponent overflow error
)
We obtain $state_m1 = (XV_2 + XV_3 + XV_4 + XV_5 + G_1 + 18149433503814401207, \ast, \ast, \ast, \ast)$
We want the first coordinate equals to zero, for simplicity, I set $G_1 = -18149433503814401207 \in \mathbb{F}_p$ and $V_2 = -V_3 - V_4 - V_5$ and we got the first coordinate equals to 0.
In sage :
state_output = state_m1(g1=-18149433503814401207, v2=(-v3 - v4 - v5))
So, we have a general expression in $V_3, V_4, V_5$ that leads to a zero in the first coordinate.
Second step of the trick :
Now we start to apply the inverse rounds to our state_output :
state_8 = round_f_inv(
state=copy(state_output),
r=8)
# We have state_8 = xV + g
state_7 = round_f_inv(
state=copy(state_8),
r=7)
At this point, $state_7 = (20XV_3 + 5XV_4 + 11XV_5 + 13165686892553568318, \ast, \ast , \ast, \ast)$ What we want is to lower the degree of this as much as possible to solve more easily the polynomial equation at the end and eliminate the variables $V_i$.
We set $P(V_3, V_4, V_5) = 20V_3 + 5V_4 + 11V_5$ to lower the degree at the next round and get rid of $V_3$, we can set $V_3 = aV_4 + bV_5$ such that $P(X, V_3, V_4, V_5) = 0$. To do so, we compute the gröbner basis of the ideal $\mathbb{F}_p[V_3, V_4, V_5]/P$ :
b = ideal(P).groebner_basis()
We have $b = \lbrace V_3 + 13835058055282163668V_4 + 15679732462653118824V_5 \rbrace$ so we set $V_3 = -(13835058055282163668V_4 + 15679732462653118824V_5)$ and we got $state_7 = (13165686892553568318, \ast, \ast, \ast, \ast)$
state_7 = state_7(v3 = -(13835058055282163668*v4 + 15679732462653118824*v5))
# now state_7 = (13165686892553568318, *, *, *, *)
Then, we can apply again the round function of $AOP^{-1}$ :
state_6 = round_f_inv(
state=copy(state_7),
r=6)
We repeat the same previous process to $state_6 = (6533221859438799463XV_4 + 11144907877866187383XV_5 + 14198193969758665933, \ast, \ast, \ast, \ast)$ :
P = 6533221859438799463*v4 + 11144907877866187383*v5
b = ideal(P).groebner_basis()
We obtain $b = \lbrace V_4 + 3434627627087123631V_5 \rbrace$ so we set $V_4 = -3434627627087123631V_5$ and apply again the round function of $AOP^{-1}$.
state_6 = state_6(v4 = -3434627627087123631*v5)
state_5 = round_f_inv(
state=copy(state_6),
r=5)
We get $state_5 = (7991135467095564677XV_5 + 7452441470924312017, \ast, \ast, \ast, \ast)$. Because there is only $V_5$ remaining, we can freely set it to a non-zero constant, I choose $V_5 = 1$, but I’m almost sure that any other value will achieve the same (maybe set $V_5$ to the inverse of $7991135467095564677 \mod p$ will more efficient for the remaining computations ?). Once this is done, we are left with only one variable : $X$, so we can change in sage the ring to a univariate polynomial ring to speed-up computation.
state_5 = state_5(v5=1)
# Change to univariate ring
state_5 = state_5(x=y)
We already applied 4 rounds of $AOP^{-1}$, 5 more are remaining, but now we fully compute each round in the univariate ring $\mathbb{F}_p[Y]$, which is way easier.
# compute the remaining rounds
state_4 = round_f_inv(
state=copy(state_5),
r=4)
state_3 = round_f_inv(
state=copy(state_4),
r=3)
state_2 = round_f_inv(
state=copy(state_3),
r=2)
state_1 = round_f_inv(
state=copy(state_2),
r=1)
state_0 = round_f_inv(
state=copy(state_1),
r=0)
Recall that we want the first coordinate of state_0 to be zero. Let $P(Y)$ be the polynomial at the first coordinate of state_0. We are seeking for a root of $P$. But $P$ has a lot of terms and a high degree, we can’t simply compute its roots by a P.roots() in sage. Instead, we can use the method described in the paper on finding roots of univariate polynomial :
- Compute $Q = Y^p-Y$ in $F_p[Y]/P$ (i.e $Q = Y^p - Y \mod P$)
- Compute $R = gcd(P, Q)$
- Compute the roots of $R$, these are roots of $P$ too.
Why are we doing that ? If I understand well, according to this paper [2], the first two steps allows to get the squarefree split part of $P$. It implies that $\deg(R) \leq \deg(P)$, in practice $\deg(R) \ll \deg(P)$. Moreover, $R|P$ so if we found a root of $R$, then it will be a root of $P$.
# New ring : F_p[Z]/P
I = ideal(P)
R3 = R2.quotient_by_principal_ideal(I)
z = R3.gens()[0]
# Q = z^p - z mod P
Q = z^p - z
# Go back in F_p[Y]
# Crappy trick to go back to R2...
coeff = Q.list()
Q = 0
for i in range(len(coeff)):
print(round(float(i/len(coeff)), 2), end="\r")
Q += coeff[i] * y^i
# R = gcd(P, Q)
R = gcd(P, Q)
roots = R.roots(multiplicities=False)
We have two roots (let say $r_1$ and $r_2$) of R (which is a degree-2 polynomial). We can take the first one.
Now, if we set $Y$ to $r_1$, then the first coordinate of state_0 will be zero !
Ok, so in a nutshell, we found a way to express the first coordinate of the output state of $AOP^{-1}$ as an univariate polynomial $P(Y)\in\mathbb{F}_p[Y]$ such that the first coordinate of the input state of $AOP^{-1}$ will be zero. Furthermore, we know two roots $r_1, r_2$ of $P$, which means that we are able to get the first coordinate of the output of $AOP^{-1}$ to be zero : we solve the CICO problem for $AOP^{-1}$
But wait, we want to solve it for $AOP$, not $AOP^{-1}$ ? Well, this equivalent : the valid output state of $AOP^{-1}$ is a valid input state for $AOP$. Lets check this :
# len(roots) == 2
X = state_0(y=roots[0])
# Lets check :
from appellation_origine_protegee import AOP
aop = AOP()
print(aop(list(X)))
# Trust me : it works ;)
We just have to give each coordinate of $X$ evaluated in $r_1$ (coma-separated) to the challenge to get the flag !
Bibliography
[1] Bariant, A., Bouvier, C., Leurent, G., & Perrin, L. (2022). Algebraic Attacks against Some Arithmetization-Oriented Primitives. IACR Transactions on Symmetric Cryptology, 2022(3), 73-101. https://doi.org/10.46586/tosc.v2022.i3.73-101
[2] Petit, C. (2014). Finding Roots in Fpn with the Successive Resultants Algorithm. LMS journal of computation and mathematics, 17, SPEC. ISSUE A, page (203-217). https://dx.doi.org/10.1112/S1461157014000138