Space Pirates
3 minutes to read
We are given this Python source code:
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 _ 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()
print(sss.coeffs)
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()
if __name__ == '__main__':
main()
And this is the output:
share: (21202245407317581090, 11086299714260406068)
coefficient: 93526756371754197321930622219489764824
secret message: 1aaad05f3f187bcbb3fb5c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427231320ee7eca39bdfe175333341b7c
It uses Shamir Secret Sharing (SSS) to get a shared value to initialize random.seed, so that the key for an AES cipher is “random”. Then, it encrypts the flag using AES.
This time, the SSS parameters are $p = 92434467187580489687$, $k = 10$ and $n = 18$. Hence, the server creates a polynomial $P \in \mathbb{Z}/p\mathbb{Z}[x]$ like this:
$$ P(x) = s + a_1 x + a_2 x^2 + a_3 x^3 + \dots + a_k x^k $$
The secret is denoted by $s$ (the constant term).
Then, the server must compute some pairs $(x_i, P(x_i))$. In fact, from $(x_1, P(x_1))$ up to $(x_n, P(x_n))$.
The share that the program provides us is $(x_1, P(x_1))$. We are also given the coefficient $a_1$.
The vulnerability here is that the coefficients $a_i$ are related as follows:
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]))
Hence, $a_{i + 1} = \mathrm{MD5}(a_i)$. Considering that we know $a_1$, we can compute $a_2$, then $a_3$, and by induction $a_k$… So we can get all the coefficients of the polynomial $P$ but the constant term $s$.
Having all $a_i$ is useful because we also have the share $(x_1, P(x_1))$, so we can solve the following equation for $s$, which is the only unknown:
$$ P(x_1) = s + a_1 x_1 + a_2 x_1^2 + \dots + a_k x_1^k $$
Therefore
$$ s = P(x_1) - a_1 x_1 - a_2 x_1^2 - \dots - a_k x_1^k $$
And once we have $s$, we can initialize random.seed and obtain the same “random” key used for AES encryption in order to decrypt the ciphertext and get the flag.
All computations are written in this Python script: solve.py:
$ python3 solve.py
The treasure is located at galaxy VS-708.
Our team needs 3 light years to reach it.
Our solar cruise has its steam canons ready to fire in case we encounter enemies.
Next time you will hear from us brother, everyone is going to be rich!
HTB{1_d1dnt_kn0w_0n3_sh4r3_w45_3n0u9h!1337}