0CTF Quals 2019: "zer0mi" writeup

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 (xi,yi), which is of course possible using the public key by encrypting random plaintexts. One then looks for linearization equations of the form aijxiyj+bixi+cixi+d=0 that all those pairs satisfy; this consists of solving a big linear system with (N+1)2 unknowns aij,bi,cj,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 y1,,yN, and solve for the plaintext x1,,xN.

The task authors programmed their own (Python) classes for all the required algebraic objects, adding up to 10π 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 aij,bi,cj,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 x1,,xN 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×(N+1)2 matrix used to compute the linearization equations. (It is definitely a good idea to dump the coefficients aij,bi,cj,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_?}
$ 

@hxp