UMDCTF 2026 - Weave

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$ :

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:

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.
Build the original loom: Reconstruct $\mathsf{loom}$ from pegs using the same lambda.
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}$ .
Recover the secret: Multiply by $\mathsf{knot}^{-1}$ :
$s = s' \cdot \mathsf{knot}^{-1}$
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.
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}