CHALL(1)

crypto

---

Challenge

Parameters: n = 57, m = 88, B = 32, base = 33. The flag is encoded into base-33 digits, giving a row vector of length m. Then:

1. 57 random coefficient vectors ai are drawn from Z/pZ.
2. A 57×88 matrix A is filled with random digits in [0, B], except one planted row A[planted_idx] is secretly the flag encoding.
3. The output vector is: h[j] = ∑i ai · A[i][j] (mod p)

We're given n, m, B, p, and the vector h of length 88. Goal: recover the flag row.

The Attack Idea

The output h is in the column span of A over Z/pZ. Since A has 57 rows but 88 columns, its right null space over Z/pZ has dimension m − n = 31. Any vector orthogonal to h mod p gives us a constraint that the planted flag row must satisfy.

The flag row has small entries (all in [0, 32]), so it will appear as a short vector in this constrained lattice. We use LLL and BKZ to find it.

Step 1 — Orthogonal Lattice of h

Build the m×m matrix M whose rows are an integer basis for the set of vectors v with v · h = 0 (mod p). Specifically: M[i][i] = 1 for i < m-1, M[i][m-1] = -(h[i] · h[m-1]-1) mod p, and the last row is [0,...,0,p]. After LLL, the 31 shortest rows span the right null space of the 57 coefficient vectors.

M = Matrix(ZZ, m, m)
inv = inverse_mod(h[-1], p)
for i in range(m - 1):
    M[i, i] = 1
    M[i, m - 1] = (-h[i] * inv) % p
M[m - 1, m - 1] = p

L = M.LLL()
V = L[:31]          # 31 shortest rows span the orthogonal complement

Step 2 — Kernel and CVP

The kernel of those 31 vectors (over Z) has dimension m - 31 = 57. Any row of A must lie in this kernel (since it's in the column span of A). The flag row additionally has entries in [0, 32], so it's a short vector near the centroid 16 · 1.

To find it we embed a CVP: append a target row/column to the kernel basis with weight W = 16. BKZ will push the flag row to the surface:

K = V.right_kernel().basis_matrix()   # 57x88 kernel

W = 16
K_ext = Matrix(ZZ, K.nrows() + 1, K.ncols() + 1)
for i in range(K.nrows()):
    for j in range(K.ncols()):
        K_ext[i, j] = K[i, j]
for j in range(K.ncols()):
    K_ext[K.nrows(), j] = 16          # target centroid
K_ext[K.nrows(), K.ncols()] = W      # weight column

K_ext_BKZ = K_ext.BKZ(block_size=20)

Step 3 — Decode the Flag

Rows of K_ext_BKZ whose last entry equals ±W are CVP solutions. The corresponding prefix, after centering around 16, gives base-33 digits that decode to the flag string:

base = B + 1   # = 33
for row in K_ext_BKZ:
    if row[K.ncols()] in (W, -W):
        sign = 1 if row[K.ncols()] == W else -1
        A_row = [16 - sign * row[j] for j in range(K.ncols())]
        if all(-5 <= x <= 37 for x in A_row):
            val = 0
            for x in reversed(A_row):
                val = val * base + int(x)
            flag = int(val).to_bytes((int(val).bit_length() + 7) // 8, 'big')
            if all(32 <= b <= 126 for b in flag):
                print(flag.decode())

Result

The flag was embedded as a message in the challenge description: “place the flag obtained in TFCCTF{}” — so the printable string found is the inner content.