I played Hitcon CTF last weekend with r3kapig, enjoyed.
MRSA
In this challenge, we need to recover a $k \cdot k$ small (8bit) secret matrix $M$ with $C = M^e \pmod{n}$, where $n$ is omitted.
Our Solution
We implemented our solution based on the truth that $M \cdot C = C \cdot M \pmod{n}$, which gives us $k \cdot k$ equations about $M$. Take a certain position $(i, j)$ as an example:
$$
\begin{aligned}
(M \cdot C)[i, j] &= (C \cdot M)[i, j] \pmod{n} \\
M[i] \cdot C^T[j] &= C[i] \cdot M^T[j] \pmod{n} \\
&\Rightarrow \\
t_{i, j} \cdot n &= M[i] \cdot C^T[j] - C[i] \cdot M^T[j]
\end{aligned}
$$
And we can construct an equation on $\mathbb{Z}$ with two separate positions $(i_0, j_0)$ and $(i_1, j_1)$:
$$
t_{i_1, j_1} \cdot (M[i_0] \cdot C^T[j_0] - C[i_0] \cdot M^T[j_0]) = t_{i_0, j_0} \cdot (M[i_1] \cdot C^T[j_1] - C[i_1] \cdot M^T[j_1])
$$
Here $t$ is a small value, since $M$ is very small. So we can combine $t \cdot M[i]$ as a secret and solve it by applying LLL to the kernel space. For an optimized strategy, we can pick $i_0 = i_1 = i$ and reduce the unknown variables from $k \cdot 4 = 64$ to $k \cdot 3 = 48$, that is:
$$
(t_{i, j_1} \cdot M[i]) \cdot C^T[j_0] - (t_{i, j_0} \cdot M[i]) \cdot C^T[j_1] = C[i] \cdot (t_{i, j_1} \cdot M^T[j_0] - t_{i, j_0} \cdot M^T[j_1])
$$
With the equation, we can find $(t \cdot M[i]) \Rightarrow M[i]$, and solve $M$ row by row.
It’s worth mentioning that for any position $(i, j)$, $(M[i, i], M[j, j])$ will always be eliminated in the equation. So we can only recover $M$ without $M[i, i]$. But it’s enough for us to brute force 3 bytes to get the flag.
Other solutions
We can implement some new solutions with Cayley-Hamiltion Theorem.
For a $k \cdot k$ matrix $M$, let $p_{M}(x) = \Sigma_{i=0}^{k-1} a_i \cdot x^i$ be the characteristic polynomial of $M$, we have $p_{M}(M) = 0$.
And this, my friend, gives us a way to find a linear expression with $[M^0, …, M^{k-1}]$ for any $M^e$, since we can use $p_M(M)$ to build a quotient ring.
Back to the challenge, we can find $[b_0, …, b_{k-1}]$ such that $C = \Sigma_{i=0}^{k-1} b_i \cdot M^i \pmod{n}$. Since $M^i$ is still small enough, we can costruct $k \cdot k$ HCLPs with each $C[i, j]$ and $[M^0[i, j], …, M^{k-1}[i, j]]$.
BabyLWE
In this challenge we need to solve a LWE problem with a special noise distribution: $e_i$ is not small but picked from a random ternary error set $errs$ ($|errs| = 3$).
Months before, me and @糖醋小鸡块 discussed about the binary error set scenario ($|errs| = 2$). Based on the fact that for any binary set $errs = \{ e_0, e_1 \}$, we can always find an affine map $f(x) = a \cdot x + b$, such that $f(errs) = \{0, 1\}$. And this affined error vector is short enough to be obtained on the following lattice:
$$
b = s \cdot A + e \pmod{p}
\Rightarrow
\begin{bmatrix}
A \\
b \\
\textbf{1}^m \\
p \cdot I
\end{bmatrix}
$$
where $\textbf{1}^m$ is an all-1 vector and $I$ is the identity matrix. With the recovered binary vector, we can learn the pick-up situations of the error vector and solve LWE in a linear system of $(s, errs)$.
The method also works in this challenge. We’re not able to find a strictly small vector (say binary vector) through affine map with $|errs| > 2$. But it turns out that in this challenge, an affined ternary vector is short enough to be solved through LLL. Then we can solve LWE with the same steps above.
Pedantic
In this challenge we need to break a zkp protocol with bad Fiat-Shamir Transformation.
Fiat-Shamir Transformation
Fiat-Shamir Transformation is a practical way to transform an interactive sigma protocol into a non-interactive version. In short, we construct a determined Random Oracle by hashing the current states, and replace the “challenge” generated by the verifier. You can check how hash_points_to_scalars is used in both prove and verify in this challenge.
RO is the core of the security here: we must make sure the hash function is well-constructed, and the current states are carefully selected. So, the linear structure of hash_points_to_scalars is definitely not a good choice. Xp
1 | def hash_points_to_scalars(pts: list[Point], n: int): |
Our Solution
The most part of the protocol remains secure due to secp256k1, which means we’re not able to forge a valid proof without the knowledge of x. But if we can predict the challenge c in some way, things will be a little different since we can randomly pick z first, and compute Gr = Y*c - G*z.
For the iteration part, we can use a fixed point:
$$
c = a \cdot c + b \Rightarrow c = \frac{b}{1 - a} \pmod{q}
$$
Now c is the same in each round, we can focus on how to construct a valid Grs to get the target c. We can generate a set of zs and the corresponding Grs first. Consider there exists a valid subset of Grs satisfying our target, we have:
$$
c = \Sigma_{i} k_i \cdot \mathcal{H}(Gr_i) \pmod{q}
$$
where $k_i$ is a binary variable and $\mathcal{H}$ is the hash function hash_point. This is a typical knapsack problem, and we can try to find a solution with LLL.
(*)Paranoid
In this challenge we need to break a zkp protocol with NOT THAT BAD Fiat-Shamir Transformation.
Some Discussions
For this one, we can still 1) fix the c first, and 2) construct a valid Grs to get c. But this time we’re not able to find a fixed point, so the iteration part is unavoidable.
In this case, we may have to fix a c and randomly get k groups of Grs, picking one out of each group to combine c. This leads to a k-sum problem, while wagner algorithm is an efficient way to solve it. I found a python-implemented version to use, but that’s not enough for this problem. Maybe cpp and careful optimization are necessary for this challenge ig.