Cyclotomic Echo - z0d1ak CTF 2026

Solve for Cyclotomic Echo - z0d1ak CTF 2026

Let's do a quick recap of what I understood for this challenge.

We were given two files verifier.py and recovery.json

ncat --ssl cyclotomic-echo-4e1b77d79761.chals.z0d1ak.org 1337

And the instance which was a TLS service that hands us a fixed instance (public key + message) and waits for a forged signature.

The verifier.py was a verifier defining the signature scheme ce-v2.

recovery.json had four integer vectors f, g, F, G, each of length 128. This is the leaked secret NTRU trapdoor basis.

The description was: "some keys despair but their geometry doesn't."

So by that what I understood is the geometry is lattices, and after looking at the file it was obvious it is encoded publicly by a Gram matrix. The specific short vectors (the "keys") are just one basis for it. I just used the leaked basis to sign, because the verifier only checks geometry.

Plan to solve the challenge

1. Recognize ce-v2 as a Falcon/DLP hash-and-sign over $K = \mathbb{Q}[x]/(x^{128} + 1)$; the public key is a Gram matrix $Q$ with $\det(Q) = 1$.

2. Read the verifier as: signature = short $e \equiv (x, y) \pmod{2}$ with $eQe^\dagger \leq 16384$.

3. Recognize recovery.json as the secret basis $B$ with $Q = BB^\dagger$; confirm it reproduces the server's $(q_{00}, q_{10})$ and $fG - gF = 1$.

4. Reduce forging to CVP: closest point of $\Lambda = 2 \cdot \text{rowspan}(B)$ to $c_{\text{vec}} = (x, y)B$.

5. LLL-reduce $\Lambda$ (defeating the half-integer tie), Babai nearest-plane, recover $u = s_1$ via $B^{-1}$.

The Math Behind It

Trapdoor produces the public key

import sys, json
sys.path.insert(0, ".../crypto_cyclotomic-echo 2/dist")
import verifier as V
K = V.K
rec  = json.load(open(".../recovery.json"))
inst = json.load(open("instance.json"))
f,g,F,G = (K(rec[k]) for k in ("f","g","F","G"))
 
a_srv, b_srv = K(V.X(inst['q00_half'])), K(inst['q10'])
a_rec = f*f.conjugate() + g*g.conjugate()      # q00
b_rec = G*g.conjugate() + F*f.conjugate()      # q10
print(a_rec == a_srv, b_rec == b_srv, f*G - g*F)   # True True 1

LLL + Babai nearest-plane

import sys, json, os
import numpy as np
sys.path.insert(0, ".../crypto_cyclotomic-echo 2/dist")
import verifier as Vf
from sage.all import matrix, ZZ
 
K = Vf.K; z = K.gen(); N = 128
rec  = json.load(open(".../recovery.json"))
f,g,F,G = (K(rec[k]) for k in ("f","g","F","G"))
inst = json.load(open("instance.json"))
 
def cl(w):                              # ring element -> length-N int list
    l = [int(c) for c in w.list()]; return (l + [0]*(N-len(l)))[:N]
 
# lattice Lambda = 2 * rowspan(B),  B = [[g,-f],[G,-F]]
rows = []
for (p0, p1) in [(g, -f), (G, -F)]:
    for i in range(N):
        rows.append(cl(2*z**i*p0) + cl(2*z**i*p1))
M    = matrix(ZZ, rows).LLL()          # reduce once
Mint = np.array(M, dtype=object)
Bf   = np.array(M, dtype=np.float64)
 
# float Gram-Schmidt
n = Bf.shape[0]; Bs = np.zeros_like(Bf)
for i in range(n):
    Bs[i] = Bf[i].copy()
    for j in range(i):
        Bs[i] -= (Bf[i].dot(Bs[j]) / Bs[j].dot(Bs[j])) * Bs[j]
sn = np.array([Bs[i].dot(Bs[i]) for i in range(n)])
 
def babai(t):                          # nearest-plane closest vector
    b = t.astype(np.float64).copy(); w = np.zeros(n, dtype=object)
    for i in reversed(range(n)):
        c = round(b.dot(Bs[i]) / sn[i])
        if c: b = b - c*Bf[i]; w = w + c*Mint[i]
    return w
 
def sign(salt):
    x, y = Vf.H(inst, salt)
    t = np.array(cl(x*g + y*G) + cl(-(x*f + y*F)), dtype=object)   # c_vec
    r = t - babai(t)                                              # residual e*B
    E0 = K([int(v) for v in r[:N]]); E1 = K([int(v) for v in r[N:]])
    e1 = E0*f + E1*g                                              # e = r * B^{-1}
    return cl((y - e1) / 2)                                       # s1 = u
 
while True:                            # salt = coset selector; resample until in-bound
    salt = os.urandom(16); s1 = sign(salt)
    if Vf.V(inst, salt, s1):
        json.dump({"salt_hex": salt.hex(), "s1": s1}, open("forgery.json", "w"))
        print("valid:", salt.hex()); break

Submit the forgery

from pwn import *
import json, time
fg = open("forgery.json").read().strip()
io = remote("cyclotomic-echo-4e1b77d79761.chals.z0d1ak.org", 1337, ssl=True)
time.sleep(1.5); io.recv(100000, timeout=5)      # instance banner
io.sendline(fg.encode())
print(io.recv(100000, timeout=6).decode())

Output

(ctf-env) manavhowal@manavs-MacBook-Air ~ % python3 meow.py
# local:  sage verifier.py instance.json forgery.json   ->  valid
# norm:   z = 16368   /   bound = 16384        (inside by 16)
# server: {"flag":"zdk{CyCl0toMIC_eCHo_ONE_Ba5IS_bindS_EVeRY_tEaM_ARcHiVE}","ok":true}

References

1. Gentry, Peikert, Vaikuntanathan, Trapdoors for Hard Lattices and New Cryptographic Constructions, STOC 2008 - the GPV hash-and-sign framework and preimage sampling. eprint.iacr.org/2007/432

2. Ducas, Lyubashevsky, Prest, Efficient Identity-Based Encryption over NTRU Lattices, ASIACRYPT 2014 - the NTRU Gram-matrix trapdoor this scheme mirrors. eprint.iacr.org/2014/794

3. Fouque, Hoffstein, Kirchner, Lyubashevsky, Pornin, Prest, Ricosset, Seiler, Whyte, Zhang, Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU (NIST PQC) - the LDL tree, the $Q = BB^\dagger$ Gram formulation, and the $(x - 2v, y - 2u)$ structure. falcon-sign.info

4. Prest, Gaussian Sampling in Lattice-Based Cryptography (PhD thesis, 2015) - the samplers and LDL trees behind Falcon. tprest.github.io

5. Babai, On Lovasz' lattice reduction and the nearest lattice point problem, Combinatorica 6 (1986) - the nearest-plane algorithm. doi.org/10.1007/BF02579403

6. Lenstra, Lenstra, Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982) - LLL reduction. doi.org/10.1007/BF01457454

7. SageMath documentation - number fields and lattice reduction. doc.sagemath.org