$ cat writeup.md…
$ cat writeup.md…
ASIS CTF Quals 2026
Task: five NTRU-style public keys over a negacyclic ring encrypt XOR-accumulated message shares under keystreams keyed by hidden ternary polynomials. Solution: reduce each 2n x 2n NTRU lattice with LLL+BKZ-30 to recover the short (a,b) vector, resolve sign/order via the HMAC tag, decrypt and XOR all five plaintexts.
$ cat /etc/rate-limit
Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.
Five locks, one dense true fence, and a flag that thinks it is safe. Find the gap!
Attachment: an archive with fence.py (the encryption scheme) and flag.enc
(JSON containing parameters N, Q, W, R, five public keys H, and five
ciphertext objects C[i] = {S, C, T}).
English summary: the challenge implements a home-rolled NTRU-like public-key
encryption over the negacyclic polynomial ring Z_q[x]/(x^n+1). Five
independent key/instance pairs encrypt five message shares; the first four are
random pads and the fifth is the running XOR of the pads with the flag, so
XOR-ing all five decrypted plaintexts yields the flag. The session key of each
instance is derived from the two secret ternary polynomials, which must be
recovered from the dense public key by lattice reduction.
fence.py)Parameters: n = 128, q = 268435361 (prime just under 2^28), w = 80
(secret weight), r = 5 instances, and a fixed 8-byte domain separator d.
gn() generates a secret polynomial: exactly w/2 = 40 coefficients +1
and 40 coefficients -1, rest zero (ternary, fixed weight 80).
iv(a) computes the inverse of a in the ring via the extended Euclidean
algorithm over Z_q[x] reduced modulo x^n + 1.
Public key: h = pm(b, iv(a)), i.e. h = b * a^{-1} mod q in
Z_q[x]/(x^n+1). Immediately this gives the classic NTRU relation
pm(a, h) = b (mod q)
...
$ grep --similar