UMDCTF 2026 - Weave

Posted on In Views: Word count in article: 1.4k Reading time ≈ 5 mins.

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）在秩度量下的分支。以下概念有助于理解：

概念 说明
有限域 \(\operatorname{GF}(2^{43})\) 扩体，每个元素可看作 43-bit 向量
Frobenius 自同构 \(\sigma(x) = x^2\)，Gabidulin 生成矩阵的构建基础
秩距离 vs Hamming 距离 前者看差向量各坐标在基域上张成空间的维数，后者数不同符号个数
Reed-Solomon 码 消息→多项式求值→码字，Gabidulin 的类比基础
Gabidulin 码 RS 在秩度量下的对应：线性化多项式 + Moore 矩阵
MRD 特性 最小秩距离 \(d = N - K + 1\)，解码半径 \(t = \left\lfloor\frac{N-K}{2}\right\rfloor\)
积秩攻击 误差向量的 rank weight 上界为原 rank weight 与矩阵元素空间维数的乘积（定义与推导见下文）

For a vector \(v=(v_1,\ldots,v_N)\in\mathbb{F}_{q^m}^{N}\), define its rank weight over the base field by

\[ \operatorname{wt}_{R,q}(v) =\dim_{\mathbb{F}_q}\operatorname{span}_{\mathbb{F}_q}\{v_1,\ldots,v_N\}. \]

Equivalently, expand each coordinate in a fixed basis of the extension field over \(\mathbb{F}_q\) and take the rank of the resulting \(m\times N\) matrix over the base field. The rank distance between two vectors is the rank weight of their difference. In this challenge \(q=2\).

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 \(\mathbb{F}_q\)-linearly independent elements \(g_0, \dots, g_{N-1} \in \mathbb{F}_{q^m}\), with \(1\le K\le N\le 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 weight 1 when \(e\ne0\), 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\) elements of \(\mathbb{F}_{2^{43}}\) that are linearly independent over \(\mathbb{F}_2\). The codeword is \(s \cdot \mathsf{loom}\) where \(s \in \mathbb{F}_{2^{43}}^K\) is the secret message.

The disguise is a two-sided invertible transformation: \(\mathsf{knot}\) is \(K\times K\), \(\mathsf{loom}\) is \(K\times N\), and \(\mathsf{shuttle}\) is \(N\times N\), with all entries in \(\mathbb{F}_{2^{43}}\).

\[ \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-Dimensional Entry Space

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

\[ \begin{aligned} U&=\operatorname{span}_{\mathbb{F}_2}\{\alpha_1,\alpha_2,\alpha_3\},\\ \mathsf{shuttle}&\in U^{N\times N},\\ \dim_{\mathbb{F}_2}U&=3. \end{aligned} \]

All vector and matrix operations take place in the extension field. Right-multiplying \(\mathsf{bolt}\) by \(\mathsf{shuttle}\) cancels the inverse in \(\mathsf{warp}\); the entry-space dimension bound applies to \(\mathsf{shuttle}\) and need not hold for \(\mathsf{shuttle}^{-1}\):

\[ \begin{aligned} \mathsf{bolt}\cdot\mathsf{shuttle} &=s\cdot\mathsf{knot}\cdot\mathsf{loom}\\ &\quad+\mathsf{frays}\cdot\mathsf{shuttle}. \end{aligned} \]

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

The vector \(\mathsf{frays}\) has rank weight at most FRAYS=5 over the base field. Because the entries of \(\mathsf{shuttle}\) lie in a 3-dimensional \(\mathbb{F}_2\)-subspace, the transformed error satisfies:

\[ \begin{aligned} &\operatorname{wt}_{R,2}(\mathsf{frays}\cdot\mathsf{shuttle})\\ &\quad\le\mathsf{FRAYS}\cdot\mathsf{FIBER\_D}\\ &\quad=5\times3=15. \end{aligned} \]

Why this inequality holds: Write \(\mathsf{shuttle}=\sum_{t=1}^{3}\alpha_t S^{(t)}\), where \(S^{(t)}\in\mathbb{F}_2^{N\times N}\). Every coordinate of \(\mathsf{frays}\cdot S^{(t)}\) is a base-field linear combination of the coordinates of \(\mathsf{frays}\), so its rank weight is at most 5. Multiplication by the nonzero scalar \(\alpha_t\) preserves that weight; subadditivity then gives

\[ \begin{aligned} &\operatorname{wt}_{R,2}(\mathsf{frays}\cdot\mathsf{shuttle})\\ &\quad\le\sum_{t=1}^{3}\operatorname{wt}_{R,2}(\alpha_t\mathsf{frays}\cdot S^{(t)})\\ &\quad\le3\cdot5=15. \end{aligned} \]

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 mathematical recovery procedure is:

  1. Remove the disguise: Compute \(\mathsf{received} = \mathsf{bolt} \cdot \mathsf{shuttle}\) to obtain a true Gabidulin codeword plus an error of rank weight at most 15.

  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: Serialize the recovered extension-field vector exactly as the challenge does, then hash those bytes with SHA-256 and take the first 16 bytes. The following expression assumes secret_bytes has already been produced correctly:

    The key expression is key = sha256(secret_bytes).digest()[:16]. It requires sha256 from hashlib and the correctly serialized byte string.

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

Caveats

An extension-field vector must be explicitly serialized to bytes using the challenge's field representation, coordinate order and encoding. A change of base field does not perform that serialization, and a SageMath vector cannot be passed directly to SHA-256.

Why This Works

The error frays has base-field rank weight at most 5, while all entries of shuttle lie in a 3-dimensional base-field subspace. Since shuttle is invertible, its ordinary matrix rank over \(\mathbb{F}_{2^{43}}\) is \(N\); the useful bound concerns its entry space. Multiplication increases the error rank weight by at most a factor of 3, leaving it within the unique decoding radius:

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

The published masking matrices permit the transformation above, and the resulting error bound makes the stated Gabidulin instance uniquely decodable. Keeping a matrix or the evaluation points private would change the attack model; it does not by itself establish the security of a modified scheme.

Flag

UMDCTF{l01dr34u_l4mbda3_brick5_th3_w34v3_but_th3_trapd00r_unsp00ls_1t}