Codegate 2024 Quals - LACUCARA_VM (Reverse) - black-box solution

lacucara.py

'''
Turns out that the output.txt contains images of the 8-byte chunks of the flag under a fixed affine map.
We can interpolate the map from a bunch of samples and then simply invert the real flag's output.
'''
from sage.all import *
import re
from binteger import Bin  # pip install binteger

# need to use script log, since the program requires a console
'''
script -aq logRANDOM.txt <<EOF
bash -c 'for i in {1..300}; do head -c 64 /dev/urandom >flag.txt; echo -n "FLAG: 0x"; xxd -ps flag.txt | tr -d "\n"; wine encryptor.exe; done'
EOF
'''
s = open("logRANDOM.txt").read()
words = re.findall(r"0x(\w+)\b", s)
blocks = [[int(w, 16) for w in words[i:i+33]] for i in range(0, len(words), 33)]

rows = []
tab = {}
for block in blocks:
    assert len(block) == 33, len(blocks)
    inp, *block = block
    inp = Bin(inp, 8 * 64).bytes
    assert len(inp) == 64
    a, b, c, d = block[:4]
    # same encryption for all chunks
    # 1 for affine constant
    rows.append(Bin.concat(inp[:8], Bin.concat(a, b, c, d, n=32), 1))

mat = matrix(GF(2), rows)
print("rank", mat.rank(), mat.ncols())

rk = mat.right_kernel().matrix()
for row in rk:
    print("".join(map(str, row[:64])), end=" ")
    print("".join(map(str, row[64:])))

assert rk[:64,:64] == 1  # identity matrix
dec = rk[:, 64:]

s = open("output.txt").read()
words = re.findall(r"0x(\w+)\b", s)

flag = b""
for i in range(0, len(words), 4):
    print(i, words[i:i+4])
    a, b, c, d = [int(w, 16) for w in words[i:i+4]]
    ct = Bin.concat(Bin.concat(a, b, c, d, n=32), 1).vector
    pt = dec * ct
    print(Bin(pt).bytes)
    flag += Bin(pt).bytes
print(flag)

# b'codegate2024{B45IC_i5_n07_d34d_4nd_n3v3r_wi11_b3_2024_MQCJAb4Wr}'