weave — UMDCTF

Description

No organizer description was included in the provided workspace files.

English summary: the handout gives a field construction over GF(2^43), a leaked Moore-code structure (pegs, knot, shuttle), a noisy linear combination called bolt, and an AES-GCM-encrypted vault. The goal is to recover the hidden secret vector well enough to derive the AES key and decrypt the flag.

Analysis

Reading chall.sage shows that the challenge works in GF(2^43) with modulus:

x^43 + x^21 + x^3 + x + 1

The public code parameters are K = 8 and N = 40. The script samples N independent field elements called pegs and builds the K x N Moore matrix

loom[j, i] = pegs[i]^(2^j)

Then it samples an invertible knot, a structured invertible shuttle, and defines

warp = knot * loom * shuttle^{-1}
bolt = secret * warp + frays

The important leak is that knot and shuttle are both given to us, along with the original pegs. That means we can rewrite the received value into the natural Gabidulin code domain. Multiplying on the right by shuttle gives

y = bolt * shuttle
  = (secret * knot) * loom + frays * shuttle
  = t * loom + e

where t = secret * knot and e = frays * shuttle.

Now the structure of the error matters. In the generator, frays is built from a rank-<= 5 binary matrix, so its GF(2)-rank is at most 5. Also, every entry of shuttle lies in the GF(2)-span of only 3 leaked fibers, so multiplying by shuttle can enlarge the error support by at most a factor of 3. Therefore:

rank_GF(2)(e) <= 5 * 3 = 15

So y is a length-40 Gabidulin/Moore codeword of dimension 8 corrupted by rank error t <= 15. That is exactly the setting needed for rank-metric decoding.

The solve script implements arithmetic for GF(2^43) directly in Python, including multiplication, inversion, matrix inversion, and linearized polynomial operations. To decode, it uses a Welch-Berlekamp/Gao-style linearized interpolation step: find nonzero linearized polynomials V and N such that

V(y_i) = N(g_i)

for each peg g_i, with bounds

deg_q(V) <= t
deg_q(N) <= k + t - 1

Once such a pair is found, the message polynomial f satisfies

N = V o f

so left-dividing N by V recovers f. Its coefficients are exactly the vector t = secret * knot. Since knot is leaked and invertible, we finally compute:

secret = t * knot^{-1}

The challenge derives the AES key as sha256(pack(secret))[:16], so recovering secret is enough to decrypt the GCM vault and obtain the flag.

Solution

1. Read chall.sage and identify the rank-metric construction over GF(2^43).
2. Notice that loom is a Moore matrix built from leaked pegs, and that both knot and shuttle are also leaked.
3. Rewrite the public ciphertext as y = bolt * shuttle = (secret * knot) * loom + e.
4. Bound the error rank: frays has binary rank at most 5, while shuttle entries lie in a 3-dimensional GF(2) subspace, so the new error rank is at most 15.
5. Treat y as a received Gabidulin codeword with parameters (n, k) = (40, 8) and error rank <= 15.
6. Build the interpolation system for linearized polynomials V and N satisfying V(y_i) = N(g_i).
7. Solve the homogeneous system for a nontrivial nullspace vector, normalize V, and left-divide N by V to recover the message polynomial.
8. Extract t_vec = secret * knot, invert knot, and recover secret.
9. Pack the secret coefficients exactly like the challenge, derive sha256(secret_bytes)[:16], and decrypt the AES-GCM vault.
10. Running the local solve script prints the flag and confirms the decoded error rank is 15.

#!/usr/bin/env python3
import json
from hashlib import sha256
from pathlib import Path

from Crypto.Cipher import AES

TASK = Path(__file__).resolve().parent
DATA = json.loads((TASK / "output.json").read_text())

M = 43
K = 8
N = 40
MOD = (1 << 43) | (1 << 21) | (1 << 3) | (1 << 1) | 1
MASK = (1 << 43) - 1


def gf_mul(a: int, b: int) -> int:
    res = 0
    while b:
        if b & 1:
            res ^= a
        b >>= 1
        a <<= 1
        if a >> 43:
            a ^= MOD
    return res & MASK


def gf_square(a: int) -> int:
    return gf_mul(a, a)


def gf_pow(a: int, e: int) -> int:
    r = 1
    while e:
        if e & 1:
            r = gf_mul(r, a)
        e >>= 1
        if e:
            a = gf_mul(a, a)
    return r


def gf_inv(a: int) -> int:
    if a == 0:
        raise ZeroDivisionError
    return gf_pow(a, (1 << M) - 2)


def gf_div(a: int, b: int) -> int:
    return gf_mul(a, gf_inv(b))


def gf_qpow(a: int, j: int) -> int:
    for _ in range(j % M):
        a = gf_square(a)
    return a


def vec_mat_mul(v, mat):
    out = [0] * len(mat[0])
    for i, vi in enumerate(v):
        if vi == 0:
            continue
        for j, mij in enumerate(mat[i]):
            out[j] ^= gf_mul(vi, mij)
    return out


def mat_inv(mat):
    n = len(mat)
    aug = [row[:] + [1 if i == j else 0 for j in range(n)] for i, row in enumerate(mat)]
    for col in range(n):
        piv = next((r for r in range(col, n) if aug[r][col]), None)
        if piv is None:
            raise ValueError("singular matrix")
        aug[col], aug[piv] = aug[piv], aug[col]
        scale = gf_inv(aug[col][col])
        aug[col] = [gf_mul(x, scale) for x in aug[col]]
        for r in range(n):
            if r != col and aug[r][col]:
                f = aug[r][col]
                aug[r] = [aug[r][c] ^ gf_mul(f, aug[col][c]) for c in range(2 * n)]
    return [row[n:] for row in aug]


def gf2_rank(values):
    basis = []
    for x in values:
        v = x
        for b in basis:
            v = min(v, v ^ b)
        if v:
            basis.append(v)
            basis.sort(reverse=True)
    return len(basis)


def qpoly_eval(coeffs, x):
    acc = 0
    cur = x
    for c in coeffs:
        if c:
            acc ^= gf_mul(c, cur)
        cur = gf_square(cur)
    return acc


def qpoly_compose(a, b):
    out = [0] * (len(a) + len(b) - 1)
    for i, ai in enumerate(a):
        if ai == 0:
            continue
        for j, bj in enumerate(b):
            if bj == 0:
                continue
            out[i + j] ^= gf_mul(ai, gf_qpow(bj, i))
    while out and out[-1] == 0:
        out.pop()
    return out or [0]


def qpoly_div_left(numer, denom):
    numer = numer[:]
    while numer and numer[-1] == 0:
        numer.pop()
    while denom and denom[-1] == 0:
        denom.pop()
    if not denom:
        raise ZeroDivisionError
    if len(numer) < len(denom):
        return [0], numer or [0]

    q = [0] * (len(numer) - len(denom) + 1)
    r = numer[:]
    d = len(denom) - 1
    while r and len(r) - 1 >= d:
        j = len(r) - len(denom)
        lead = gf_qpow(gf_div(r[-1], denom[-1]), M - d)
        q[j] = lead
        sub = qpoly_compose(denom, [0] * j + [lead])
        if len(sub) > len(r):
            r += [0] * (len(sub) - len(r))
        for i in range(len(sub)):
            r[i] ^= sub[i]
        while r and r[-1] == 0:
            r.pop()
    return q, r or [0]


def nullspace_one(mat):
    a = [row[:] for row in mat]
    rows, cols = len(a), len(a[0])
    pivots = []
    r = 0
    for c in range(cols):
        piv = next((i for i in range(r, rows) if a[i][c]), None)
        if piv is None:
            continue
        a[r], a[piv] = a[piv], a[r]
        scale = gf_inv(a[r][c])
        a[r] = [gf_mul(x, scale) for x in a[r]]
        for i in range(rows):
            if i != r and a[i][c]:
                f = a[i][c]
                a[i] = [a[i][j] ^ gf_mul(f, a[r][j]) for j in range(cols)]
        pivots.append((r, c))
        r += 1
        if r == rows:
            break

    pivot_cols = {c for _, c in pivots}
    free_cols = [c for c in range(cols) if c not in pivot_cols]
    if not free_cols:
        return None

    x = [0] * cols
    x[free_cols[0]] = 1
    for r, c in reversed(pivots):
        s = 0
        for j in range(c + 1, cols):
            if a[r][j] and x[j]:
                s ^= gf_mul(a[r][j], x[j])
        x[c] = s
    return x


def decode_gabidulin(pegs, recv, k, max_t):
    for t in range(max_t + 1):
        system = []
        for g, y in zip(pegs, recv):
            row = []
            cur = y
            for _ in range(t + 1):
                row.append(cur)
                cur = gf_square(cur)
            cur = g
            for _ in range(k + t):
                row.append(cur)
                cur = gf_square(cur)
            system.append(row)

        sol = nullspace_one(system)
        if sol is None:
            continue

        v = sol[: t + 1]
        n = sol[t + 1 :]
        if v[-1] == 0:
            continue

        scale = gf_inv(v[-1])
        v = [gf_mul(c, scale) for c in v]
        n = [gf_mul(c, scale) for c in n]
        f, rem = qpoly_div_left(n, v)
        if any(rem):
            continue

        f += [0] * (k - len(f))
        codeword = [qpoly_eval(f, g) for g in pegs]
        err = [a ^ b for a, b in zip(recv, codeword)]
        if gf2_rank(err) <= t:
            return t, f, codeword, err
    raise ValueError("decoding failed")


def main():
    pegs = DATA["loom"]["pegs"]
    knot = DATA["loom"]["knot"]
    shuttle = DATA["loom"]["shuttle"]
    bolt = DATA["bolt"]

    y = vec_mat_mul(bolt, shuttle)
    t_rank, t_vec, _, err = decode_gabidulin(pegs, y, K, 16)
    secret = vec_mat_mul(t_vec, mat_inv(knot))

    secret_bytes = b"".join(int(x).to_bytes((M + 7) // 8, "big") for x in secret)
    key = sha256(secret_bytes).digest()[:16]

    vault = DATA["vault"]
    flag = AES.new(key, AES.MODE_GCM, nonce=bytes.fromhex(vault["iv"])).decrypt_and_verify(
        bytes.fromhex(vault["body"]), bytes.fromhex(vault["tag"])
    )

    print(f"decoded rank = {t_rank}")
    print(f"error rank   = {gf2_rank(err)}")
    print(flag.decode())


if __name__ == "__main__":
    main()

The script decodes the corrupted Gabidulin codeword, reconstructs the secret, derives the AES key, and successfully decrypts the vault to the provided flag.