XCTF-ACTF 2025

(Updated: )
,

Time: 2025.04.26-27 (online)

I played XCTF-ACTF 2025 with N0wayBack this weekend, and we got 1st for the first time. My teammates are sooooo strong orz

rank.png

I with @糖醋小鸡块 solved all 4 crypto challenges. All of them are high-quality, and we actually found many interesting unintended solutions XD

easy_log (12 solves)

Yet another DLP challenge.

Our Solution

At first glance this’s a classic curve problem, so we need to recover the curve first. We (@糖醋小鸡块) tried an interesting method from @hellman. In this method we take many points as inputs and try to solve the curve parameters by polynomial interpolation. 

1
2
3
4
5
6
7
8
9
10
11
12
from itertools import product
R, (x, y) = GF(p)["x", "y"].objgens() # try on each p, since we need to compute kernel basis
xt, yt = 2, 2

monomials = [x**i*y**j for i, j in product(range(xt+1), range(yt+1))]
kG2 = [double_and_add(randint(0, p), G2, p) for _ in range(len(monomials)+1)]
A = matrix(GF(p), [[monomial(x, y) for monomial in monomials] for x, y in kG2])
coefs = A.right_kernel().basis()
for coef in coefs:
	f = sum([fi*monomial for fi, monomial in zip(coef, monomials)])
	print(coef)
	print(f)

And this is a universal method, you just need to pre-assume the monomials. We managed to recover the curve as $x^2 + x \cdot y - y^2 + 1 = 0$ with G2, but IT DIDN’T WORK ON G1! (And this will be discussed later)

Now this is a quadratic curve (a conic curve actually), and the order of the curve on $\mathbb{F_p}$ should be $p^2-1$. With some tests, this worked on both G1 and G2. Based on this we can implement a PH-BSGS style attack to solve DLP.

For the first part, we factor the given $n$.

1
2
3
4
5
6
7
8
9
10
11
n = 0x231d5fa471913e79facfd95e9b874e2d499def420e0914fab5c9f87e71c2418d1194066bd8376aa8f02ef35c1926f73a46477cd4a88beae89ba575bb3e1b04271426c6706356dd8cd9aa742d7ad0343f8939bfd2110d45122929d29dc022da26551e1ed7000
ps = [
    (2, 12),
    (5, 4),
    (15271784978279, 1),
    (10714146599832792643, 1), 
    (222696442740376752383, 3), 
    (899889935029682511225429150065010811552017719005924136271659168643090431, 1),
    (899889935029682511225429150065010811552017719005924136271659166808024139, 1)
]
assert n == prod([p**i for p, i in ps])

It turns out each factor is appropriate for the attack (note that the order on some certain primes are $p-1$). To recover the secret (8*68=544bit), we also used p-adic field attack on (222696442740376752383, 3). Somehow I could only solve it on $p^2$ instead of $p^3$, but that was enough.

For the second part, we just constructed a smooth prime with several 16bit subgroups.

solution: exp.py

Definitely not a pleasing code, but we have a worse one during the contest.

Some Additional Thoughts

So far it’s enough to solve the challenge. We don’t need the curve itself, we just need the order actually. But it’s really weird that G1 is not on the curve (not on any curve ig, considering @hellman’s method is universal), but has the same structure.

After the contest I got the answer from @∝: this is not a curve operation but a matrix operation.

$$
\begin{bmatrix}
y_3-x_3 & x_3 \\
x_3 & y_3
\end{bmatrix}=
\begin{bmatrix}
y_2-x_2 & x_2 \\
x_2 & y_2
\end{bmatrix}
\cdot
\begin{bmatrix}
y_1-x_1 & x_1 \\
x_1 & y_1
\end{bmatrix}
$$

This forms a multiplication matrix group. And when the elements satisfy the curve equation, it becomes isomorphic to the addition curve group. But the operation itself doesn’t need the element to be a curve point. And now it’s quite clear. We can analyze the eigenvalues or the group itself to get the order. With the eigenvalues we can also map the elements onto $\mathbb{F_p^2}$, gaining some optimization to solve DLP.

Since this is not my first time to connect matrixs and quadratic curves, I may find some time to give a comprehensive learning these days. And we still need some math works on how to solve such DLP on $p^i$.

AAALLL (8 solves)

In this challenge we need to find a $n$-degree small ternary polynomial $f$, with $\frac{n}{2}$ pairs of $(x_i, f(x_i))$ on $\mathbb{F_p}$. The special part is that $x_i$ is randomly picked from the roots of $x^n+1$. Here $n=450$ and $pbit=32$.

Solution 1 (Unintended)

A direct way is to construct the primal lattice and solve $f$ with flatter. The main reason this worked is $pbit=32$ is a little big for $n=450$, and it’s enough to solve uSVP under BKZ-2 bound. One can pick a subset of the instances to get a better perfomance.

Solution 2 (Intended)

The intended solution captures the special structure of the lattice. Since $x_i$ is a root of $x^n+1$, we’re actually dealing with a subset of Vandermonde matrix columns. This is called Partial Vandermonde Knapsack Problem, and you can find a optimized solution in this from Eurocrypt 2024.

pvkp.png

To make it clear, we have $x^n + 1 = 0 \rightarrow \frac{1}{x} = -x^{n-1} \pmod{p}$, and this builds certain connections between $f(x)$ and $f(\frac{1}{x})$. For instance, we have $f(x) = a_{n-1} \cdot x^{n-1} + …$ and $f(\frac{1}{x}) = a_1 \cdot \frac{1}{x} + …$, and we can sum them up to get $f(x) + f(\frac{1}{x}) = (a_{n-1}-a_1) \cdot x^{n-1} + …$.

In short, we can construct new polynomials $(\phi_+(x), \phi_-(x))$ with $(f(x), f(\frac{1}{x}))$, where $(\phi_+(x), \phi_-(x))$ are small and can be generated with a shorter (about $\lfloor \frac{n}{2} \rfloor$) basis. The following code gives a better explanation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from sage.all import *

def sample_ternery_poly(Q):
    return Q([choice([-1, 0, 1]) for _ in range(Q.degree())])

n = 450
p = 3774877201
t = n//2

P, x = GF(p)["x"].objgen()
g = x**n+1
roots = [i[0] for i in g.roots()]
Q = P.quotient(g)

f = sample_ternery_poly(Q).lift()
rs = list()
for r in roots:
    if r not in rs and 1/r not in rs:
        rs.append(r)

xs = [[r**i + 1/r**i for i in range(n//2+1)] for r in rs]
ys = [f(r) + f(1/r) for r in rs]
print(matrix(GF(p), xs).solve_right(vector(ys)))

xs = [[r**i - 1/r**i for i in range(1, n//2+1)] for r in rs]
ys = [f(r) - f(1/r) for r in rs]
print(matrix(GF(p), xs).solve_right(vector(ys)))

With high possibility, we can find some pairs of $(f(x), f(\frac{1}{x}))$ from the given data. Then we can solve $(\phi_+, \phi_-)$ from two smaller primal lattices and combine them to get the original polynomial $f$.

OhMyTetration (8 solves)

Here is a lottery center with some secret code in lotteryCenter. In short, we can send some $(g, times)$ to the server and receive a tetration $\mathcal{T}(p, g, x, times)$. For instance, $\mathcal{T}(p, g, x, 2) = g^{g^x} \pmod{p}$. And our target is to recover $x$.

Some Fuzzes

It turns out that each time the server randomly chooses a prime $p$ from a small prime set. Take one of them as an example:

1
2
3
4
p = 1502305675703953507826564356364207463785905265358954425050832597353379827611347779894929874274487297076504174110953417469304402049079223143080164648064147459
q = (p - 1) // 2
qs = [(2, 12), (2449952539, 1), (2580715139, 1), (2792523953, 1), (2945474351, 1), (2996317717, 1), (3172879987, 1), (3229817321, 1), (3272969519, 1), (3435471803, 1), (3606091481, 1), (3613773421, 1), (3696075863, 1), (3706535681, 1), (3729911617, 1), (3912962413, 1), (3919762169, 1)]
assert q == prod(qi**i for qi, i in qs) + 1

Here $p = 2*q + 1$, where $q$ is another big prime and $q-1$ is very smooth. All other $p$ have the same structure so we can just use this one in the following steps. To achieve that in the code, I just kept reconnecting until the server chose my prime.

Another point worth noting is that we cannot just choose $g$ arbitrarily because of lotteryCenter.defineG(g). After some tests, we found that some certain primes can pass the check. While it doesn’t expose the underlying checking strategy, we still have the opportunity to get a valid one by keeping constructing some primes.

Solution 1 (Unintended)

Considering $q-1$ is smooth, with several 32bit small primes, a PH-BSGS style attack works as:

  1. Choose a generator $g_i$ from the $q_i$-order subgroup of $\mathbb{F_q}$, here we have $q_i | (q-1)$.
  2. Receive $y = \mathcal{T}(p, g_i, x, 2) = g_i^{g_i^x} \pmod{p}$ from the server.
  3. For all $a \in [0, t]$, compute and store $g_i^{2 \cdot g^{a \cdot t} \pmod{q}} \pmod{p}$.
  4. For all $b \in [0, t]$, compute $y^{2 \cdot g_i^{-b} \pmod{q}} \pmod{p}$ and query for a corresponding $a$.
  5. Finally, we have $x = a \cdot t + b \pmod{q_i}$, and we can combine them using crt.

Here we choose $t = \lceil \sqrt{q_i} \rceil$ for a balanced perfomance. You can check the correctnest by $y^{g_i^{-b}} = g_i^{g_i^{x-b}} = g_i^{g_i^{a \cdot t}}\pmod{p}$. The reason we need $g_i^{2 \cdot (…)} \pmod{p}$ instead of $g_i^{(…)} \pmod{p}$ is that the order of $g_i$ may be $p-1 = 2 \cdot q$ on $\mathbb{F_p}$, where the order of $g_i^2 \pmod{p}$ is guaranteed to be $q$ (or 1, with negligible probability).

That’s it. What we need to do is to find a valid prime generator $g_i$, get a piece of $x_i$ locally, and then recover $x \pmod{\frac{q-1}{2}}$ with crt. For this chall, we need a little bruteforce to get the real $x = (x \pmod{\frac{q-1}{2}}) + k \cdot \frac{q-1}{2}$.

It actually costed us plenty of time since lotteryCenter.defineG(g) is veryyyyy slow, somehow :o

Solution 2 (Intended)

For the intended solution, we need more complex tetrations. As we compute a “higher” tetration tower, the order decreases rapidly as $\phi(\phi(…\phi(p)))$ where $\phi(x)$ is the Euler function. With an appropriate order, we can bruteforce the solution and a piece of $x$ under some modulus.

This is more complicated. But if the level of tetration got limited or $q-1$ was not that smooth, we might have to try this ig.

tinyCKKS (2 solves)

A good chance to learn more about FHE-CKKS! Nice code from @den.g_feng :D

CKKS: Intro

In CKKS we deal with polynomials on a quotient ring with a prime power modulus $q=p^i$. At first the modulus is $p^{L+1}$. In general, CKKS is a RLWE style FHE scheme.

  • $\mathcal{Keygen}$: Generate a secret ternary polynomial $sk$.
  • $\mathcal{Encode}$: For message polynomial $m$, compute $pt_i = \lfloor m_i \cdot p \rfloor$ and construct the plaintext polynomial $pt$.
  • $\mathcal{Decode}$: Compute $m_i = \frac{pt_i}{p}$ to recover the original $m$.
  • $\mathcal{Enc}$: For the plaintext polynomial $pt$, sample a noise polynomial $e$ and a random polynomial $ct_0$. Then compute $ct_1 = pt + e - ct_0 \cdot sk$, and the ciphertext pair is $(ct_0, ct_1)$.
  • $\mathcal{Dec}$ Compute $pt’ = ct_1 + ct_0 \cdot sk$.

In this challenge we use a simpler encode/decode strategy, the original CKKS scheme involves complex number and some other complicated operations.

It’s important to know that CKKS handles float data, which means $m$ is a float sequence (but $pt$ and other parts are not). You can find out that we actually cannot recover the original $pt$ and $m$ in CKKS. The noise is retained and after decoding, it exists as a small error in $m$.

Solution 1 (Intended)

In this challenge our target is to submit the exact original plain.

The intended solution uses an interesting feature about CKKS, which may be counter-intuitive to FHE newbies (me). By encoding the decrypted plain again, we can recover the exact $pt + e$, and then we can recover $sk$ with the ciphtext pair $ct$.

I’m not sure about other FHE schemes but for CKKS, it’s NOT a secure option to open a decryption oracle. I think the main reason is that CKKS uses floats instead of integers.

At least in this challenge it’s true. I heard a patched version is available in industrial implementations. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from sage.all import *
import numpy as np
load("ckks.sage")

N = 1024
p = 947819
B = 2
L = 4

r = 10
precision = 4

debug = False

ckks = tinyCKKS(N, p, B, L, debug)
plain = [round(np.random.uniform(0, r), precision) for _ in range(N)]
pt = ckks.encode(plain)
ct = ckks.encrypt(pt)
pt = ckks.decrypt(ct)
plain = ckks.decode(pt)

# recover sk
P, z = GF(p)["z"].objgen()
Q = P.quotient_ring(z**N+1)
pt = ckks.encode(plain)
sk = Q((pt - ct.b).poly.list()) / Q(ct.a.poly.list())
assert P(sk.list()) == P(ckks.sk.poly.list())

# recover e
plain = [round(np.random.uniform(0, r), precision) for _ in range(N)]
pt = ckks.encode(plain)
ct = ckks.encrypt(pt)
e = ct.b + ckks.sk*ct.a - pt
e = [ZZ(_+p//2)%p - p//2 for _ in e.poly.list()]
print(e)

Remember our target is to submit the orignial plain, so we need to predict $e$ too. Since the server uses a sequence of consecutive getrandbits(4) to generate $e$, we can crack MT19937 with the current $e$ and predict the next one. And the solution is quite clear now:

  1. (c=1) Get any plaintext-ciphertext pair as your wish, recover $sk$.
  2. (c=2) Get a ciphertext and the original plain, use $sk$ to recover $e$.
  3. Recover the underlying MT19937 states and predict the next $e$.
  4. (c=3) Get a ciphertext, use $sk$ and $e$ to recover the orignal plain.

It’s worth mentioning that the noise is kinda too small compared to $p$ (you can find it out in module_test, the error between the original plain and the decrypted one is quite small). So it’s also feasible to eliminate the effect of the noise by controlling the precision of the plain (thanks to @hash_hash).

Solution 2 (Unintended)

My teammate @糖醋小鸡块 found an interesting vuln about MT19937. Another PRNG used in this challenge is np.random, which is also based on MT19937 (in certain versions maybe).

1
2
3
4
5
6
7
8
9
10
11
12
13
# distribution.sage
def sample_uniform_poly(Q):
    q = Q.base_ring().cardinality()
    N = Q.degree()
    return polynomial(q, N, Q([np.random.choice([-1, 1]) * randbelow(int(q//2)) for _ in range(Q.degree())]))

def sample_ternery_poly(Q):
    q = Q.base_ring().cardinality()
    N = Q.degree()
    return polynomial(q, N, Q([np.random.choice([-1, 0, 1]) for _ in range(Q.degree())]))

# main.sage
plain = [round(np.random.uniform(0, r), precision) for _ in range(N)]

While sample_ternery_poly and plain may not be accessible, we can get sample_uniform_poly from ct_0 (and somewhere else), and it turns out we can obtain np.random.choice([-1, 1]) from the signs of the coefficients.

Only with enough (say 19937bits) consecutive values of np.random.choice([-1, 1]) can we recover the underlying states. So instead of ct, we need to use gen_ksk or gen_relin_key which gives t sets of ciphtertext-like data. Here t=100 is big so we can get enough data in one shot. Here is how we solved it:

  1. (c=1 and ccc=3 or 4) Get t sets of sample_uniform_poly data through ksk or galois_key (you can also use relin_key in ccc=2, which may be more complicated to implement).
  2. Recover the underlying MT19937 states and predict the next plain (you can also predict sample_ternery_poly to get the next $e$).

We actually thought this is the intended solution since it could use randbelow(q) in sample_uniform_poly. And B is very small to q so t is big enough here, but in module_test we have B=2^8.