HTB 2021 Uni CTF Quals - Space Pirates writeup

 Space Pirates

For this challenge we got a file containing some cryptosystem, and an encrypted file containing the output of a message encrypted with that cryptosystem. With the encrypted message, a share and coefficient are also included:

share: (21202245407317581090, 11086299714260406068)
coefficient: 93526756371754197321930622219489764824
secret message: 1aaad05f3f187bcbb3fb5c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427231320ee7eca39bdfe175333341b7c

The way the secret message is encrypted and output is as follows:

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()

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

Since it’s using AES-ECB, we don’t expect much to be able to do there. But the key that is used is random, where the randomness is seeded with a value that comes from the Shamir class:

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]

It’s called Shamir, likely in reference to the Shamir Secret Sharing scheme. In short: the way Shamir Secret Sharing normally works is with multiple shares $(x_i, y_i)$ with $x_i \neq 0$. For each of these shares, $y_i = f(x_i)$ holds for a polynomial $f(x)$. To get back from the shares to the correct polynomial, at least a certain number of shares is necessary, so that the polynomial can be recovered. The output of $f(0)$ is then the secret value (which is not one of the shares as $x = 0$).

This also seems to be roughly what the code is doing, but that is not something we actually need to break. All coefficients in the code are based of the previous coefficient, and we know the second coefficient - it is given with the message. With the one share we also have, we can use this to calculate the secret, and thus the key for the decryption.

With $f(x)$ being the polynomial using the coefficients $c_i$, $x_s$ the $x$ of the share, and $y_s$ the $y$ value of the share, this works because of the following: \begin{align*} f(x) &= c_0 + c_1 \cdot x + c_2 \cdot x^2 + \cdots + c_k \cdot x^k \newline \text{secret} &= f(0) \newline &= c_0 + c_1 \cdot 0 + \cdots + c_k \cdot 0^k \newline &= c_0 \newline y_s &= f(x_s) \newline &= c_0 + c_1 \cdot x_s + \cdots + c_k \cdot x_s^k \newline &= \text{secret} + c_1 \cdot x_s + \cdots + c_k \cdot x_s^k \newline => \newline \text{secret} &= y_s - (c_1 \cdot x_s + \cdots + c_k \cdot x_s^k) \newline \end{align*}

We know the $y_s$, $x_s$, and $c_1$ (the coefficient given with the message), so we only need to calculate all the $c_i$’s. This is done with the calc_coeffs function, which just takes the MD5 of the previous coefficient to calculate the next. We can do that too.

Bringing this together, we get the following solve script (which we executed in SageMath):

from hashlib import md5
prime = 92434467187580489687
k=10
n=18
share = (21202245407317581090, 11086299714260406068)

coeff1 = 93526756371754197321930622219489764824

secretMessage = 0x1aaad05f3f187bcbb3fb5c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427231320ee7eca39bdfe175333341b7c
from Crypto.Util.number import long_to_bytes
secretMessage = long_to_bytes(secretMessage)
from Crypto.Cipher import AES

def subs(x , coeffs, p):
    res = 0
    for i, coeff in enumerate(coeffs):
        res += (coeff * pow(x,i,p))  % p
    return res % p

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

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

coeffs = [0, coeff1]
for i in range(1,k-1):
    coeffs.append(next_coeff(coeffs[i]))

print(f"coeffs= {coeffs}")

y  = calc_y(share[0], coeffs, prime)

secret = (share[1] - y) % prime

print(f"secret={secret % prime}")

seed(secret)
key = randbytes(16)
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(secretMessage)
print(flag)

Which outputs the message containing the flag:

sage: load('solve2.py')
coeffs= [0, 93526756371754197321930622219489764824, 240113147373490959044275841696533066373, 277069233924763976763702126953224703576, 251923626603331727108061512131337433905, 303281427114437576729827368985540159120, 289448658221112884763612901705137265192, 175064288864358835607895152573142106157, 28168790495986486687119360052973747333, 320025932402566911430256919284757559396]
secret=39612257993477957104
b'The treasure is located at galaxy VS-708.\nOur team needs 3 light years to reach it.\nOur solar cruise has its steam canons ready to fire in case we encounter enemies.\nNext time you will hear from us brother, everyone is going to be rich!\nHTB{1_d1dnt_kn0w_0n3_sh4r3_w45_3n0u9h!1337}\x08\x08\x08\x08\x08\x08\x08\x08'

HTB{1_d1dnt_kn0w_0n3_sh4r3_w45_3n0u9h!1337}