Space Pirates

Challenge details

Name	Space Pirates
Hint	Jones and his crew have started a long journey to discover the legendary treasure left by the guardians of time in the early beginnings of the universe. Mr Jones, though, is wanted by the government for his crimes as a pirate.
Difficulty	Easy - Retired [0]
Rated difficulty
First blood	HTB-Bot
Creator	P3t4

This time we have two files and the hint:

chall.py:
from sympy import *
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint, randbytes, seed

FLAG = b'HTB{dummyflag}'

class Shamir:
    def __init__(self, prime, k, n):
        self.p = prime
        self.secret = randint(1, self.p - 1)
        self.k = k
        self.n = n
        self.coeffs = [self.secret]
        self.x_vals = []
        self.y_vals = []

    def next_coeff(self, val):
        return int(md5(val.to_bytes(32, byteorder="big")).hexdigest(), 16)

    def calc_coeffs(self):
        for i in range(1, self.n + 1):
            self.coeffs.append(self.next_coeff(self.coeffs[i - 1]))

    def calc_y(self, x):
        y = 0
        for i, coeff in enumerate(self.coeffs):
            y += coeff * x ** i
        return y % self.p

    def create_pol(self):
        self.calc_coeffs()
        self.coeffs = self.coeffs[:self.k]
        for i in range(self.n):
            x = randint(1, self.p - 1)
            self.x_vals.append(x)
            self.y_vals.append(self.calc_y(x))

    def get_share(self):
        return self.x_vals[0], self.y_vals[0]


def main():
    sss = Shamir(92434467187580489687, 10, 18)
    sss.create_pol()
    share = sss.get_share()
    seed(sss.secret)
    key = randbytes(16)
    cipher = AES.new(key, AES.MODE_ECB)
    enc_FLAG = cipher.encrypt(pad(FLAG, 16)).hex()

    with open('msg.enc', 'w') as f:
        f.write('share: ' + str(share) + '\n')
        f.write('coefficient: ' + str(sss.coeffs[1]) + '\n')
        f.write('secret message: ' + str(enc_FLAG) + '\n')

if __name__ == "__main__":
    main()

msg.enc:
share: (21202245407317581090, 11086299714260406068)
coefficient: 93526756371754197321930622219489764824
secret message: 1aaad05f3f187bcbb3fb6c9e233ea339...

The share and coefficient point directly to Shamir Secret Sharing. The next_coeff function derives each coefficient with MD5, and the threshold value of 10 means we need the next nine coefficients. From there, we can reconstruct the secret and use it as the seed that generated the AES key.

#!/bin/python3
from Crypto.Cipher import AES
from random import randbytes, seed
from hashlib import md5
import math


def next_coeff(val):
    return int(md5(val.to_bytes(32, byteorder="big")).hexdigest(), 16)


def calc_coeffs(init_coeff, coeffs):
    for i in range(8):
        coeffs.append(next_coeff(coeffs[i]))


def rev_secret(init_coeff, init_x, init_y, p):
    coeffs = [init_coeff]
    calc_coeffs(init_coeff, coeffs)
    for i in range(len(coeffs)):
        init_y -= coeffs[i] * (init_x ** (i + 1))
    gcd = math.gcd(p, 1)
    return (gcd * init_y) % p


secret = rev_secret(
    93526756371754197321930622219489764824,
    21202245407317581090,
    11086299714260406068,
    92434467187580489687,
)

enc = '1aaad05f3f187bcbb3fb6c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427231320ee7eca39bdfe175333341b7c'

seed(secret)
key = randbytes(16)
cipher = AES.new(key, AES.MODE_ECB)
print(cipher.decrypt(bytes.fromhex(enc)).decode("ascii"))

There it is: HTB{1_d1dnt_kn0w_0n3_sh4r3_w45_3n0u9h!1337}