The Ashen Field

Platform: CACTF2026 | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-07-27 | Status: Solved Techniques: hfe_linearization_attack, frobenius_power_collapse, boolean_variable_reduction, gaussian_elimination_gf2, underdetermined_system_enumeration, sha256_key_derivation

Summary

Task: HFE multivariate public-key cryptosystem over GF(2) with N=137 variables; recover a KEY that seeds an AES-ECB flag key. Solution: the central map F^4+F^2+1 is a linearized polynomial and boolean variables (x^2=x) collapse the whole public key to an affine GF(2) map, so Gaussian elimination recovers KEY and decrypts the flag.

The Ashen Field — CACTF2026

Description

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.

We are given a SageMath implementation of an HFE (Hidden Field Equations) multivariate public-key cryptosystem over GF(2) with N = 137 variables, plus an output.txt containing: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

1. The public key PK — 137 multivariate polynomials over GF(2).
2. encrypted_key — the encryption of a 137-bit secret KEY under PK (a 137-bit vector).
3. enc_flag — the flag encrypted with AES-ECB, whose key is sha256(str(KEY)).

Goal: recover KEY, derive the AES key, and decrypt the flag.

Analysis

How the scheme works

keygen(n) builds a classic HFE public key:

• Polynomial ring R = GF(2)[x1..x137], quotiented by the ideal (x^2 - x) for every generator — i.e. boolean / idempotent variables where x_i^2 = x_i.
• A secret affine input transform S = (S_A, S_B): Rv = S_A * x + S_B.
• An extension field GF(2^137) via an irreducible polynomial g of degree 137. The affine-mixed variable vector is embedded as a field element F.
• Central map: F = Q(F^(2*q) + F^q + 1) with q = 2, i.e. F = F^4 + F^2 + 1 over GF(2^137).
• A secret affine output transform T = (T_A, T_B): PK = T_A * PK + T_B. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Encryption embeds the message bits (LSB-first, zero-padded to length N) and evaluates PK(msg).

The vulnerability: the central map is linear

The central map is F^4 + F^2 + 1. In characteristic 2:

• F^4 = F^(2^2), F^2 = F^(2^1), 1 = F^(2^0) are all Frobenius powers F^(2^k).
• A polynomial that is a sum of Frobenius powers is a linearized (additive) polynomial: L(a + b) = L(a) + L(b) over GF(2). Adding the constant 1 makes it affine.

So the "hidden" central map that is supposed to be a hard quadratic system is in fact an affine map over GF(2^137), and hence over GF(2)^137. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

There is a second, even simpler reason the system collapses. Because every variable is boolean (x_i^2 = x_i from the quotient ideal), any monomial x_i^4 or x_i^2 reduces to x_i. There are no genuine cross-terms surviving — every published polynomial is a plain XOR of single variables plus an optional constant 1. Wrapping the secret affine S and T around an affine central map yields an affine map, so:

<!-- attack references the classic HFE linearization / Groebner-basis weakness -->

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

PK(m) = M * m + C

for a single 137 x 137 matrix M and constant vector C over GF(2). This is the well-known linearization weakness of HFE with a linearized central map — the algebraic (Groebner-basis) style attack on such schemes. The flag text also nods to this class of published cryptanalytic results.

Solution

1. Parse the public key into an affine map

Each of the 137 polynomials is a flat GF(2) sum of terms x_i, x_i^2, x_i^4, or 1. Reduce every x_i^k -> x_i (boolean) and XOR-accumulate coefficient parity per variable to build row i of M; track the constant 1 term as C_i. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

2. Set up and solve the linear system

The ciphertext of KEY satisfies M * m + C = encrypted_key, so we solve

M * m = encrypted_key XOR C   (over GF(2))

via Gaussian elimination on bitmask-packed augmented rows.

3. Handle the underdetermined system

The rank of M was only 135 (free columns at indices 133 and 136), giving 2^2 = 4 candidate solutions. Enumerate all four assignments of the free variables and back-substitute.

4. Reconstruct KEY and pick the valid candidate

The message embedding for KEY is KEY.bits() (LSB-first, no zero padding because the generator enforces KEY.nbits() == 137). So KEY = sum(sol[j] << j). The valid candidate is the one whose KEY has exactly 137 bits (top bit set) — the generation constraint. We also assert PK(sol) == encrypted_key for the chosen solution. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

5. Derive AES key and decrypt

AES_KEY = sha256(str(KEY).encode()).digest(), then AES-ECB decrypt enc_flag and unpad.

Full working solver: /Users/sergeyskorobogatov/Projects/Agents/CTF/tasks/CACTF2026/the_ashen_field/solve2.py

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import re, hashlib, itertools
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

N = 137

with open('extracted/crypto_ashen_field/output.txt') as f:
    lines = f.read().split('\n')

pk_line = lines[0].strip()[1:-1]           # strip surrounding ( )
polys = [p.strip() for p in pk_line.split(',')]
assert len(polys) == N
enc_key = eval(lines[1].strip())           # 137-bit list
enc_flag = bytes.fromhex(lines[2].strip())
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# --- Parse each polynomial into a GF(2) affine row: x_i^k -> x_i, XOR parity ---
mono_re = re.compile(r'x(\d+)(?:\^\d+)?')
M = []; C = []
for p in polys:
    row = [0]*N; const = 0
    for t in p.split('+'):
        t = t.strip()
        if not t: continue
        m = mono_re.fullmatch(t)
        if m:
            row[int(m.group(1))-1] ^= 1     # boolean collapse + parity
        elif t == '1':
            const ^= 1
        else:
            raise ValueError(t)
    M.append(row); C.append(const)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# RHS = enc_key XOR C
b = [(enc_key[i] ^ C[i]) for i in range(N)]

# --- Gaussian elimination over GF(2) on bitmask-packed augmented rows ---
rows = []
for i in range(N):
    val = 0
    for j in range(N):
        if M[i][j]: val |= (1 << j)
    val |= (b[i] << N)
    rows.append(val)

pivot_col = [-1]*N
r = 0
for col in range(N):
    piv = -1
    for rr in range(r, N):
        if (rows[rr] >> col) & 1:
            piv = rr; break
    if piv == -1: continue
    rows[r], rows[piv] = rows[piv], rows[r]
    for rr in range(N):
        if rr != r and ((rows[rr] >> col) & 1):
            rows[rr] ^= rows[r]
    pivot_col[r] = col
    r += 1
rank = r
pivot_cols = set(pivot_col[:rank])
free_cols = [c for c in range(N) if c not in pivot_cols]
print("rank", rank, "free cols", free_cols)   # rank 135, free cols [133, 136]
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def apply(m):
    out = []
    for i in range(N):
        v = C[i]
        for j in range(N):
            if M[i][j] and m[j]: v ^= 1
        out.append(v)
    return out

# --- Enumerate the 2^(#free) candidate solutions ---
for bits in itertools.product([0, 1], repeat=len(free_cols)):
    sol = [0]*N
    for c, val in zip(free_cols, bits):
        sol[c] = val
    for rr in range(rank):
        col = pivot_col[rr]
        acc = (rows[rr] >> N) & 1
        for c in free_cols:
            if (rows[rr] >> c) & 1:
                acc ^= sol[c]
        sol[col] = acc
    assert apply(sol) == enc_key            # verify against ciphertext
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    KEY = 0
    for j in range(N):
        KEY |= (sol[j] << j)                 # LSB-first, no padding
    AES_KEY = hashlib.sha256(str(KEY).encode()).digest()
    dec = AES.new(AES_KEY, AES.MODE_ECB).decrypt(enc_flag)
    print("free", bits, "KEYnbits", KEY.bit_length(), "dec head", dec[:16])
    if b'HTB{' in dec:
        print("FLAG:", unpad(dec, 16))       # valid candidate: KEY.nbits()==137

The candidate with free-vars (0, 1) produced a KEY of exactly 137 bits and decrypted to the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍