Details

This challenge was given to the HackTheBox University CTF 2023. It was a crypto challenge of easy difficulty. A server is running for this challenge, and the code running on it is given.

Overview

The code

import os, random, json
from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import FLAG

class MSS:
    def __init__(self, BITS, d, n): # 256, 30, 19
        self.d = d # 30
        self.n = n # 19
        self.BITS = BITS # 256
        self.key = bytes_to_long(os.urandom(BITS//8)) # 256//8 = 32
        self.coeffs = [self.key] + [bytes_to_long(os.urandom(self.BITS//8)) for _ in range(self.d)]

    def poly(self, x):
        return sum([self.coeffs[i] * x**i for i in range(self.d+1)])

    def get_share(self, x):
        if x < 1 or x > 2**15:
            return {'approved': 'False', 'reason': 'This scheme is intended for less users.'}
        elif self.n < 1:
            return {'approved': 'False', 'reason': 'Enough shares for today.'}
        else:
            self.n -= 1
            return {'approved': 'True', 'x': x, 'y': self.poly(x)}
    
    def encrypt_flag(self, m):
        key = sha256(str(self.key).encode()).digest()
        iv = os.urandom(16)
        cipher = AES.new(key, AES.MODE_CBC, iv)
        ct = cipher.encrypt(pad(m, 16)) 
        return {'iv': iv.hex(), 'enc_flag': ct.hex(), 'keysha': key, 'key': self.key }

def show_banner():
    print("""
#     #  #####   #####               #       ###   
##   ## #     # #     #             ##      #   #  
# # # # #       #                  # #     #     # 
#  #  #  #####   #####     #    #    #     #     # 
#     #       #       #    #    #    #     #     # 
#     # #     # #     #     #  #     #   ## #   #  
#     #  #####   #####       ##    ##### ##  ###

This is a secure secret sharing scheme with really small threshold. We are pretty sure the key is secure...
    """)

def show_menu():
    return """
Send in JSON format any of the following commands.

    - Get your share
    - Encrypt flag
    - Exit

query = """


def main():
    mss = MSS(256, 30, 19)
    show_banner()
    while True:
        try:
            query = json.loads(input(show_menu()))
            if 'command' in query:
                cmd = query['command']
                if cmd == 'get_share':
                    if 'x' in query:
                        x = int(query['x'])
                        share = mss.get_share(x)
                        print(json.dumps(share))
                    else:
                        print('\n[-] Please send your user ID.')
                elif cmd == 'encrypt_flag':
                    enc_flag = mss.encrypt_flag(FLAG)
                    print(f'\n[+] Here is your encrypted flag : {json.dumps(enc_flag)}.')
                elif cmd == 'exit':
                    print('\n[+] Thank you for using our service. Bye! :)')
                    break
                else:
                    print('\n[-] Unknown command:(')
        except KeyboardInterrupt:
            exit(0)
        except (ValueError, TypeError) as error:
            print(error)
            print('\n[-] Make sure your JSON query is properly formatted.')
            pass

if __name__ == '__main__':
    main()

We are allowed to perform two actions on the server. To get a share and to get the encrypted flag.

The get_share method can be called at most 19 times. It returns a share of the secret, which is a point on a polynomial of degree 30.

$$ f(x) = a_0 + a_1x + a_2x^2 + … + a_{30}x^{30},;where;a_0=key $$

We need to find the key to decrypt the flag. This would be easy if we could get 30 shares, but we can only get 19.

Solution

We can notice that if we take the polynomial and evaluate it modulo x, we get the key, modulo x.

$$ f(x) = a_0 + a_1x + a_2x^2 + … + a_{30}x^{30} \equiv a_0 \pmod{x} $$

So we can get 19 results of the form

$$ key \equiv f(x) \pmod{x} $$

Using the Chinese Remainder Theorem we can get the key.

The Chinese Remainder Theorem states that given a system of congruences

$$ \begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ … \ x \equiv a_n \pmod{m_n} \end{cases} $$

where $m_1, m_2, …, m_n$ are pairwise coprime, there exists a unique solution modulo $m_1m_2…m_n$ and we can calculate it.

To make the selection for $m_1, m_2, …, m_n$ easier, we can choose primes. We can choose randomly 15-bit primes and get the key modulo their product.

The product has to be larger than the key because the modulo operation will not change the value of the key.

The following code gets the key using the Chinese Remainder Theorem.

from hashlib import sha256
from Crypto.Util.number import getPrime
from pwn import *
import json
from Crypto.Cipher import AES
from sympy.ntheory.modular import crt

r = remote("83.136.255.120", 39735)
# r = process(["python3", "./server.py"])

primes = []
results = []
for _ in range(19):
    primes.append(getPrime(15))

# Or can be hardcoded
# primes = [32569, 32573, 32579, 32587, 32603, 32609, 32611, 32621, 32633, 32647, 32653, 32687, 32693, 32707, 32713, 32717, 32719, 32749, 2**15]

for prime in primes:
    r.recvuntil(b"query = ")
    r.sendline(b'{"command": "get_share", "x": %d}' % prime)
    data = json.loads(r.recvline().decode().strip())
    res = data["y"] % prime
    results.append(res)

a = results # x = a mod x
n = primes # x = x mod n

r.recvuntil(b"query = ")
r.sendline(b'{"command": "encrypt_flag"}')
r.recvline()
data = r.recvline().decode()
data = json.loads(data[data.find("{"):-2])

iv = bytes.fromhex(data["iv"])
enc_flag = bytes.fromhex(data["enc_flag"])

key = int(crt(n,a)[0])

key = sha256(str(key).encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(enc_flag)
print("Flag:",flag) # Flag: b'HTB{thr3sh0ld_t00_sm4ll_______CRT_t00_str0nk!}\x02\x02'

Details#

Overview#

Solution#

Details

Overview

Solution