Magical Oracle - L3akCTF 2025

This challenge was a standard Hidden Number Problem dressed up in fantasy cosplay. The objective was clear: uncover a hidden value $\alpha$ using Babai's CVP algorithm

Challenge Overview

The challenge spins up a remote service that hands out:

p: A 256-bit prime modulus.
n: The bit length of p, which is 256.
k: The number of bits to be leaked, calculated as int(n**0.5) + n.bit_length() + 1, which comes out to 26.
d: The maximum number of queries we can make, 2 * int(n**0.5) + 3, giving us 35 attempts.

Then we have the entry point: Query MSB oracle. For each query, the server:

Generates a random $t$.
Computes $x = (\alpha * t)\mod p$, where $\alpha$ is the secret we’re after.
Returns $t$ and a value $z$, which is an approximation of $x$.

Finally, an AES-CBC–encrypted flag, with the key derived as $\text{SHA256}(\alpha)$.

All we have to do is to recover the secret $\alpha$ from the oracle leaks, derive the AES key, and decrypt the flag. Easy, right?

Attack Vector ;)

1. Collecting the Noisy Leaks

We scripted a quick loop to:

Send option 1 repeatedly until we exhausted the max queries $d$.
Retrieve $t_i$ and $z_i$ ans store them in arrays for later.

Tip: Whenever you’re given the source code of a challenge, ALWAYS run it locally before interacting with the remote. This lets you add logging and monitor exactly what’s going on so the challenge doesn’t feel as black-boxy

2. Modeling as a Hidden Number Problem

This is textbook Howgrave-Graham–Naehrig territory. We have:

$$ \alpha \cdot t_i \equiv z_i \pm \varepsilon_i \pmod p, $$

where each error $\varepsilon_i$ is bounded by $p / 2^{k+1}$. The goal: recover $\alpha$ from these noisy modular equations.

For those of you who’re unfamiliar with HNP, it is an application of lattice reduction, where the goal is to construct a lattice and reduce it (via LLL or BKZ) so that one of the short vectors reveals a relatively small value that we’re looking for, in this case, it’s $\alpha$

3. Lattice Construction & Babai’s Closest Vector

Let’s build our lattice. For $d$ samples $(t_i, z_i)$, we can construct the following basis matrix $M$ of dimension $(d+1)\times(d+1)$:

$$ M=\begin{bmatrix} p & 0 & \cdots & 0 & 0 \\ 0 & p & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & p & 0 \\ t_1 & t_2 & \cdots & t_d & C \end{bmatrix} $$

Concretely:

1
2
3
4
5
6
7
from sage.all import Matrix, vector, RationalField

M = Matrix(RationalField(), d+1, d+1)
for i in range(d):
    M[i, i] = p
    M[d, i]   = t[i]
M[d, d] = 1 / (2**(k+1))

Then we feed $M$ to LLL (with $\delta=0.75$, default value) and apply Babai’s nearest plane to find the shortest vector closest to $[z_1, \dots, z_d, 0]$. We let the algorithm do its magic, and we’ll find that the last coordinate of that vector (scaled back by $2^{k+1}$) yields $\alpha$.

4. Decrypting the Flag

With $\alpha$ in hand, derive the AES key:

1
2
3
4
5
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

aes_key = sha256(str(alpha).encode()).digest()

Then unwrap the CBC cipher to retrieve the flag:

1
2
3
4
iv, ciphertext = enc_blob[:16], enc_blob[16:]
cipher = AES.new(aes_key, AES.MODE_CBC, iv=iv)
flag = unpad(cipher.decrypt(ciphertext), AES.block_size)
print(flag)

L3AK{hnp_BBB_cvp_4_the_w1n}

Full Solver Snippet

Click to expand solver code

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
from pwn import remote
from time import time
import numpy as np
from sage.all import Matrix, vector, RationalField

HOST, PORT = '34.59.96.214', 11000

io = remote(HOST, PORT)
header= io.recvuntil(b"option: ").decode()
print(header)
io.sendline(b"3")
resp = io.recvuntil(b"Exit").decode().split('\n')[:5]
p = int(resp[1].split(" = ")[-1])
n = int(resp[2].split(" = ")[-1])
k = int(resp[3].split(" = ")[-1])
d = int(resp[4].split(" = ")[-1])
print(f"p={p}, n={n}, k={k}, d={d}")
threshold = p >> (k + 1)

samples_t = []
samples_z = []
delays = np.array([])
for i in range(d):
    print(io.recvuntil(b"Choose option: "))

    start = time()
    io.sendline(b"1")
    io.recvline()
    resp = io.recvline().decode().strip()
    end = time()


    duration = end - start
    print(f"Response time: {duration:.6f}s")
    delays = np.append(delays, duration)
    print(f"Response: {resp}")
    resp = resp.split(": ")[-1].split(", ")
    t_i = int(resp[0].split("=")[-1])
    z_i = int(resp[1].split("=")[-1])
    samples_t.append(t_i)
    samples_z.append(z_i)
avg_delay = np.mean(delays)
variance = np.var(delays)
std_dev = np.std(delays)
print(f"Average delay: {avg_delay:.6f}s, Variance: {variance:.6f}, Std Dev: {std_dev:.6f}")
print(f"Collected {len(samples_t)} samples.")
curated_t = []
curated_z = []
for i in range(len(samples_t)):
    if True:
        curated_t.append(samples_t[i])
        curated_z.append(samples_z[i])


def solve_hnp(t, u):
    length = len(t)
    M = Matrix(RationalField(), length+1, length+1)
    for i in range(length):
        M[i, i] = p
        M[length, i] = t[i]

    M[length, length] = 1 / (2 ** (k + 1))

    def babai(A, w):
        A = A.LLL(delta=0.75)
        G = A.gram_schmidt()[0]
        t = w
        for i in reversed(range(A.nrows())):
            c = ((t * G[i]) / (G[i] * G[i])).round()
            t -= A[i] * c
        return w - t

    closest = babai(M, vector(u + [0]))
    return (closest[-1] * (2 ** (k + 1))) % p

alpha = solve_hnp(curated_t, curated_z)
print(f"Recovered alpha: {alpha}")
io.sendlineafter(b"Choose option: ", b"2")

from base64 import b64decode
io.recvline()
enc_flag = io.recvline().decode().strip().split("Flag: ")[-1]
print(f"Encrypted flag: {enc_flag}")
enc_flag = b64decode(enc_flag)
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha256
key = sha256(str(alpha).encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv=enc_flag[:16])
flag = unpad(cipher.decrypt(enc_flag[16:]), AES.block_size)
print(f"Decrypted flag: {flag.decode()}")

Ignore the timing analysis. I initially thought that we had to perform some kind of timing attack due to the number of iterations used to derive $z$
1
2
3
4
5
time.sleep(0.05)
for _ in range(1000):
    z = random.randrange(1, self.p)
    if abs(x - z) < threshold:
        return z
Turns out it was a red herring