Lattices Wreck Everything - Crypto

Points: 500 | Flag: BITSCTF{h1nts_4r3_p0w3rfu1_4nd_f4lc0ns_4r3_f4st} | Solved by: Smothy @ 0xN1umb

what we got

zip file with a bunch of python files implementing Falcon-512 (post-quantum signature scheme) and two important files:

• challenge_data.json - public key matrix A, the vector b (all zeros), and 436 leaked coefficients of the secret key f
• challenge_flag.enc - flag encrypted with SHA256(f) as XOR key

so basically someone's faulty HSM leaked most of the private key and we gotta recover the rest lol

the solve

ok so first things first - Falcon-512 works in the ring Z_q[x]/(x^512 + 1) where q = 12289. the private key is two short polynomials f and g where f * h = g mod q (h is the public key). "short" here means coefficients are tiny - like between -12 and 10.

we got 436 out of 512 coefficients of f. only 76 missing. the key insight is this becomes an LWE problem:

where:

• s = the 76 unknown coefficients (small, bounded by ~12)
• A_U = rows of the public rotation matrix at unknown positions (76 x 512)
• e = -g the other secret polynomial (also small)
• c = -f_known * A mod q (computable from what we know)

76 unknowns, 512 equations, small secret AND small error, q = 12289. this is a baby LWE instance lmao

lattice go brrr

built a Kannan embedding lattice - pick m'=90 samples from the 512 equations, construct a (90 + 76 + 1) = 167 dimensional lattice:

the target short vector (e, -s, 1) is hiding in this lattice. ran LLL first (didn't find it), then BKZ with block size 10 and boom:

from fpylll import IntegerMatrix, LLL, BKZ

m_prime = 90
d = m_prime + 76 + 1  # 167

M = IntegerMatrix(d, d)

# q*I block
for i in range(m_prime):
    M[i, i] = q

# A^T block
for k in range(num_unknown):
    ui = unknown_indices[k]
    for j in range(m_prime):
        M[m_prime + k, j] = int(A[ui][j]) % q
    M[m_prime + k, m_prime + k] = 1

# target row
for j in range(m_prime):
    M[d - 1, j] = c[j]
M[d - 1, d - 1] = 1

LLL.reduction(M)
par = BKZ.Param(block_size=10, max_loops=8)
BKZ.reduction(M, par)

found it instantly - max|s|=9, max|e|=11. all the recovered values were small as expected.

why it works

quick math: the gaussian heuristic says the shortest vector in a random 167-dim lattice with our determinant should be ~340ish. our target vector has norm ~54. thats like a 6x gap. BKZ-10 eats this for breakfast fr

decrypt

once we have all 512 coefficients of f, just SHA256 hash it and XOR decrypt:

f_arr = np.array(f_full, dtype=np.int64)
key = hashlib.sha256(f_arr.tobytes()).digest()
flag = bytes([b ^ key[i % len(key)] for i, b in enumerate(enc_bytes)])

verified by checking that g = f * A mod q is also short (max|g| = 14). we good

flag

BITSCTF{h1nts_4r3_p0w3rfu1_4nd_f4lc0ns_4r3_f4st}

ngl this was a clean challenge. 436/512 leaked coefficients turns a "post-quantum hard" problem into a baby lattice reduction that BKZ-10 solves in seconds. moral of the story: partial key leaks are devastating even for lattice-based crypto

smothy out ✌️