This challenge asked us to break an instance of the Matsumoto–Imai multivariate public-key encryption scheme. Clearly the first thing to look at is a linearization attack: The first step is generating about $(N+1)^2$ plaintext-ciphertext pairs $(x_i,y_i)$, which is of course possible using the public key by encrypting random plaintexts. One then looks for linearization equations of the form \[ a_{ij}x_iy_j + b_ix_i + c_ix_i + d = 0 \] that all those pairs satisfy; this consists of solving a big linear system with $(N+1)^2$ unknowns $a_{ij},b_i,c_j,d$. The construction of the nonlinear maps used in the MI scheme ensures that there exist $N$ such equations in almost all cases. Finally, one can take those linearization equations, plug in a specific ciphertext $y_1,\dots,y_N$, and solve for the plaintext $x_1,\dots,x_N$.

The task authors programmed their own (Python) classes for all the required algebraic objects, adding up to $\lfloor 10\pi\rfloor$ lines of challenge source code, so the first step is a little bit of reading code and importing their representations into sage:

#!/usr/bin/env sage
import re

F.<z> = GF(256, modulus = sum(x**i for i in [0,2,3,4,8]))

N = 63
R = PolynomialRing(F, N, list(map('x{}'.format, range(N))))
Xs = list(R.gens())

pubkey, cipher = open('output').read().strip().split('\n')
pubkey = eval(re.sub(r'x([0-9]+)', r'Xs[\1]', pubkey.replace('z8', 'z').replace('^','**')))
cipher = [F.fetch_int(x) for x in map(ord, cipher.decode('hex'))]
sys.stderr.write('done loading data.\n')

After this, we simply follow the steps outlined above to solve for the coefficients $a_{ij},b_i,c_j,d$:

def get_pair():
    a = (F**N).random_element()
    return a, [f.subs({x:v for x,v in zip(Xs,a)}) for f in pubkey]

# equations: aij xi yj + bi xi + cj yj + d = 0
# unknowns: first aij (N^2), then bi (N), then cj (N), then d (1). total (N+1)^2.
# aij are flattened as a11, a12, a13, ..., a1n, a21, a22, ..., an1, ..., ann.
o_as, o_bs, o_cs, o_d = 0, N^2, N^2+N, N^2+2*N
mat = []
while len(mat) < (N+1)**2:
    xs, ys = get_pair()
    row = vector(F, (N+1)**2)
    for i,x in enumerate(xs):
        for j,y in enumerate(ys):
            row[o_as + N*i+j] = x*y
            row[o_bs + i] = x
            row[o_cs + j] = y
            row[o_d] = 1
    mat.append(row)
    sys.stderr.write('\r{:4}/{:4}'.format(len(mat), (N+1)**2))
sys.stderr.write('\rdone building matrix.\n')

ker = matrix(mat).right_kernel()
print(ker.dimension())
for v in ker.basis(): print(v)
sys.stderr.write('done computing kernel.\n')

At this point, we can see whether there are enough linearization equations: Indeed, the kernel turned out to have dimension precisely $N=63$, which is exactly what the theory predicts (unless we’re in a rare exceptional case)!

We can now simply plug in our challenge ciphertext into those equations and solve for the plaintext $x_1,\dots,x_N$ to obtain the flag:

# equations: aij xi yj + bi xi + cj yj + d = 0
# unknowns: x1 .. xn
mat, vec = [], []
for v in ker.basis():
    row = vector(F, N+1)
    for i in range(N):
        for j,y in enumerate(cipher):
            row[i] += v[o_as + N*i+j] * y
        row[i] += v[o_bs + i]
    rhs = -v[o_d]
    for j,y in enumerate(cipher):
        rhs -= v[o_cs + j] * y
    mat.append(row)
    vec.append(rhs)
mat, vec = matrix(mat), vector(vec)
sys.stderr.write('done building second matrix.\n')

sol = mat.solve_right(vec)
seen = set()
for v in mat.right_kernel():
    s = ''.join(chr(x.integer_representation()) for x in sol + v)
    for flag in re.findall('flag{[^}]+}', s):
        if flag not in seen: print(flag)
        seen.add(flag)

Running the whole script takes something like half an hour, the bulk of which is generating the $(N+1)^2\times (N+1)^2$ matrix used to compute the linearization equations. (It is definitely a good idea to dump the coefficients $a_{ij},b_i,c_j,d$ into a file once they’re known, in case the script crashes after that part…) Fortunately, it printed the flag on the almost first attempt:

$ ./pwn.sage
done loading data.
done building matrix.
63
(1, 0, 0, 0, [...], 0, 0, z^6 + z^5 + z^4 + z^3 + z^2 + 1, 0, z^7 + z^5 + z^4 + z^3 + 1, z^7 + z^6 + z^4, z^7 + z^4 + z + 1, z^6 + z^5 + z^4 + z^3 + z^2 + z + 1, z^3 + 1, z^3 + z + 1, z^7 + z^5 + z^4 + z^3 + 1, z^6 + z^5 + z^2, z^7 + z^6 + z^3 + z^2 + z + 1, z^6 + z^4 + z^3 + z^2 + z, z^6 + z^3 + z^2 + 1, [...], z^7 + z^4, 0, 0, 0, [...], 0)
(0, 1, 0, 0, [...], 0, 0, z^7 + z^6 + z^3 + z + 1, 0, z^7 + z^5 + z^4 + 1, z^7 + z^6 + z^5 + z^3 + z^2 + z, z^5 + z^2 + z + 1, z^7 + z^5 + z^4 + z^2 + 1, z^7 + z^5 + z + 1, z^7 + z^3 + z^2 + z, z^7 + z^6 + z^4 + z^2 + z, z^7 + 1, z^5 + z^4 + z^3 + 1, z^6 + z^5 + z^4 + z, z^7 + z^5, [...], z^7 + z^6 + z^5 + z^3 + z^2 + z, 0, 0, 0, [...], 0)
[...]
(0, 0, 0, 0, [...], 0, 1, z^3 + z^2 + z + 1, z^7 + z^4 + z^2 + 1, z^4 + z^3 + z^2 + 1, z^7 + z^3 + 1, z^4 + z^3 + z^2 + z + 1, 1, z^7 + z^5 + z^2 + z, z^6 + z^4 + z^3 + z^2 + 1, z^6 + z^5 + z^3 + z^2, z^4 + z^2 + z, z^7 + z^4 + z^3, z^6 + 1, z^7 + z^6 + z, z^7 + z^6 + z^5 + z^4 + z^3 + z^2 + z, z^4 + z^2, [...], z^5 + z + 1, 0, 0, 0, [...], 0)
done computing kernel.
done building second matrix.
flag{E$t-ce_qu3_Le_c!3l_m0uRra,_Mourr4_?}
$