https://app.hackthebox.com/challenges/478

Description

As you deciphered the Matrix, you discovered that the astronomy scientist had observed that certain stars were not real. He had created two 5x5 matrices with values based on the time the stars were bright, but after some time, the stars stopped emitting light. Nonetheless, he had managed to capture every matrix until then and created an algorithm that simulated their generation. However, he could not understand what was hidden behind them as he was missing something. He believed that if he could understand the stars, he would be able to locate the secret tombs where the relic was hidden.

Exploitation

#!/usr/bin/env python3
from pwn import *
from sage.all import GF, Matrix
from sympy.ntheory.modular import crt
import sys

def get_matrices(r):
    r.sendlineafter(b'> ', b'C')
    r.recvline()
    ct = eval(r.recvline().strip().decode())
    key = eval(r.recvline().strip().decode())
    ct_list = [list(row) for row in ct]
    key_list = [list(row) for row in key]
    return [x for row in ct_list for x in row], [x for row in key_list for x in row]

def solve_matrix(ct, key, p):
    try:
        ct_mat = Matrix(GF(p), 5, 5, ct)
        key_mat = Matrix(GF(p), 5, 5, key)
        result = ct_mat * key_mat.inverse()
        return [int(x) for x in result.list()]
    except:
        return None

def solve_with_matrices(M_1, M_2, p1, p2):
    res = []
    for i in range(len(M_1)):
        crt_result = int(crt([p1, p2], [M_1[i], M_2[i]])[0])
        res.append(crt_result % 256)
    return ''.join(chr(x) for x in res)

def main():
    if len(sys.argv) != 2:
        print(f"Usage: {sys.argv[0]} <ip:port>")
        sys.exit(1)
    try:
        host, port = sys.argv[1].split(':')
        port = int(port)
    except:
        print("[-] Invalid ip:port format")
        sys.exit(1)
    context.log_level = 'critical'
    print("[*] Starting...")
    print("[*] Getting samples...")
    PRIMES = [17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
    try:
        r = remote(host, port)
        ct1, key1 = get_matrices(r)
        r.sendlineafter(b'> ', b'T')
        ct2, key2 = get_matrices(r)
        print("[*] Trying prime combinations...")
        for p1 in PRIMES:
            M_1 = solve_matrix(ct1, key1, p1)
            if not M_1:
                continue
            for p2 in PRIMES:
                if p2 == p1:
                    continue
                M_2 = solve_matrix(ct2, key2, p2)
                if not M_2:
                    continue
                try:
                    flag = solve_with_matrices(M_1, M_2, p1, p2)
                    if 'HTB{' in flag and '}' in flag:
                        print(f'[+] Found with primes {p1}, {p2}:')
                        print(f'[+] Flag: {flag}')
                        r.close()
                        return
                except:
                    continue
        print("[-] Could not find flag")
        r.close()
    except Exception as e:
        print(f"[-] Error: {e}")
        try:
            r.close()
        except:
            pass

if __name__ == '__main__':
    main()

Summary

Inside the Matrix: turn the RSA leak into a lattice recovery, rebuild the secret values, and decrypt the flag.