Time: 2025.03.29-31 (online)
fairy-ring (7 solves)
https://github.com/defund/ctf/tree/master/dicectf-quals-2025/fairy-ring
Also check this defund’s gift and this Improved cryptanalysis of UOV and Rainbow!
A good chance to learn more about MQ and UOV.
Multivariate Quadratic
A Multivariate Quadratic (MQ) is a polynomial in $n$ variables over $\mathbb{F_q}$: $f(x_1, …, x_n) = \sum_i^n \sum_j^n a_{i,j} x_i x_j + \sum_i^n b_{i} x_i + c$. We can represent it with matrix: $f(\vec{x}) = \vec{x}^\top A \vec{x} + \vec{b}^\top \vec{x} + c$.
A Multivariate Quadratic Map $\mathcal{F}: \mathbb{F_q^n} \rightarrow \mathbb{F_q^m}$ is a collection of such polynomials $f_1, …, f_m$ where:
$$\mathcal{F}(\vec{x}) = (f_1(\vec{x}), …, f_m(\vec{x}))$$
Multivariate Quadratic Problem (MQP): Given arbitrary $\mathcal{F}: \mathbb{F_q^n} \rightarrow \mathbb{F_q^m}$ and $\vec{t} \in \mathbb{F_q^m}$, it’s NP-hard to find $\mathcal{F}(\vec{s}) = \vec{t}$.
Polar Form
It’s clear that:
$$
\begin{aligned}
f(\vec{x} + \vec{y}) &= (\vec{x} + \vec{y})^\top A (\vec{x} + \vec{y}) + \vec{b}^\top (\vec{x} + \vec{y}) + c \\
&= f(\vec{x}) + f(\vec{y}) - f(\vec{0}) + \vec{x}^\top (A + A^\top) \vec{y} \\
\end{aligned}
$$
And we have the polar form: $f’(\vec{x}, \vec{y}) = \vec{x}^\top (A + A^\top) \vec{y} = f(\vec{x} + \vec{y}) - f(\vec{x}) - f(\vec{y}) + f(\vec{0})$. This also works for a Multivariate Quadratic Map: $\mathcal{F}’(\vec{x}, \vec{y}) = \mathcal{F}(\vec{x} + \vec{y}) - \mathcal{F}(\vec{x}) - \mathcal{F}(\vec{y}) + \mathcal{F}(\vec{0})$.
Words
We mainly focus on the quadratic part of a MQ, which serves as the core of the hardness. So we usually have $f(\vec{x}) = \sum_i^n \sum_j^n a_{i,j} x_i x_j = \vec{x}^\top A \vec{x}$. One can always find a symmertric $A$ since $\vec{x}^\top A \vec{x} = \vec{x}^\top A^\top \vec{x} = \vec{x}^\top (\frac{A + A^\top}{2}) \vec{x}$. We can further simplify $A$ into a upper triangular matrix, which is more intuitive and leads to less storage overhead.
And the polar form: $f’(\vec{x}, \vec{y}) = f(\vec{x} + \vec{y}) - f(\vec{x}) - f(\vec{y})$.
UOV Signature
The Unbalanced Oil and Vinegar (UOV) scheme is a signature scheme based on MQ.
First we construct an easy-to-solve MQ $f(\vec{x}) = \sum_i^n \sum_{j > m}^n a_{i,j} x_i x_j$. Here we call oil variables $\vec{x_o} = (x_1, …, x_m, 0, …, 0)$ and vinegar variables $\vec{x_v} = (0, …, 0, x_{m+1}, …, x_{m+v})$ (where $n = m+v$), and it’s clear that $\mathcal{F}$ is linear to $\vec{x_o}$. By randomly choosing $\vec{x_v}$, one can solve the linear system to get the answer.
Matrix form:
$$
A = \begin{bmatrix}
O_{m \times m} & B_{m \times v} \\
O_{v \times m} & C_{v \times v}
\end{bmatrix}
\rightarrow
(\vec{x_o} + \vec{x_v})^\top A (\vec{x_o} + \vec{x_v}) = \vec{x_o}’^\top B \vec{x_v}’ + \vec{x_v}’^\top C \vec{x_v}’
$$
Polar form:
$$
\mathcal{F}(\vec{x_o}) = \vec{0} \rightarrow \mathcal{F}(\vec{x_o} + \vec{x_v}) = \mathcal{F}’(\vec{x_o}, \vec{x_v}) + \mathcal{F}(\vec{x_v})
$$
In UOV, we use $\mathcal{F}$ as the private key and the public key is $\mathcal{P} = \mathcal{F} \circ \mathcal{T}$, where $\mathcal{T}$ is an invertable linear transformation. For a message $m$, the signature $\vec{s}$ satisfies $\mathcal{P}(\vec{s}) = \mathcal{Hash}(m)$. The signer just solves $\mathcal{F}(\vec{x}) = \mathcal{Hash}(m)$ and computes $\vec{s} = \mathcal{T}^{-1}(\vec{x})$.
The main idea is to find a linear space $\mathcal{O}$ with rank $r \geq m$, and for all $\vec{o} \in \mathcal{O}$ we have $\mathcal{P}(\vec{o}) = \vec{0}$. It’s also worth mentioning that for any valid signature $\vec{s}$, $\vec{s} + \mathcal{O}$ is still valid.
Ring Signature
In this challenge, we have a ring signature scheme based on UOV. Any one of the $n$ users can generate a signature on behalf of the group, and no one can distinguish the signer.
- $\mathcal{Setup}:$ Each user generates a UOV key pair $(\mathcal{P}, \mathcal{F})$.
- $\mathcal{Sign}:$ For message $m$, user $a$ randomly chooses $(\vec{x_1}, …, \vec{x_{a-1}}, \vec{x_{a+1}},…, \vec{x_n})$ and compute $\vec{t} = \mathcal{Hash}(m) - \sum_{i \neq a}^n \mathcal{P_i}(\vec{x_i})$. Then user $a$ solve $\mathcal{P_a}(\vec{x_a}) = \vec{t}$ with the private key $\mathcal{F_a}$. The signature is $(\vec{x_1}, …, \vec{x_n})$.
- $\mathcal{Verify}:$ Check whether $\mathcal{Hash}(m) = \sum_{i}^n \mathcal{P_i}(\vec{x_i})$ satisfies.
Solution
The solution is easy but elegant.
We can pick the same public key more than once, and actually it’s possible for us to forge a valid signature for any message (yeah it’s completely broken). Consider a public key $\mathcal{P}$, we have
$$\vec{t} = \mathcal{P}(\vec{x} + \vec{y}) - \mathcal{P}(\vec{x}) = \mathcal{P}’(\vec{x}, \vec{y}) + \mathcal{P}(\vec{y})$$
Here $\vec{t}$ is linear to $\vec{x}$, that’s all we need to solve this challenge. For a given message $m$, we can pick the same public key $\mathcal{P}$ twice, then randomly choose a $\vec{y}$ and find the solution $\mathcal{Hash}(m) = \mathcal{P}(\vec{x} + \vec{y}) - \mathcal{P}(\vec{x})$ (it’s the same for ‘$+$’ and ‘$\oplus$’ on $\mathbb{F_{2^8}}$). And $(\vec{x} + \vec{y}, \vec{x})$ is a valid signature.