Fence — ASIS CTF Quals 2026

Description

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.

Analysis

The scheme (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)
  

  with both a and b short ternary vectors of norm 160 (80 nonzero entries of ±1 each). That is exactly the shape of an NTRU lattice problem.

• sh(a, k) is a signed cyclic rotation — multiplication by x^k in the negacyclic ring (sign flips when the coefficient wraps around).

• Session key: ky(a, b, s) = sha3_256(d || s || bytes(i+1 for i in u)) where u = min over all 2n signed rotations sh(a,i) + sh(b,i) taken as tuples. This canonicalization is symmetric under swapping a and b but not under negation of either secret, and bytes(i+1) would raise on negative entries — so a recovered lattice vector must be tested in all 4 variants (a,b), (-a,-b), (b,a), (-b,-a).

• Encryption: keystream z = shake_256(d || k || s), ciphertext c = m XOR z, authentication tag T = HMAC-SHA256(k, d || json({N,Q,H}) || s || c)[:16]. The tag is a free offline oracle: any candidate secret pair can be verified without ambiguity.

• Message accumulation in main(): for instances 0..3 a random pad is XOR-accumulated into acc; instance 4 encrypts acc XOR flag. Therefore m0 XOR m1 XOR m2 XOR m3 XOR m4 = flag.

Why it falls

The pair (a, b) satisfies a * rot(h) - b * q = 0 in integer coefficient vectors, so it lives in the 2n x 2n NTRU lattice

B = [[ I_n   | rot(h) ]
     [ 0     | q*I_n  ]]

where rot(h) is the multiplication matrix of h in the negacyclic ring. (a, b) has Euclidean norm exactly 160, while generic lattice vectors have norm on the order of sqrt(2n) * q^(1/2) ~ 10^4-10^5, giving a large gap.

Two practical pitfalls found during solving:

1. Matrix orientation matters. The multiplication matrix must be built so that a lattice row (x, x*rot(h)) equals pm(x, h) — i.e. row j of the top-right block is pm(e_j, h). Building columns as pm(h, e_j) instead yields a wrong lattice where reduction only ever pops trivial unit vectors.
2. LLL is not enough. Plain LLL on the 256-dimensional basis stalls at vectors of norm ~19000. Running BKZ with block_size=30 after LLL immediately produced ~30 basis rows of norm exactly 160 with all coefficients in {-1,0,1} — the secrets fall out directly as row 0, no embedding or rescaling tricks required.

Solution

1. Parse flag.enc; for each of the 5 instances build the NTRU lattice from the public key h (sparse pm() skipping zero coefficients keeps the matrix construction fast in pure Python).
2. LLL-reduce, then BKZ-reduce with block_size=30.
3. Scan the reduced basis for rows whose first half and second half are both ternary with exactly 80 nonzero coefficients each. Such rows appear in bulk (~30 of them, ± rotations/sign flips of the same secret).
4. For each candidate, try the 4 sign/order variants, derive k = ky(a, b, S), recompute the truncated HMAC tag and compare with T — exactly one variant matches. This also disambiguates (a,b) vs (b,a) since ky is swap-symmetric but negation-asymmetric.
5. Regenerate the keystream shake_256(d || k || S) and XOR out the plaintext.
6. XOR the five recovered plaintexts together — the flag.

Full solver (run from the task directory; requires fpylll):

import json, hashlib, hmac
from pathlib import Path
from fpylll import IntegerMatrix, LLL, BKZ

z = json.loads(Path('Fence/flag.enc').read_text())
n = z['N']; q = z['Q']
d = b"\x3a\x91\xf0\x7d\x14\x68\xbc\x29"

def pm(a, b):
    c = [0]*n
    for i in range(n):
        ai = a[i]
        if not ai:
            continue
        for j in range(n):
            t = ai*b[j]
            if i+j < n:
                c[i+j] = (c[i+j]+t) % q
            else:
                c[i+j-n] = (c[i+j-n]-t) % q
    return c

def sh(a, k):
    k %= 2*n
    s = -1 if k >= n else 1
    if k >= n:
        k -= n
    b = [0]*n
    for i in range(n):
        if i+k < n:
            b[i+k] = s*a[i]
        else:
            b[i+k-n] = -s*a[i]
    return b

def ky(a, b, s):
    u = min(tuple(sh(a, i)+sh(b, i)) for i in range(2*n))
    return hashlib.sha3_256(d + s + bytes(i+1 for i in u)).digest()

def recover_ab(h):
    basis = []
    for j in range(n):
        e = [0]*n; e[j] = 1
        basis.append(pm(e, h))          # row j of the multiplication matrix
    B = IntegerMatrix(2*n, 2*n)
    for i in range(n):
        B[i, i] = 1
        for j in range(n):
            B[i, n+j] = basis[i][j]
    for i in range(n):
        B[n+i, n+i] = q
    LLL.reduction(B)
    BKZ.reduction(B, BKZ.Param(block_size=30))
    cands = []
    for r in range(2*n):
        v = tuple(B[r, c] for c in range(2*n))
        a = list(v[:n]); b = list(v[n:])
        if all(x in (-1, 0, 1) for x in a+b) and sum(1 for x in a if x) == 80 and sum(1 for x in b if x) == 80:
            cands.append((a, b))
    return cands

msgs = []
for idx, (h, ct) in enumerate(zip(z['H'], z['C'])):
    S = bytes.fromhex(ct['S']); C = bytes.fromhex(ct['C']); T = bytes.fromhex(ct['T'])
    u_json = json.dumps({'N': n, 'Q': q, 'H': h}, sort_keys=True, separators=(',', ':')).encode()
    found = None
    for a, b in recover_ab(h):
        for aa, bb in [(a, b), ([-x for x in a], [-x for x in b]), (b, a), ([-x for x in b], [-x for x in a])]:
            k = ky(aa, bb, S)
            t = hmac.new(k, d + u_json + S + C, hashlib.sha256).digest()[:16]
            if hmac.compare_digest(T, t):
                zt = hashlib.shake_256(d+k+S).digest(len(C))
                found = bytes(i ^ j for i, j in zip(C, zt))
                break
        if found is not None:
            break
    assert found is not None, idx
    msgs.append(found)

flag = bytearray(len(msgs[0]))
for m in msgs:
    for i, b in enumerate(m):
        flag[i] ^= b
print('FLAG:', flag.decode())

Runtime is roughly 2–3 minutes per instance (the dominant cost is the pure Python pm() matrix construction; BKZ-30 on the 256-dim basis is fast after LLL warm-up).