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
$$ P(x) = \mathrm{key} + a_1 x + a_2 x^2 + \dots + a_{30} x^{30} $$
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 $x = 0$, so that $P(0) = \mathrm{key}$:
$ 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'