Scenario

Deep beneath the Ash-Vault rests a relic the Cinderbound once swore could preserve truth without ever revealing it, a public rite built from equations, guarded only by the silent calculations its keepers left behind before they vanished. Unravel those old protections and the words sealed inside may finally be read, along with whatever authority the realm hoped they'd bury for good.

Code Analysis & Cryptosystem Breakdown

I started by opening up source.sage to see what I was actually dealing with. It turned out to be a custom public-key encryption scheme built on Multivariate Public Key Cryptography — the kind of construction that echoes Hidden Field Equations (HFE) — operating over the finite field $\mathbb{F}_2 = \text{GF}(2)$ .

Key Generation (`source.sage`)

sage

q = 2

def keygen(n):
    K = GF(q)
    _vars = [f"x{i}" for i in range(1, n+1)]
    R = PolynomialRing(K, _vars, n)
    J = ideal([x^q-x for x in R.gens()])
    H = R.quotient_ring(J, _vars)

    S_B = random_vector(K, n)
    T_B = random_vector(K, n)
    while True:
        S_A, T_A = [matrix.random(K, n, n) for _ in range(2)]
        if not False in [S_A.is_singular(), T_A.is_singular()]:
            break

    S = (S_A, S_B)
    T = (T_A, T_B)

    Rv = vector(R, n, R.gens())
    Rv = S[0] * Rv + S[1]

    PRK.<x> = PolynomialRing(K)
    PRL.<t> = PolynomialRing(R)
    g = PRK.irreducible_element(n)
    g = PRL(g)
    I = PRL.ideal([g])
    Q = PRL.quotient_ring(I)
    
    F = PRL(Rv.list()[::-1])
    F = Q(F^(2*q)+F^q+1)

    PK = vector(R, n, F.list()[::-1])
    PK = T[0] * PK + T[1]

    return PK

Breaking down what I was looking at:

$q = 2$ , so every operation lives in $\mathbb{F}_2$ .
A linear transformation vector $R_v = S_A \cdot \mathbf{x} + S_B$ , where each entry is an affine linear combination of the input variables $x_1, \dots, x_N$ .
A polynomial $F(t) \in R[t]/(g(t))$ built out of $R_v$ .
A transformation $F \mapsto F^\bgroup 2q \egroup + F^q + 1 = F^4 + F^2 + 1 \pmod\bgroup g(t)\egroup$ .
A final affine transformation $PK = T_A \cdot \text{coefficients}(F) + T_B$ .

What caught my eye immediately: $S_A$ and $T_A$ were deliberately generated as singular matrices. That felt like the kind of detail a challenge author leaves in on purpose.

Encryption & Flag Protection

sage

encrypted_key = encrypt(KEY, PK)
AES_KEY = hashlib.sha256(str(KEY).encode()).digest()
cipher = AES.new(AES_KEY, AES.MODE_ECB)
enc_flag = cipher.encrypt(pad(FLAG, 16))

So a random 137-bit integer KEY gets generated, its bit array $\mathbf{m} \in \lbrace 0, 1 \rbrace^{137}$ gets fed into $PK(\mathbf{m})$ , and the result — encrypted_key — is what I'd get in output.txt. Separately, $\text{SHA-256}(\text{str}(KEY))$ becomes the AES-ECB key used to encrypt the flag. If I could recover KEY, the flag would fall right out.

Mathematical Vulnerability & Collapse to Linear System

Characteristic 2 Properties & Bit Domain Constraints

This is where the singular matrices started making sense to me. In any field or ring of characteristic 2 (like $\mathbb{F}_2$ ), the Frobenius automorphism gives me:

Frobenius Automorphism: $(a + b)^2 = a^2 + b^2 \pmod 2$ $(a + b)^4 = ((a + b)^2)^2 = a^4 + b^4 \pmod 2$

And because the input vector $\mathbf{x} = (x_1, \dots, x_{137})$ only ever represents bit values $x_i \in \lbrace 0, 1 \rbrace$ , I also get:

$x_i^2 = x_i \pmod 2, \quad x_i^4 = x_i \pmod 2$

That combination was the crack I needed.

Absence of Cross-Terms

Since $R_v[i]$ is just an affine linear polynomial $\sum_{j=1}^N c_j x_j + c_0$ , raising it to powers of 2 doesn't introduce anything new:

$(R_v[i])^2 = \sum_{j=1}^N c_j x_j^2 + c_0$ $(R_v[i])^4 = \sum_{j=1}^N c_j x_j^4 + c_0$

I noticed no cross-terms (like $x_i x_j$ for $i \neq j$ ) ever show up during this exponentiation — the Frobenius structure over $\mathbb{F}*2$ keeps everything additive. And since $x_i^4$ and $x_i^2$ both collapse back to $x_i$ on binary inputs, every public key polynomial component $P_k(x_1, \dots, x*{137})$ — despite looking like a degree-4 multivariate polynomial on paper — actually simplifies to a plain affine linear equation:

$P_k(\mathbf{x}) = \sum_{j=1}^{137} M_{k,j} x_j + c_k \pmod 2$

where:

$M_{k,j} =$ (count of $x_j^4$ in $P_k$ ) $+$ (count of $x_j^2$ in $P_k$ ) $\pmod 2$ .
$c_k = 1$ if the constant term 1 is present in $P_k$ , else $0$ .

That meant the "hard" multivariate public key evaluation was really just:

$\text{encrypted}*\text*{key} *= M \cdot \mathbf*{x} *+ c \pmod 2 \implies M \cdot \mathbf*{x} *= \text*{encrypted}\text{key} \oplus c \pmod 2$

A linear system in disguise. Once I saw that, I knew this was going to come down to straightforward linear algebra over $\mathbb{F}_2$ .

Resolving the Singular Matrix & Linear System

Here's how I worked through the rest of it:

System Construction: I built the $137 \times 137$ matrix $M$ and vector $b = \text{encrypted}_\text{key} \oplus c$ over $\mathbb{F}_2$ , parsing the public key polynomials directly out of output.txt.
Matrix Rank: Running Gaussian elimination to Reduced Row Echelon Form (RREF), I found $\text{rank}(M) = 135$ — not full rank. That rank deficiency was exactly what I expected, since $T_A$ and $S_A$ had been chosen singular from the start.
Kernel & Enumeration: A rank of 135 over a 137-dimensional space leaves a 2-dimensional nullspace, which meant only $2^2 = 4$ candidate solutions to check.
Candidate Check: I enumerated all 4 candidates and checked each against the AES-encrypted flag until I found the unique 137-bit string $\mathbf{x}$ corresponding to KEY.

Complete Solver Script

python

import ast
import hashlib
import itertools
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

def solve():
    with open('crypto_ashen_field/output.txt') as f:
        lines = [line.strip() for line in f if line.strip()]

    pk_str = lines[0][1:-1]
    polys = pk_str.split(', ')
    enc_key = ast.literal_eval(lines[1])
    enc_flag = bytes.fromhex(lines[2])

    N = 137
    M = [[0]*N for _ in range(N)]
    c = [0]*N

    for k, p in enumerate(polys):
        terms = p.split(' + ')
        for t in terms:
            if t == '1':
                c[k] ^= 1
            else:
                var = t.split('^')[0]
                idx = int(var[1:]) - 1
                M[k][idx] ^= 1

    b = [enc_key[k] ^ c[k] for k in range(N)]

    # Gaussian elimination to RREF over GF(2)
    aug = [M[i] + [b[i]] for i in range(N)]

    pivot_cols = []
    pivot_row_map = {}
    row = 0
    for col in range(N):
        pivot = None
        for r in range(row, N):
            if aug[r][col] == 1:
                pivot = r
                break
        if pivot is None:
            continue
        
        aug[row], aug[pivot] = aug[pivot], aug[row]
        pivot_cols.append(col)
        pivot_row_map[col] = row
        
        for r in range(N):
            if r != row and aug[r][col] == 1:
                for c_idx in range(col, N + 1):
                    aug[r][c_idx] ^= aug[row][c_idx]
        row += 1

    free_cols = [col for col in range(N) if col not in pivot_row_map]

    # Test all 2^len(free_cols) candidates
    for free_vals in itertools.product([0, 1], repeat=len(free_cols)):
        x = [0]*N
        for col, val in zip(free_cols, free_vals):
            x[col] = val
        
        for col in pivot_cols:
            r = pivot_row_map[col]
            val = aug[r][N]
            for f in free_cols:
                val ^= (aug[r][f] & x[f])
            x[col] = val

        KEY = sum(x[i] * (1 << i) for i in range(N))
        if KEY.bit_length() != N:
            continue

        AES_KEY = hashlib.sha256(str(KEY).encode()).digest()
        cipher = AES.new(AES_KEY, AES.MODE_ECB)
        try:
            flag = unpad(cipher.decrypt(enc_flag), 16)
            print(f"[+] Flag found: {flag.decode()}")
            return flag.decode()
        except Exception:
            continue

if __name__ == '__main__':
    solve()

Execution

Running my solver gave me exactly what I was after:

text

[+] Flag found: HTB{{REDACTED}}

What looked like an intimidating quartic multivariate cryptosystem turned out to be nothing more than linear algebra wearing a costume — the deliberately singular matrices were the tell the whole way through.