D3HFERP — d3c2026

Description

We obtained the public key of a post-quantum encryption prototype, together with several ciphertext blocks. Analyze the multivariate public-key encryption scheme and recover the encrypted flag.

The archive provides the Sage source, a public key, and seven ciphertext blocks. The goal is to invert the public multivariate map and reconstruct the length-prefixed plaintext.

Analysis

Public map

The source sets the field and dimensions to

q, d, o, r, s = 3, 20, 11, 11, 11
n, m = d + o, d + o + r + s

Thus a plaintext block is a vector in GF(3)^31, while a ciphertext block contains 53 field elements. Before mixing, the central map consists of:

• 20 HFE-derived coordinate polynomials;
• 22 oil-free UOV-style polynomials;
• 11 unrestricted random quadratic polynomials.

Invertible input and output transformations hide this decomposition. A public coordinate has the form

[ P_k(x)=x^T A_k x+L_kx+C_k. ]

Because the saved matrices are symmetric and only their upper triangles are serialized, an off-diagonal entry contributes 2*A[i][j]*x_i*x_j. This factor of two is important over GF(3).

Why direct inversion works

For ciphertext coordinate y_k, inversion requires solving

[ P_k(x)-y_k=0,\qquad 0\le k<53. ]

This is an overdetermined system of 53 quadratic equations in only 31 variables. The variables must also be restricted to GF(3), so append one field equation per variable:

[ x_i^3-x_i=x_i^3+2x_i=0. ]

Each block therefore becomes an 84-equation polynomial system. msolve's F4 implementation reduces every instance to a degree-one ideal with a unique solution. No recovery of the hidden HFE or UOV decomposition is needed.

A potentially related UOV common-kernel attack was not directly applicable. Output mixing combines all central coordinates, and the 11 unrestricted random quadratics destroy the full public common kernel that such an attack would need.

Solution

1. Parse and evaluate the public key

The evaluator must reproduce Sage's symmetric quadratic form exactly:

def enc(x, polys):
    out = []
    for A, L, C in polys:
        value = C
        for i in range(len(x)):
            value += A[i][i] * x[i] * x[i] + L[i] * x[i]
            for j in range(i + 1, len(x)):
                value += 2 * A[i][j] * x[i] * x[j]
        out.append(value % 3)
    return out

This evaluator is also an independent check on every root returned by the algebra system.

2. Generate an msolve system for each block

The following is the essential equation generator. load() parses pubkey.txt and ciphertext.txt into the representation used above.

#!/usr/bin/env python3
from pathlib import Path
import sys
from solve import load

block = int(sys.argv[1])
n, m, polys, targets = load()
target = targets[block]
equations = []

for (A, L, C), y in zip(polys, target):
    terms = []
    for i in range(n):
        if A[i][i] % 3:
            c = A[i][i] % 3
            terms.append((c, f"x{i}^2"))
        if L[i] % 3:
            terms.append((L[i] % 3, f"x{i}"))
        for j in range(i + 1, n):
            c = (2 * A[i][j]) % 3
            if c:
                terms.append((c, f"x{i}*x{j}"))
    if (C - y) % 3:
        terms.append(((C - y) % 3, "1"))
    equations.append("+".join(
        ("" if c == 1 else f"{c}*") + mon for c, mon in terms
    ))

equations += [f"x{i}^3+2*x{i}" for i in range(n)]

with Path(f"block{block}.ms").open("w") as f:
    f.write(",".join(f"x{i}" for i in range(n)) + "\n3\n")
    f.write(",\n".join(equations) + "\n")

Generate and solve all systems:

for i in 0 1 2 3 4 5 6; do
    python3 generate_msolve.py "$i"
    msolve -f "block${i}.ms" -o "block${i}.out" -t 8 -v 2
done

Parallelizing independent blocks is safe if sufficient memory is available. For block 0, the Gröbner-basis phase took 88.66 seconds with eight threads. Its largest F4 matrix was 24947 x 47404, and the final reduced basis contained 31 linear polynomials.

3. Parse msolve's rational parametrization

Each output reports characteristic 3, 31 variables, and ideal degree 1. In msolve's parametrization, the univariate equation determines the final variable t. The other coordinates are represented by

[ d(t)x_i+n_i(t)=0, ]

not by d(t)x_i-n_i(t)=0. Consequently, with denominator one, each coordinate is the negated numerator modulo 3. Missing degree (-1) represents the zero polynomial.

import ast

def poly_constant(poly):
    degree, coeffs = poly
    if degree == -1:
        return 0
    assert degree == 0 and len(coeffs) == 1
    return coeffs[0] % 3

def unique_root(path):
    data = ast.literal_eval(path.read_text().rstrip().rstrip(":"))
    assert data[0] == 0
    characteristic, nvars, degree = data[1][:3]
    assert (characteristic, nvars, degree) == (3, 31, 1)

    parameterization = data[1][5]
    assert parameterization[0] == 1
    univariate, denominator, coordinates = parameterization[1]
    assert univariate[0] == 1 and denominator == [0, [1]]

    c0, c1 = univariate[1]
    t = (-c0 * pow(c1, -1, 3)) % 3
    values = [(-poly_constant(item[0])) % 3 for item in coordinates]
    values.append(t)
    assert len(values) == nvars
    return values

4. Verify and decode

Never trust an external solver result without checking it against the original public map. After verification, concatenate the seven blocks in their original order. The source treats these 217 trits as little-endian base-3 digits, converts the resulting integer to little-endian bytes, and interprets the first two bytes as the payload length.

from pathlib import Path
from solve import enc, load

_, _, polys, targets = load()
blocks = []

for i, target in enumerate(targets):
    block = unique_root(Path(f"block{i}.out"))
    assert enc(block, polys) == target
    blocks.append(block)

trits = [digit for block in blocks for digit in block]
value = sum(digit * 3**i for i, digit in enumerate(trits))
raw = value.to_bytes((value.bit_length() + 7) // 8, "little")
length = int.from_bytes(raw[:2], "little")
assert length == 38
print(raw[2:2 + length].decode())

All seven roots pass re-encryption. Decoding the verified trits yields the requested flag.

Failed and Deprioritized Approaches

• A direct CP-SAT model remained UNKNOWN after 60 seconds.
• Singular did not finish the first block within 300 seconds.
• Conventional known-prefix probes did not reproduce the first ciphertext block.
• Structural MinRank or hidden HFE/UOV recovery was unnecessary once direct F4 solving proved practical.