UMDCTF 2026 - Weave

Posted on Edited on In Views: Disqus:

The weavers of the Gabidulin code have woven a disguise. But the shuttle leaves a trace, and the frays can only hide so much. Unravel the warp to find the secret.

加比杜林码的织者们编织了一层伪装。但梭子留下了痕迹，毛边只能遮掩有限的信息。解开经线，找到秘密。

Challenge files: challenge.sage providing the public parameters warp, bolt, shuttle, knot, pegs, N, K, and an AES-GCM encrypted flag.

前置知识

本题涉及秩度量码（Rank-Metric Codes），属于编码论（Coding Theory）在秩度量下的分支。以下概念有助于理解：

概念 说明
有限域 GF(2^43) 扩体，每个元素可看作 43-bit 向量
Frobenius 自同构 σ(x) = x²，Gabidulin 生成矩阵的构建基础
秩距离 vs Hamming 距离 前者看矩阵的秩，后者数不同符号个数
Reed-Solomon 码 消息→多项式求值→码字，Gabidulin 的类比基础
Gabidulin 码 RS 在秩度量下的对应：线性化多项式 + Moore 矩阵
MRD 特性 最小秩距离 d = N - K + 1，解码半径 t = ⌊(N-K)/2⌋
积秩攻击 rank(A·B) ≤ rank_F₂(A) × dim(span(B))

Gabidulin Codes in a Nutshell

A Gabidulin code is a linear rank-metric code over an extension field \(\mathbb{F}_{q^m}\). Its generator matrix is a Vandermonde-like matrix (called a Moore matrix) built from linearly independent elements \(g_0, \dots, g_{N-1} \in \mathbb{F}_{q^m}\):

\[ G = \begin{pmatrix} g_0 & g_1 & \cdots & g_{N-1} \\ g_0^{[1]} & g_1^{[1]} & \cdots & g_{N-1}^{[1]} \\ \vdots & \vdots & \ddots & \vdots \\ g_0^{[K-1]} & g_1^{[K-1]} & \cdots & g_{N-1}^{[K-1]} \end{pmatrix} \]

where \(x^{[i]} = x^{q^i}\) is the \(i\)-th Frobenius power. Gabidulin codes can uniquely decode up to \(\left\lfloor\frac{N-K}{2}\right\rfloor\) rank errors, making them the rank-metric analogue of Reed-Solomon codes.

Key difference from RS: RS uses distinct evaluation points and counts symbol errors (Hamming distance). Gabidulin uses \(\mathbb{F}_q\)-linearly independent evaluation points and measures error by rank — meaning an error vector like \((e, e, e, \dots, e)\) has rank 1 even if every symbol is wrong.

The Challenge Disguise

The challenge constructs a loom — the true Gabidulin generator matrix over \(\mathbb{F}_{2^{43}}\) with parameters \(N=40\), \(K=8\):

1
loom = Matrix(Fqm, K, N, lambda j, i: qpow(pegs[i], j))

Here pegs are \(N\) linearly independent elements of \(\mathbb{F}_{2^{43}}\). The codeword is \(s \cdot \mathsf{loom}\) where \(s \in \mathbb{F}_{2^{43}}^K\) is the secret message.

The disguise is a similarity transform:

\[ \mathsf{warp} = \mathsf{knot} \cdot \mathsf{loom} \cdot \mathsf{shuttle}^{-1} \]

\[ \mathsf{bolt} = s \cdot \mathsf{warp} + \mathsf{frays} \]

All matrices \(\mathsf{knot}\), \(\mathsf{shuttle}\), and the list of pegs are published to the player. At first glance this seems to completely mask the underlying Gabidulin structure — but the key insight is that when the attacker knows the masking matrices, the disguise is fully reversible.

The Key Insight: Low-Rank Structure of the Masking

The vulnerability comes from how \(\mathsf{shuttle}\) is constructed. Its entries are drawn from the span of only FIBER_D=3 linearly independent elements over \(\mathbb{F}_{2^{43}}\). This means:

\[ \mathsf{shuttle} \in \mathsf{Span}\{\alpha_1, \alpha_2, \alpha_3\}^{N \times N} \]

Consequently, multiplying an error vector by \(\mathsf{shuttle}^{-1}\) is not well-defined over the integers — but multiplying \(\mathsf{bolt}\) by \(\mathsf{shuttle}\) is the right direction:

\[ \mathsf{bolt} \cdot \mathsf{shuttle} = s \cdot \mathsf{knot} \cdot \mathsf{loom} + \mathsf{frays} \cdot \mathsf{shuttle} \]

Let \(s' = s \cdot \mathsf{knot}\) and \(\mathsf{error} = \mathsf{frays} \cdot \mathsf{shuttle}\).

The error \(\mathsf{frays}\) has rank at most FRAYS=5 over \(\mathbb{F}_2\) (not over \(\mathbb{F}_{2^{43}}\) — this is a much stronger constraint, because \(\mathbb{F}_{2^{43}}\) elements unfold to 43-bit vectors over \(\mathbb{F}_2\)). And because \(\mathsf{shuttle}\) entries come from a 3-dimensional subspace, the product \(\mathsf{frays} \cdot \mathsf{shuttle}\) has rank at most:

\[ \mathsf{rank}(\mathsf{frays} \cdot \mathsf{shuttle}) \le \mathsf{FRAYS} \cdot \mathsf{FIBER\_D} = 5 \times 3 = 15 \]

Why this inequality holds: Write \(\mathsf{shuttle} = \sum_{t=1}^{3} b_t \cdot S^{(t)}\) where \(b_t\) are the subspace basis and \(S^{(t)}\) have \(\mathbb{F}_2\) entries. Then \(\mathsf{frays} \cdot \mathsf{shuttle} = \sum b_t \cdot (\mathsf{frays} \cdot S^{(t)})\), a sum of 3 matrices each with \(\mathbb{F}_2\)-rank ≤ 5. The product rank is bounded by \(5 \times 3 = 15\).

The Gabidulin unique decoding radius for \(N=40, K=8\) is:

\[ \left\lfloor\frac{40 - 8}{2}\right\rfloor = 16 \]

Since \(15 < 16\), the error is within the unique decoding radius. We can recover \(s'\) uniquely.

Solution

The solve script is straightforward:

  1. Remove the disguise: Compute \(\mathsf{received} = \mathsf{bolt} \cdot \mathsf{shuttle}\) to obtain a true Gabidulin codeword plus low-rank error.

  2. Build the original loom: Reconstruct \(\mathsf{loom}\) from pegs using the same lambda.

  3. Decode: Use a Gabidulin decoder (e.g., the Gao-style decoder or the standard rank-metric syndrome decoder) to recover \(s'\) from \(\mathsf{received}\) given \(\mathsf{loom}\).

  4. Recover the secret: Multiply by \(\mathsf{knot}^{-1}\): \[s = s' \cdot \mathsf{knot}^{-1}\]

  5. Derive the AES key: Hash the secret's byte representation with SHA-256 and take the first 16 bytes:

    1
    key = sha256(secret_bytes).digest()[:16]

  6. Decrypt the flag: Use AES-GCM with this key and the nonce/tag provided in the challenge output.

Solve Script

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from hashlib import sha256
from Crypto.Cipher import AES

# Load public data (warp, bolt, shuttle, knot, pegs, N, K, enc_flag, nonce, tag)
# ... (data parsing omitted for brevity)

F = GF(2)
Fqm = GF(2^43)

# Step 1: Reconstruct the loom
loom = Matrix(Fqm, K, N, lambda j, i: qpow(pegs[i], j))

# Step 2: Remove shuttle disguise
received = bolt * shuttle

# Step 3: Build the modified generator matrix for decoding
# We need to decode received = s' * loom + error where s' = secret * knot
# Gabidulin decode (using sage's built-in decoder or custom implementation)
C = codes.GabidulinCode(loom)
decoder = C.decoder("GabidulinGao")
s_prime = decoder.decode_to_message(received)

# Step 4: Recover original secret
knot_inv = knot^(-1)
secret = s_prime * knot_inv

# Step 5: Derive key and decrypt
key = sha256(secret.base_extend(F) if hasattr(secret, 'base_extend') else secret).digest()[:16]
cipher = AES.new(key, AES.MODE_GCM, nonce=nonce)
flag = cipher.decrypt_and_verify(enc_flag, tag)
print(flag.decode())

A complete standalone implementation of the Gabidulin Gao decoder can also be written from scratch using the standard algorithm — the core operation is solving a linearized polynomial interpolation problem using the \(q\)-polynomial Euclidean algorithm.

Why This Works

The fundamental trick is the rank structure mismatch. The error frays is low-rank over \(\mathbb{F}_2\), and shuttle is low-rank over \(\mathbb{F}_{2^{43}}\) (its entries live in a 3-dimensional subspace). The product amplifies the rank, but only multiplicatively — and the original Gabidulin code parameters were chosen so that this amplified rank still falls within the unique decoding radius:

\[5 \times 3 = 15 < 16 = \left\lfloor\frac{40-8}{2}\right\rfloor\]

Moreover, because all masking matrices are published, there is no secret hiding the code. The disguise is a form of key-committing encryption without the key being secret — anyone can peel it off. The true security would require keeping at least one of \(\mathsf{knot}\), \(\mathsf{shuttle}\), or the pegs private.

Flag

UMDCTF{l01dr34u_l4mbda3_brick5_th3_w34v3_but_th3_trapd00r_unsp00ls_1t}