Write-up McEliece@Hack.lu 2024

The challenge was as follows:

Robert McEliece, our lord and savior of the gym, reveals his flag only after you lift some weights. Given the public-key and ciphertext, can you find a correct error vector?

nc mceliece.flu.xxx 5555

Now, while we know efficient such codes, decoding for a random G is NP-hard. McEliece uses this to produce a public-key encryption scheme: For the private key, we generate an efficient generator and code pair (G,C). For the public key, we however transform the generator G to a random looking generator G'.

For encryption, we now multiply the public key with a message vector m and add some small error to it (which is now hard to decode without the secret key, because G’ is random-looking). However, if we have the secret key, we can use the “inverted” transform on the ciphertext c and now use the original C to decode c, recovering m.

Having this information about McEliece, we can now look at the challenge code:

pk = json.loads(Path("data/pubkey").read_text())

H, w = pk["P"], pk["w"]
n = len(H[0])
k = n-len(H)

syndrome = json.loads(Path("data/secret.txt.enc").read_text())
MCELIECE_PARAMS = (3488, 64, 12)

flag = os.getenv("FLAG", "flag{testflag}")

The first thing the challenge does is read a public key and an encrypted message. Here, H is the generator matrix and w is a parameter for a hemming weight. Next, it wants us to provide some kind of error:

def ask_weights():
    print("Enter the error:")
    try:
        datafile = json.loads(input())
    except EOFError:
        return


    # check length 
    if len(datafile) != MCELIECE_PARAMS[0]:
        print("wrong len")
        return
        # check if binary
    if not all([0 <= d <= 1 for d in datafile]):
        print("not binary")
        return

    # check weight:
    weight = sum(datafile)
    if weight < w:
        print("wrong weight %d" % weight)
        return

    # compute syndrome
    check_syndrome = None
    try:
        data = vector(GF(2), datafile)
        check_syndrome = mceliece.encrypt([matrix(GF(2), pk["P"]), pk["w"]], data)
    except e as Exception:
        print(e)
        return
    
    # check syndrome
    for i in range(n-k):
        if syndrome[i] != check_syndrome[i]:
            print("wrong syndrome")
            return
    print(flag)
    exit(0)

So we should provide some “error” datafile, which has to be a list of binary values of length 3488. Futher, the hamming weight of the “error” should be at least w (which is 64).

Now, the program calls mceliece.encrypt on the public key and our “error” and checks whether the result is identical to the encrypted message.

This seems strange for multiple reasons. First, we encrypt something without giving the message to encrypt, just some error. The error has be larger than w, while for McEliece, we want to have a small error. And finally, computing a message which encrypts to the same ciphertext should be hard, if McEliece is not broken! Therefore, let’s take a look at the provided McEliece encryption function:

def encrypt(pk, m):
    """
    :param pk: public key = parity check matrix
    :param m: the error to 
    """
    P, w = pk
    s = P * m
    return s

That something is wrong here is maybe already clear from the length of the function. Indeed, the only thing happening here is that we multiply the public key P with the “error” m and return the result. So m is actually the message and we just don’t add any error?

But McEliece without error term is just a linear equation and these are easy to invert! So all we have to do is for a given encryption s, find an m such that P*m=s. Using sage, this is quite easy to do:

P = matrix(GF(2), H)
s = vector(GF(2), syndrome)

m = P.solve_right(s)

Helpfully, m has also a big enough hamming weight, so it is a valid input and we get the flag:

flag{H4v3_y0U_3v3N_l0Ck3d_1n_th3_c0rr3CT_w31Ght}

Full solution script:

#!/usr/bin/env python3

import json
from pathlib import Path
import socket
import telnetlib
from sage.all import *

pk = json.loads(Path("data/pubkey").read_text())

H, w = pk["P"], pk["w"]
n = len(H[0])
k = n-len(H)

syndrome = json.loads(Path("data/secret.txt.enc").read_text())
MCELIECE_PARAMS = (3488, 64, 12)

P = matrix(GF(2), H)
s = vector(GF(2), syndrome)

m = P.solve_right(s)

sol = json.dumps([int(i) for i in m])

t = telnetlib.Telnet("mceliece.flu.xxx", 5555)
print("{}".format(t.read_until(b'\n')))
print("{}".format(t.read_until(b'\n')))
print("{}".format(t.read_until(b'\n')))

t.write(sol.encode('ascii') + b'\n')
print("{}".format(t.read_until(b'\n')))