MATH OR METH? hidden row in a lattice

crypto 298 pts
flag TFCCTF{this_is_a_very_very_long_flag_for_a_short_ctf_chall_ggs}

Overview

The challenge encodes the flag body as a vector of base-33 digits and plants it as one row of a small random matrix A (57 rows, 88 columns). It publishes only the product

text 
h = a * A  (mod p)

for a secret row vector a and a 1084-bit prime p, and withholds both a and A. The goal is to recover the planted row.

The digit vector

python 
1base = B + 1  # 33
2while x:
3    row.append(x % base)
4    x //= base

So the planted row f satisfies x = sum(f[j] * 33**j) with every coordinate in [0, 32]. Recovering f and reading it as base-33 gives the flag body.

Vulnerability

Work in the lattice of integer vectors that are consistent with the single published modular relation:

text 
L = { v in Z^88 : <h, v> = 0 (mod p) }

Every integer null-vector of A lies in L, because A v = 0 implies <h, v> = a A v = 0. With 57 rows and 88 columns, A has expected nullity 88 - 57 = 31, and those 31 null-vectors are short since every entry of A is small. Any vector that only satisfies the modular relation is huge by comparison, on the order of p. on L therefore recovers exactly the 31 short null-relations.

Insight

Two rounds of LLL. The first recovers the null-space of the hidden matrix as short vectors. Stack them into Y. Every original row of A is orthogonal to Y, so the integer right kernel of Y contains the row lattice of A. A second LLL on that kernel produces short vectors in the hidden row lattice. One of them, up to sign and small combinations, has all 88 coordinates in [0, 32] and decodes to printable text.

Solver

python 
1# SageMath, run from the challenge directory
2inv = inverse_mod(h[0], p)
3rows = [[p] + [0] * (m - 1)]
4for j in range(1, m):
5    v = [0] * m
6    v[0] = ZZ((-h[j] * inv) % p)
7    if v[0] > p // 2:
8        v[0] -= p
9    v[j] = 1
10    rows.append(v)
11
12K = Matrix(ZZ, rows).LLL(delta=0.999)
13short = [v for v in K.rows() if v.norm() < 10000]      # ~31 of these
14
15Y = Matrix(ZZ, short).row_space().basis_matrix()
16R = Y.right_kernel_matrix().LLL(delta=0.999)           # hidden row lattice
17
18def decode(v):
19    if min(v) < 0 or max(v) > B:
20        return None
21    x = sum(ZZ(v[i]) * ZZ(B + 1) ** i for i in range(m))
22    return int(x).to_bytes((int(x).bit_length() + 7) // 8, 'big')
23
24# search the short basis, its signs, and modest pairwise combinations
25candidates = list(R.rows())
26for i in range(R.nrows()):
27    for j in range(i):
28        candidates += [R[i] + R[j], R[i] - R[j], -R[i] + R[j], -R[i] - R[j]]
29for v in candidates:
30    for w in (v, -v):
31        msg = decode(w)
32        if msg and (b'TFCCTF' in msg or all(32 <= c < 127 for c in msg)):
33            print('CANDIDATE', msg)
session 
$sage solve_math_or_meth.sage
short modular relations: 31
relation rank: 31
row lattice: 57 88
CANDIDATE b'this_is_a_very_very_long_flag_for_a_short_ctf_chall_ggs'

The challenge source wraps the recovered body in TFCCTF{}.

Flag

text 
TFCCTF{this_is_a_very_very_long_flag_for_a_short_ctf_chall_ggs}