heist

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: kernel_intersection, signature_forgery, uov_attack

Summary

Walkthrough of the CUSTOM Crypto heist. Task: forge a signature for a weakened Unbalanced Oil-and-Vinegar (UOV) multivariate quadratic scheme. Solution: recover the Oil subspace by finding the common kernel of polar form matrices of the pub

Description

The challenge implements a Multivariate Quadratic (MQ) signature scheme. We are given a public key consisting of $m=42$ quadratic polynomials in $n=123$ variables over $GF(256)$. The goal is to forge a signature for an arbitrary message.

Analysis

The scheme is a variant of the Unbalanced Oil and Vinegar (UOV) signature scheme. The public key $P$ is a composition of a central map $F$ and a secret linear transformation $T$: $P = F \circ T$.

Vulnerability Identification

By inspecting the generate.sage script (provided in the challenge), we can see how the central map $F$ is constructed:

 python read-only • copy allowed Copy
ks = [tuple((i,j).count(u) for u in range(n)) for i in range(n) for j in range(i,n-m)]
ks += [tuple(i == u for u in range(n)) for i in range(n)]  + [(0,)*n]

Here $n-m = 123-42 = 81$. The variables $x_0, \dots, x_{80}$ are "Vinegar" variables, and $x_{81}, \dots, x_{122}$ are "Oil" variables. The code shows that quadratic terms $x_i x_j$ are only included if $j < 81$. Since $i \le j$ in the loop, this means both $i$ and $j$ must be Vinegar variables. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

In a standard UOV scheme, Oil variables do not have quadratic terms among themselves ($O \times O$), but they can have cross-terms with Vinegar variables ($V \times O$). In this challenge, the central map $F$ is significantly weakened:

1. No Oil-Oil terms: Standard for UOV.
2. No Vinegar-Oil terms: This is the critical weakness. Oil variables only appear linearly in $F$.

Exploitation Strategy

The polar form of a polynomial $f$ is defined as $G(x, y) = f(x+y) - f(x) - f(y) + f(0)$. It is a bilinear form that can be represented by a matrix $M$. In characteristic 2, $M_{ij}$ is the coefficient of $x_i x_j$ for $i \neq j$, and $M_{ii} = 0$. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Because the Oil variables only appear linearly in $F$, the Oil subspace $O$ is contained in the kernel of the polar form matrices $M_i$ of the central polynomials $F_i$. Specifically, for any $o \in O$ and any $x$, $G_{F_i}(x, o) = 0$.

Since the public polynomials $P_i$ are related to $F_i$ by the linear transformation $T$ ($P = F \circ T$), the Oil subspace in the public basis $O' = T^{-1}(O)$ is the common kernel of the polar form matrices of the public polynomials $P_i$.

Solution

1. Recover the Oil Subspace: Construct the polar form matrix $M_k$ for each public polynomial $P_k$. Find the intersection of their kernels (the common kernel). This yields a 42-dimensional subspace, which is the transformed Oil subspace $O'$. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

2. Forge the Signature: To sign a message $m$:

   • Hash the message to a target vector $h \in GF(256)^{42}$.
   • Pick a random 'Vinegar' vector $v \in GF(256)^{123}$.
   • Since $P$ is linear on $O'$ and there are no cross-terms between Vinegar and Oil variables in the central map, we have: $P(v + o) = P(v) + (P(o) - P(0)) = h$
   • This is a linear system $L(o) = h - P(v)$ where $L(o) = P(o) - P(0)$ is the linear part of $P$.
   • Solve for the coefficients of $o$ in the basis of $O'$.
   • The resulting vector $x = v + o$ is the signature. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Implementation (Sage)

 python read-only • copy allowed Copy
#!/usr/bin/env sage
from public import K, R, P
from Crypto.Hash import SHAKE256

n = R.ngens()
m = len(P)

def get_polar_matrix(f):
    M = matrix(K, n, n)
    d = f.dict()
    for mon, coeff in d.items():
        if sum(mon) == 2:
            vars = [i for i, exp in enumerate(mon) if exp > 0]
            if len(vars) == 2:
                i, j = vars
                M[i, j] = coeff
                M[j, i] = coeff
    return M

# 1. Recover the Oil subspace
print("[*] Constructing polar form matrices...")
Ms = [get_polar_matrix(f) for f in P]
big_M = stack([M for M in Ms])
print("[*] Finding common kernel...")
O_space = big_M.right_kernel()
basis = O_space.basis()
print(f"[*] Found Oil subspace of dimension {len(basis)}")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def sign(msg_bytes):
    # Hash message to target vector
    ctr = b'\x00\x00\x00\x00'
    h_bytes = SHAKE256.new(ctr + msg_bytes).read(m)
    h = vector(K, [K.from_integer(b) for b in h_bytes])
    
    # Pick random vinegar part
    v = vector(K, [K.random_element() for _ in range(n)])
    
    # 2. Solve the linear system for the Oil part
    target = h - vector(K, [f(*v) for f in P])
    A = matrix(K, m, len(basis))
    for i in range(len(basis)):
        # Linear part L(o_i) = P(v + o_i) - P(v)
        val = vector(K, [f(*(v + basis[i])) for f in P]) - vector(K, [f(*v) for f in P])
        for k in range(m):
            A[k, i] = val[k]
            
    c = A.solve_right(target)
    o = sum(c[i] * basis[i] for i in range(len(basis)))
    x = v + o
    
    return ctr + bytes(int(val.to_integer()) for val in x)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

msg = "pls gief fl0g | ..." # Actual message from the challenge
sig = sign(msg.encode())
print(f"[*] Signature: {sig.hex()}")

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

Key Takeaways / Lessons

• Mastering kernel_intersection, signature_forgery, uov_attack was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2025-12-28 • CUSTOM • heist • Difficulty: Medium