Cyber

Platform: volgactf | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-03-28 | Status: Solved Techniques: babai_cvp, bkz_lattice_reduction, negacyclic_convolution_linearization, ring_lwe_small_dimension, triangular_matrix_exploitation

Summary

Task: Custom Kyber-like Module-LWE encryption with N=80, K=2, q=3329; public key matrix A has a zero sub-block making it triangular. Solution: exploit triangular structure to decompose into independent Ring-LWE instances, solve each via BKZ lattice reduction + Babai CVP, recover encryption randomness, then decrypt.

Cyber — VolgaCTF 2026

Description

The future does not scare us - we are ready!

A custom post-quantum encryption scheme inspired by Kyber (Module-LWE). Given files: cipher.py (full implementation), key.pub (public key), flag.txt.enc (encrypted flag), requirements.txt (numpy). The scheme operates in the ring R_q = Z_q[X]/(X^N+1) with parameters q=3329, N=80, K=2, eta1=eta2=2. The goal is to decrypt the flag without the private key.

Analysis

Scheme overview

The cipher implements a standard Module-LWE public key encryption: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

• Key generation: Random K×K matrix A of polynomials, small secret s and error e (CBD with eta=2, coefficients in {-2,-1,0,1,2}). Public key: (A, t = A·s + e).
• Encryption: For message polynomial m, sample random r, e1, e2 (all small CBD). Compute u = A^T·r + e1, v = ⟨t, r⟩ + e2 + m·⌊(q+1)/2⌋.
• Decryption: Compute v - ⟨s, u⟩ to get noisy message, round to recover bits.

Critical parameter choice: N=80

The code includes a full NTT implementation, but N=80 is not a power of two, so the NTT check _ntt_supported(Q, N) fails and the code falls back to O(N²) negacyclic convolution. This is a hint that the parameters are intentionally weakened — standard Kyber uses N=256. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The vulnerability: triangular public key matrix

Inspecting the public key reveals that A[0,1] contains only values 0 and 3329. Since 3329 ≡ 0 (mod q=3329), the entire sub-block A[0,1] is zero modulo q. This makes the 2×2 polynomial matrix A effectively upper-triangular:

A = [[A[0,0],    0   ],
     [A[1,0],  A[1,1]]]

This structural flaw completely breaks the Module-LWE security. The ciphertext equation u = A^T · r + e1 decomposes:

u[0] = A[0,0]·r[0] + A[1,0]·r[1] + e1[0]
u[1] = A[1,1]·r[1] + e1[1]           ← depends only on r[1]!

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Each equation is a single Ring-LWE instance with dimension N=80, which is small enough to solve via lattice reduction.

Attack strategy

1. Solve for r[1] from u[1] = A[1,1]·r[1] + e1[1] — a single Ring-LWE instance
2. Solve for r[0] from u[0] - A[1,0]·r[1] = A[0,0]·r[0] + e1[0] — another Ring-LWE instance
3. Decrypt using recovered r: m_noisy = v - ⟨t, r⟩, then round to bits

Solution

Step 1: Lattice construction for Ring-LWE

For a polynomial equation a·x + e ≡ u (mod q) in Z_q[X]/(X^N+1) with small x and e, we linearize using the negacyclic convolution matrix. If M is the N×N matrix representing multiplication by a, then: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

M·x + e ≡ u (mod q)

We build a 2N×2N lattice basis:

B = [ q·I_N  |   0   ]   ← N rows
    [   M    |  I_N  ]   ← N rows

A lattice vector with coefficients (y, x) gives (q·y + M·x, x). When x is the secret, the first N coordinates equal e (mod q), which is small. After BKZ reduction, Babai's nearest plane algorithm finds the closest lattice vector to the target (u, 0), recovering both x and e.

Step 2: BKZ reduction (one-time per polynomial)

The lattice is reduced with LLL followed by BKZ with block_size=40 and max_loops=6. This takes ~2.5 minutes per basis but only needs to be done twice (once for A[1,1] and once for A[0,0]). The reduced basis is then reused for all 9 ciphertext blocks via Babai's CVP. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step 3: Recover randomness and decrypt

For each ciphertext block:

1. Use Babai CVP with the A[1,1] basis to recover r[1] from u[1]
2. Subtract A[1,0]·r[1] from u[0], then use Babai CVP with the A[0,0] basis to recover r[0]
3. Compute v - t[0]·r[0] - t[1]·r[1] to get the noisy message polynomial
4. Round each coefficient: closer to 0 → bit 0, closer to q/2 → bit 1
5. Convert bits to bytes and remove PKCS#7 padding

Full solve script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import struct

import numpy as np
from fpylll import BKZ, GSO, LLL, IntegerMatrix
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Q = 3329
N = 80
K = 2


def negacyclic_matrix(a):
    """Build N×N matrix for multiplication by polynomial a in Z_q[X]/(X^N+1)."""
    m = np.zeros((N, N), dtype=int)
    a = np.array(a, dtype=int) % Q
    for i in range(N):
        for j in range(N):
            idx = i - j
            if idx < 0:
                idx += N
                m[i, j] = -int(a[idx])
            else:
                m[i, j] = int(a[idx])
    return m


def prep_decoder(a, block_size=40, loops=6):
    """Build and BKZ-reduce the Ring-LWE lattice for polynomial a.
    Returns GSO object and basis rows for Babai CVP."""
    m = negacyclic_matrix(a)
    basis = IntegerMatrix(2 * N, 2 * N)
    for i in range(N):
        basis[i, i] = Q
    for j in range(N):
        for i in range(N):
            basis[N + j, i] = int(m[i, j])
        basis[N + j, N + j] = 1
    LLL.reduction(basis)
    BKZ.reduction(basis, BKZ.Param(block_size=block_size, max_loops=loops))
    gso = GSO.Mat(basis)
    gso.update_gso()
    rows = [[int(basis[i, j]) for j in range(2 * N)] for i in range(2 * N)]
    return gso, rows
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍


def solve_ring_eq(gso, rows, u):
    """Solve a·x + e ≡ u (mod q) using Babai's nearest plane on pre-reduced basis."""
    target = [int(x) % Q for x in u] + [0] * N
    coeffs = gso.babai(tuple(target))
    vec = [0] * len(target)
    for c, row in zip(coeffs, rows):
        if c:
            cc = int(c)
            for i, v in enumerate(row):
                vec[i] += cc * v
    diff = [target[i] - vec[i] for i in range(2 * N)]
    e = np.array(diff[:N], dtype=int)
    x = np.array([-d for d in diff[N:]], dtype=int)
    return x, e
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍


def poly_mul(a, b):
    """Negacyclic polynomial multiplication in Z_q[X]/(X^N+1)."""
    aa = np.array(a, dtype=np.int64) % Q
    bb = np.array(b, dtype=np.int64) % Q
    out = np.zeros(N, dtype=np.int64)
    for i in range(N):
        ai = int(aa[i])
        if ai == 0:
            continue
        for j in range(N):
            idx = i + j
            prod = ai * int(bb[j])
            if idx >= N:
                out[idx - N] -= prod
            else:
                out[idx] += prod
    return out % Q
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍


def poly_to_bits(poly):
    """Decode polynomial coefficients to bits by rounding to {0, q/2}."""
    out = []
    half_q = Q // 2
    for i in range(N):
        c = int(poly[i]) % Q
        dist_zero = min(c, Q - c)
        dist_one = min(abs(c - half_q), abs(c - (half_q + 1)))
        out.append(1 if dist_one < dist_zero else 0)
    return out


def bits_to_bytes(bits):
    out = bytearray((len(bits) + 7) // 8)
    for idx, bit in enumerate(bits):
        if bit & 1:
            out[idx // 8] |= 1 << (idx % 8)
    return bytes(out)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍


def unpad(data):
    pad = data[-1]
    if data[-pad:] != bytes([pad]) * pad:
        raise ValueError("bad padding")
    return data[:-pad]


def main():
    # Parse public key: 10-byte header, then A (K×K×N uint16), then t (K×N uint16)
    with open("key.pub", "rb") as f:
        data = f.read()
    a_len = K * K * N * 2
    A = np.frombuffer(data[10:10 + a_len], dtype="<u2").astype(int).reshape(K, K, N) % Q
    t = np.frombuffer(data[10 + a_len:], dtype="<u2").astype(int).reshape(K, N) % Q

    # Parse ciphertext: 10-byte header, 4-byte block count, then u and v arrays
    with open("flag.txt.enc", "rb") as f:
        data = f.read()
    blocks = struct.unpack("<I", data[10:14])[0]
    off = 14
    u = np.frombuffer(data[off:off + blocks * K * N * 2], dtype="<u2") \
        .astype(int).reshape(blocks, K, N) % Q
    off += blocks * K * N * 2
    v = np.frombuffer(data[off:off + blocks * N * 2], dtype="<u2") \
        .astype(int).reshape(blocks, N) % Q
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    # Key observation: A[0,1] ≡ 0 mod q → A is triangular
    # Prepare BKZ-reduced lattice decoders (one-time, ~2.5 min each)
    gso_d, rows_d = prep_decoder(A[1, 1])
    gso_a, rows_a = prep_decoder(A[0, 0])

    # Recover r[1] for each block from u[1] = A[1,1]·r[1] + e1[1]
    r1 = []
    for b in range(blocks):
        x, e = solve_ring_eq(gso_d, rows_d, u[b, 1])
        assert min(x) >= -2 and max(x) <= 2 and min(e) >= -2 and max(e) <= 2
        r1.append(x)

    # Recover r[0] for each block from u[0] - A[1,0]·r[1] = A[0,0]·r[0] + e1[0]
    r0 = []
    for b in range(blocks):
        rhs = (u[b, 0] - poly_mul(A[1, 0], r1[b])) % Q
        x, e = solve_ring_eq(gso_a, rows_a, rhs)
        assert min(x) >= -2 and max(x) <= 2 and min(e) >= -2 and max(e) <= 2
        r0.append(x)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    # Decrypt: v - <t, r> gives noisy message, round to recover bits
    bits = []
    for b in range(blocks):
        noisy = (v[b] - poly_mul(t[0], r0[b]) - poly_mul(t[1], r1[b])) % Q
        bits.extend(poly_to_bits(noisy))

    print(unpad(bits_to_bytes(bits)).decode())


if __name__ == "__main__":
    main()

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍