exploit.sage

from os import urandom
from random import choices, shuffle
from itertools import product
from tqdm import tqdm

ALPHABET = '0123456789abcdef'
N = len(ALPHABET)

plaintext = b'The secret message is:'.hex()
ciphertext = '85677bc8302bb20f3be728f99be0002ee88bc8fdc045b80e1dd22bc8fcc0034dd809e8f77023fbc83cd02ec8fbb11cc02cdbb62837677bc8f2277eeaaaabb1188bc998087bef3bcf40683cd02eef48f44aaee805b8045453a546815639e6592c173e4994e044a9084ea4000049e1e7e9873fc90ab9e1d4437fc9836aa80423cc2198882a'

class Cipher:
    def __init__(self, key):
        self.key = key
        self.n = len(self.key)
        self.s = 7

    def add(self, num1, num2):
        res = 0
        for i in range(4):
            res += (((num1 & 1) + (num2 & 1)) % 2) << i
            num1 >>= 1
            num2 >>= 1
        return res

    def encrypt(self, msg):
        key = self.key
        s = self.s
        ciphertext = ''
        for m_i in msg:
            c_i = key[self.add(key.index(m_i), s)]
            ciphertext += c_i
            s = key.index(m_i)
        return ciphertext

    def decrypt(self, ciphertext):
        key = self.key
        s = self.s
        plaintext = ''
        for c_i in ciphertext:
            m_i = key[self.add(key.index(c_i), s)]
            plaintext += m_i
            s = key.index(m_i)
        return plaintext

#### SOLUTION

def num_to_gf16_poly(num):
    b = []
    for _ in range(4):
        b.append(num & 1)
        num >>= 1
    return GF(16)(b)

def gf16_to_num(poly):
    return poly.integer_representation()

def get_eqn_matrix(known_pt, known_ct, n=len(ALPHABET)):
    M = []

    L = known_ct[1:]
    S = known_pt
    R = known_pt[1:]

    for l,s,r in zip(L, S, R):
        eqn = [0]*n
        eqn[ALPHABET.index(l)] += num_to_gf16_poly(1) 
        eqn[ALPHABET.index(s)] += num_to_gf16_poly(1)
        eqn[ALPHABET.index(r)] += num_to_gf16_poly(1)
        M.append(eqn)

    return M

def vec_to_key(vec, n=N):
    key = ['0']*n
    for i,v in enumerate(vec[:n]):
        key[gf16_to_num(v)] = ALPHABET[i]
    return ''.join(key)

for i in range(1, len(plaintext)-N):
    M = get_eqn_matrix(plaintext, ciphertext)[i:i+N]
    M = Matrix(GF(16), M)
    nullity = M.nullity()

    if nullity > 5: # too much to bruteforce
        continue

    B = M.right_kernel_matrix()

    for lc in tqdm(product(range(N), repeat=nullity), total=N^nullity):
        v = B.linear_combination_of_rows([num_to_gf16_poly(alpha) for alpha in lc])

        if len(set(v)) != len(v):
            continue

        key = vec_to_key(v)
        cipher = Cipher(key)
        d = bytes.fromhex(cipher.decrypt(ciphertext))

        if b'DUCTF' in d:
            print(d)