MSS

4 minutes to read

We are given the Python source code of the server:

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):
        self.d = d
        self.n = n
        self.BITS = BITS
        self.key = bytes_to_long(os.urandom(BITS//8))
        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 > 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()}

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

Source code analysis

The challenge creates a polynomial with random coefficients, where the key is the independent term:

class MSS:
    def __init__(self, BITS, d, n):
        self.d = d
        self.n = n
        self.BITS = BITS
        self.key = bytes_to_long(os.urandom(BITS//8))
        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)])

This key is used to encrypt the flag with SHA256 and AES:

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

We are allowed to evaluate the polynomial and retrieve the result:

    def get_share(self, x):
        if 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)}

So, the objective is to evaluate the polynomial in some points and retrieve the key in order to decrypt the flag.

Doing the maths

So, the polynomial can be expressed as

Notice that the 31 coefficients are 256-bit numbers, and we are allowed to get a maximum of 19 results (known as shares in this Mignotte Secret Sharing scheme):

    mss = MSS(256, 30, 19)

As a result, we are not able to recover the coefficients of the polynomial because we would need a minimum of 31 shares.

Solution

There is a flaw in this challenge that led to an unintended solution, which is pretty simple because the server lacks a check. Basically, we are able to evaluate the polynomial at , so that :

$ nc 94.237.52.253 42725

#     #  #####   #####               #       ###
##   ## #     # #     #             ##      #   #
# # # # #       #                  # #     #     #
#  #  #  #####   #####     #    #    #     #     #
#     #       #       #    #    #    #     #     #
#     # #     # #     #     #  #     #   ## #   #
#     #  #####   #####       ##    ##### ##  ###

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


Send in JSON format any of the following commands.

    - Get your share
    - Encrypt flag
    - Exit

query = {"command":"get_share","x":0}
{"approved": "True", "x": 0, "y": 59039542526107649351650840730991076528666491016633591549589766556211744611557}

There it is. Now we can simply get the encrypted flag and decrypt it with AES:

query = {"command":"encrypt_flag"}

[+] Here is your encrypted flag : {"iv": "5c336325fedc415ed64ccd1d934316e8", "enc_flag": "3531d154e41df5053ffc5a1db22c9caaa34b3484aaa8c1fd56a0c63c89278697e6ed75905858c116727bc0f6d799a1f1"}.

Flag

Here we have it, it talks about the CRT, which is covered in MSS Revenge:

$ python3 -q
>>> from hashlib import sha256
>>> from Crypto.Cipher import AES
>>> key = 59039542526107649351650840730991076528666491016633591549589766556211744611557
>>> key = sha256(str(key).encode()).digest()
>>> enc_flag = bytes.fromhex('3531d154e41df5053ffc5a1db22c9caaa34b3484aaa8c1fd56a0c63c89278697e6ed75905858c116727bc0f6d799a1f1')
>>> iv = bytes.fromhex('5c336325fedc415ed64ccd1d934316e8')
>>> AES.new(key, AES.MODE_CBC, iv).decrypt(enc_flag)
b'HTB{thr3sh0ld_t00_sm4ll_______CRT_t00_str0nk!}\x02\x02'