WEAVE

"every piece of the cipher lies open on the table. compose them correctly and the flag is yours."

Challenge Files

• output.json — public parameters + ciphertext
• chall.sage — encryption scheme source

Scheme Analysis

Parameters

The scheme is instantiated with the following parameters:

Key Generation

The private key is a triplet decomposition of the public matrix:

• loom — a Moore matrix over GF(2⁴³):
  loom[j][i] = pegs[i]^2j
• knot — a random invertible 8×8 matrix over GF(2⁴³)
• shuttle — a 40×40 matrix whose entries lie in a 3-dimensional GF(2)-subspace spanned by fibers
• warp — the public 8×40 matrix

Encryption

• secret ∈ GF(2⁴³)⁸ — the plaintext (derived from flag)
• frays = u × B where u ∈ GF(2⁴³)⁵ (random), B is a 5×40 GF(2) matrix of rank 5
• The flag is encrypted as AES-GCM(SHA256(secret)[:16], flag)

The frays term is the rank-metric "noise" that makes naive inversion hard without the private key decomposition.

The Attack

Our attack follows a structured path to undo the scrambling and decode the ciphertext:

1. Recognise the Gabidulin Structure

We multiply both sides of the encryption equation bolt = secret × warp + frays on the right by the private shuttle matrix:

Defining:

• y = bolt × shuttle (received word, 1×40)
• s = secret × knot (encoded message, 1×8)
• e = frays × shuttle (error vector, 1×40)

The relation becomes:

This is exactly a received word of a Gabidulin[N=40, K=8] code with error e.

2. Bound the Error Rank

The rank of the error vector e = frays × shuttle in GF(2⁴³)⁴⁰ is bounded by:

Since each entry of frays × shuttle is a linear combination over GF(2) of the 15 products {fibers[k] × u[l]}, the maximum rank of e is 15. Since a Gabidulin code of minimum rank distance d = N - K + 1 = 33 can correct up to 16 errors, and 15 ≤ 16, the error is fully decodable.

3. Berlekamp-Welch for Rank-Metric Codes

To find the error support, we search for a monic linearized polynomial Λ of q-degree t ≤ 15 (the error annihilator) such that Λ(e[i]) = 0 for all i. By linearity:

where P = Λ ∘ L_s is a composed linearized polynomial of q-degree K + t - 1. This gives the key equation system (setting λ_t = 1):

With K + 2t = 38 unknowns and N = 40 equations, this overdetermined system has a unique solution.

4. Extract the Secret

Once p and λ are recovered, we invert the skew-polynomial composition via back-substitution to solve for s₀, s₁, ..., s₇:

Finally, we recover the original secret vector:

Solver

Below is the SageMath/Python solver to perform the rank-metric decoding and decrypt the flag:

import json
from hashlib import sha256
from Crypto.Cipher import AES

MOD = (1 << 43) | (1 << 21) | (1 << 3) | (1 << 1) | 1

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

def gf_inv(a):
    e = (1 << 43) - 2
    r, base = 1, a
    while e:
        if e & 1: r = gf_mul(r, base)
        base = gf_mul(base, base)
        e >>= 1
    return r

def gf_qpow(e, j):
    for _ in range(j): e = gf_mul(e, e)
    return e

def fqm_rref(A, nrows, ncols):
    A = [list(row) for row in A]
    pivots = []
    r = 0
    for c in range(ncols):
        piv = next((i for i in range(r, nrows) if A[i][c]), None)
        if piv is None: continue
        A[r], A[piv] = A[piv], A[r]
        inv_p = gf_inv(A[r][c])
        A[r] = [gf_mul(x, inv_p) for x in A[r]]
        for i in range(nrows):
            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(ncols)]
        pivots.append(c)
        r += 1
    return A, pivots

def fqm_mat_inv(A, n):
    A = [list(row) + [1 if i==j else 0 for j in range(n)] for i, row in enumerate(A)]
    for c in range(n):
        piv = next((r for r in range(c, n) if A[r][c]), None)
        A[c], A[piv] = A[piv], A[c]
        inv_p = gf_inv(A[c][c])
        A[c] = [gf_mul(x, inv_p) for x in A[c]]
        for r in range(n):
            if r != c and A[r][c]:
                f = A[r][c]
                A[r] = [A[r][j] ^ gf_mul(f, A[c][j]) for j in range(2*n)]
    return [row[n:] for row in A]

def mat_mul(A, B, ra, ca, cb):
    C = [[0]*cb for _ in range(ra)]
    for i in range(ra):
        for k in range(ca):
            if not A[i][k]: continue
            for j in range(cb):
                if B[k][j]: C[i][j] ^= gf_mul(A[i][k], B[k][j])
    return C

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

K, N = 8, 40
bolt   = [int(v) for v in data['bolt']]
pegs   = [int(v) for v in data['loom']['pegs']]
knot   = [[int(v) for v in row] for row in data['loom']['knot']]
shuttle = [[int(v) for v in row] for row in data['loom']['shuttle']]
vault  = data['vault']

# Step 1: compute received word y = bolt × shuttle
y = mat_mul([bolt], shuttle, 1, N, N)[0]

# Step 2: Berlekamp-Welch with t = 15
t = 15
pegs_pow = [[gf_qpow(pegs[i], m) for m in range(K+t)] for i in range(N)]
y_pow    = [[gf_qpow(y[i], l)    for l in range(t+1)] for i in range(N)]

Aeq = [[pegs_pow[i][m] for m in range(K+t)] +
       [y_pow[i][l]    for l in range(t)]
       for i in range(N)]
beq = [y_pow[i][t] for i in range(N)]
Aug = [Aeq[i] + [beq[i]] for i in range(N)]

rref_aug, piv = fqm_rref(Aug, N, K + 2*t + 1)

sol = [0] * (K + 2*t)
for idx, pc in enumerate(piv):
    sol[pc] = rref_aug[idx][K + 2*t]

p_coeffs      = sol[:K+t]
lambda_coeffs = sol[K+t:] + [1]  # λ_t = 1

# Step 3: recover s via triangular back-substitution
lam0_inv = gf_inv(lambda_coeffs[0])
s = [0] * K
for m in range(K):
    rhs = p_coeffs[m]
    for l in range(1, min(m, t) + 1):
        rhs ^= gf_mul(lambda_coeffs[l], gf_qpow(s[m-l], l))
    s[m] = gf_mul(rhs, lam0_inv)

# Step 4: recover secret = s × knot⁻¹
knot_inv = fqm_mat_inv(knot, K)
secret   = mat_mul([s], knot_inv, 1, K, K)[0]

# Step 5: derive key and decrypt
secret_bytes = b''.join(x.to_bytes(6, 'big') for x in secret)
wrap_key = sha256(secret_bytes).digest()[:16]

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

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

Dead Ends & Lessons Learned

Flag