Chris Ruggieri (Neocount Phoenix)

Security Blog, Rants, Raves, Write-ups, and Code

Space Pirates

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. Our agents entered his
Base Points: Easy - Retired [0]
Rated Difficulty:
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
from Crypto.Util.number import bytes_to_long

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()
    
    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()
      
msg.enc:
share: (21202245407317581090, 11086299714260406068)
coefficient: 93526756371754197321930622219489764824
secret message: 1aaad05f3f187bcbb3fb6c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91
d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097a
d8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f
76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a8
18a5427231320ee7eca39bdfe175333341b7c
      
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. Our agents entered his

We have a very important clue in the msg.enc file. The shares and coefficient lead directly to Shamir Secret Sharing (as does the SSS line clearly saying Shamir). This is going to be very similar to the "Please don't share" challenge. We can also see in the next_coeff function of the chall.py file that it is an MD5 conversion. We can also (the n=10 or first numeric argument in the SSS line) that we only need the next 9 coefficients. We should be able to script out a method of finding these coefficients and reversing the Shamir Secret Sharing to break this message.

 
# sss_reverse.py
#!/bin/python3

import base64
from Crypto import Random
from Crypto.Cipher import AES
from random import randint, 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)
        # init_y = (secret + coeffs[1] * init_x + coeffs[2] * init_x^1 + ... + coeffs[9] * init_x^9) % P
        sum = 0

        for i in range(len(coeffs)):
                init_y -= coeffs[i] * (init_x ** (i + 1))

        GCD = math.gcd(p, 1)
        secret = (GCD * (init_y)) % p
        return secret

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

enc = '1aaad05f3f187bcbb3fb5c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29
f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5d
f079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587
400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427
231320ee7eca39bdfe175333341b7c'

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

There it is! HTB{1_d1dnt_kn0w_0n3_sh4r3_w45_3n0u9h!1337}