Weave / ph1nx_ Writeup

Flag

UMDCTF{l01dr34u_l4mbda3_brick5_th3_w34v3_but_th3_trapd00r_unsp00ls_1t}

What the challenge is doing

The challenge builds a secret key from a hidden vector over the field $GF(2^{43})$, then uses that key to AES-GCM encrypt the flag.

The important parts are:

• A public Gabidulin-style linear map generated from pegs.
• A secret knot matrix that mixes the secret.
• A shuttle matrix that is built from a 3-dimensional fiber subspace.
• A ciphertext in vault encrypted with SHA-256(secret_bytes)[:16].

The job is to recover the secret vector, derive the AES key, and decrypt the vault.

The structure hidden in the output

The generator does this:

• It samples pegs, a length-40 list of independent field elements.
• It builds a loom matrix from Frobenius powers of those pegs.
• It samples a random invertible knot matrix of size 8 x 8.
• It samples a 3-dimensional space fibers and uses it to build shuttle.
• It computes

$$warp = knot \cdot loom \cdot shuttle^{-1}$$

and then publishes warp, bolt, loom, and vault.

The secret is hidden in

$$bolt = secret \cdot warp + frays$$

where frays is a low-rank perturbation coming from a 5-dimensional random space.

Why the flag is recoverable

The key observation is that the overall construction is still linear over the base field. The shuttle matrix compresses the random frays into a rank-limited additive disturbance, while the loom matrix is a Gabidulin encoding over $GF(2^{43})$.

So the attack is not brute force. The recoverable structure is:

1. Use the published shuttle to move the received word into the code domain.
2. Treat the result as a Gabidulin codeword plus a bounded-rank error.
3. Decode the message polynomial.
4. Undo knot to recover the secret vector.
5. Hash the recovered secret bytes to get the AES key.
6. Decrypt vault.

What did not work first

A few trial-and-error attempts were useful:

• Treating the frays term as if it stayed inside the original 3-dimensional fiber span after multiplication by shuttle failed. That produced inconsistent linear equations.
• A direct bit-level elimination over the expanded $GF(2)$ system also failed for the same reason: the error lives in the transformed space, not the original span.
• The successful model was to recognize the post-shuttle object as a rank-bounded Gabidulin decoding problem.

That is the reason the first linearization attempt failed but the later decoding-based approach worked.

The decoding idea

The clean algebraic model is:

$$received = f(peg) + e$$

where f is the message linearized polynomial and e is a rank-bounded error term.

For Gabidulin codes, the standard way to decode is to build an error-span polynomial E and an interpolant N such that

$$N(x) = E(f(x))$$

and then recover f from that composition.

In this challenge, the effective error rank is 15 after the shuttle mixing, which still sits inside the unique decoding radius for the code parameters used here.

Why the final decoder works

The solver does four things:

1. Reconstructs arithmetic in $GF(2^{43})$ using the irreducible polynomial from the challenge.
2. Solves the interpolation system for the composition polynomial.
3. Recovers the message coefficients by descending recursion on the linearized polynomial.
4. Inverts knot, hashes the secret, and decrypts the AES-GCM ciphertext.

The final validation checks are important:

• The interpolation identity is verified before trying AES.
• The recovered secret is checked against knot before deriving the key.
• AES-GCM authentication confirms the derivation is correct.

Full solver

The working code is in solve.py. It is reproduced here for convenience:

import json
from hashlib import sha256

from Crypto.Cipher import AES


MOD_BITS = (1 << 21) | (1 << 3) | (1 << 1) | 1
MASK = (1 << 43) - 1
NUM_FIELD_BITS = 43
NUM_SECRET_WORDS = 8
NUM_COORDS = 40
ERROR_RANK = 15


def mul(a, b):
    res = 0
    aa = a
    bb = b
    while bb:
        if bb & 1:
            res ^= aa
        bb >>= 1
        aa <<= 1
        if aa >> NUM_FIELD_BITS:
            aa &= MASK
            aa ^= MOD_BITS
    return res & MASK


def sqr(a):
    return mul(a, a)


def pow_field(a, e):
    result = 1
    base = a
    while e:
        if e & 1:
            result = mul(result, base)
        e >>= 1
        if e:
            base = sqr(base)
    return result


def inv(a):
    if a == 0:
        raise ZeroDivisionError
    return pow_field(a, (1 << NUM_FIELD_BITS) - 2)


def vec_mat_mul(v, m):
    out = []
    for j in range(len(m[0])):
        acc = 0
        for i, vi in enumerate(v):
            acc ^= mul(vi, m[i][j])
        out.append(acc)
    return out


def mat_inv(m):
    n = len(m)
    aug = [row[:] + [0] * n for row in m]
    for i in range(n):
        aug[i][n + i] = 1

    r = 0
    for c in range(n):
        pivot = None
        for i in range(r, n):
            if aug[i][c] != 0:
                pivot = i
                break
        if pivot is None:
            raise ValueError('singular matrix')
        aug[r], aug[pivot] = aug[pivot], aug[r]
        pivot_inv = inv(aug[r][c])
        for j in range(2 * n):
            aug[r][j] = mul(aug[r][j], pivot_inv)
        for i in range(n):
            if i != r and aug[i][c] != 0:
                factor = aug[i][c]
                for j in range(2 * n):
                    aug[i][j] ^= mul(factor, aug[r][j])
        r += 1
    return [row[n:] for row in aug]


def solve_linear_system_field(matrix, rhs):
    n_vars = len(matrix[0])
    pivots = {}

    for row, rhs_value in zip(matrix, rhs):
        vec = row[:]
        value = rhs_value
        while True:
            col = None
            for idx in range(n_vars - 1, -1, -1):
                if vec[idx] != 0:
                    col = idx
                    break
            if col is None:
                if value != 0:
                    raise ValueError('inconsistent system')
                break
            if col in pivots:
                prow, prhs = pivots[col]
                factor = vec[col]
                for idx in range(n_vars):
                    if prow[idx] != 0:
                        vec[idx] ^= mul(factor, prow[idx])
                value ^= mul(factor, prhs)
            else:
                inv_piv = inv(vec[col])
                for idx in range(n_vars):
                    if vec[idx] != 0:
                        vec[idx] = mul(vec[idx], inv_piv)
                value = mul(value, inv_piv)
                pivots[col] = (vec, value)
                break

    memo = {}

    def solve(col):
        if col in memo:
            return memo[col]
        if col not in pivots:
            memo[col] = 0
            return 0
        row, value = pivots[col]
        result = value
        for idx in range(col):
            if row[idx] != 0:
                result ^= mul(row[idx], solve(idx))
        memo[col] = result
        return result

    return [solve(i) for i in range(n_vars)]


def parse_vec(xs):
    return [int(x) for x in xs]


def parse_mat(ms):
    return [parse_vec(row) for row in ms]


def bits_to_field(bits):
    value = 0
    for i, bit in enumerate(bits):
        if bit:
            value |= 1 << i
    return value


def eval_linearized(coeffs, x):
    acc = 0
    for i, coeff in enumerate(coeffs):
        if coeff:
            acc ^= mul(coeff, pow_field(x, 1 << i))
    return acc


with open('output.json') as fh:
    data = json.load(fh)

pegs = parse_vec(data['loom']['pegs'])
knot = parse_mat(data['loom']['knot'])
shuttle = parse_mat(data['loom']['shuttle'])
bolt = parse_vec(data['bolt'])

received = vec_mat_mul(bolt, shuttle)

matrix = []
rhs = []
for i in range(NUM_COORDS):
    row = []
    g_pows = [pow_field(pegs[i], 1 << j) for j in range(NUM_SECRET_WORDS + ERROR_RANK)]
    r_pows = [pow_field(received[i], 1 << j) for j in range(ERROR_RANK)]
    for j in range(NUM_SECRET_WORDS + ERROR_RANK):
        row.append(g_pows[j])
    for j in range(ERROR_RANK):
        row.append(r_pows[j])
    matrix.append(row)
    rhs.append(pow_field(received[i], 1 << ERROR_RANK))

coeffs = solve_linear_system_field(matrix, rhs)
n_coeffs = coeffs[: NUM_SECRET_WORDS + ERROR_RANK]
e_coeffs = coeffs[NUM_SECRET_WORDS + ERROR_RANK :] + [1]

for i in range(NUM_COORDS):
    left = eval_linearized(n_coeffs, pegs[i])
    right = eval_linearized(e_coeffs, received[i])
    if left != right:
        raise ValueError('interpolation check failed')

f_coeffs = [0] * NUM_SECRET_WORDS
for m in range((NUM_SECRET_WORDS + ERROR_RANK - 1), ERROR_RANK - 1, -1):
    accum = n_coeffs[m]
    for a in range(ERROR_RANK):
        j = m - a
        if 0 <= j < NUM_SECRET_WORDS:
            accum ^= mul(e_coeffs[a], pow_field(f_coeffs[j], 1 << a))
    if m >= ERROR_RANK and m - ERROR_RANK < NUM_SECRET_WORDS:
        f_coeffs[m - ERROR_RANK] = pow_field(accum, 1 << (NUM_FIELD_BITS - ERROR_RANK))

t = f_coeffs

knot_inv = mat_inv(knot)
secret = vec_mat_mul(t, knot_inv)

if vec_mat_mul(secret, knot) != t:
    raise ValueError('knot inversion check failed')

secret_bytes = b''.join(int(v).to_bytes((NUM_FIELD_BITS + 7) // 8, 'big') for v in secret)
wrap_key = sha256(secret_bytes).digest()[:16]

iv = bytes.fromhex(data['vault']['iv'])
body = bytes.fromhex(data['vault']['body'])
tag = bytes.fromhex(data['vault']['tag'])

cipher = AES.new(wrap_key, AES.MODE_GCM, nonce=iv)
flag = cipher.decrypt_and_verify(body, tag)

print(flag.decode())

Flag meaning

The flag itself is written in leetspeak and mirrors the challenge theme: weaving, lambda-style algebra, bricks, and a trapdoor effect. Read normally, it points to the idea that the weave looks tangled, but once the right algebraic structure is recovered, the hidden trapdoor opens cleanly.

Summary

The solve is a rank-metric decoding problem disguised as matrix gibberish. The key was to stop treating the disturbance as a simple span issue and instead decode the Gabidulin-style structure after the shuttle transform. Once that was done, the secret, AES key, and flag all fell out deterministically.