MSS
4 minutos de lectura
Se nos proporciona el código fuente en Python del servidor:
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()
Análisis del código fuente
El reto crea un polinomio con coeficientes aleatorios, donde key es el término independiente:
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)])
Esta key se usa para cifrar la flag con SHA256 y 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()}
Se nos permite evaluar el polinomio y obtener el resultado:
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)}
Entonces, el objetivo es evaluar el polinomio en algunos puntos y recuperar la key para descifrar la flag.
Haciendo matemáticas
Entonces, el polinomio se puede expresar como
$$ P(x) = \mathrm{key} + a_1 x + a_2 x^2 + \dots + a_{30} x^{30} $$
Obsérvese que los 31 coeficientes son números de 256 bits, y se nos permite obtener un máximo de 19 resultados (conocidos como shares en este Mignotte Secret Sharing scheme):
mss = MSS(256, 30, 19)
Como resultado, no podemos recuperar los coeficientes del polinomio porque necesitaríamos un mínimo de 31 shares.
Solución
Hay un fallo en este reto que condujo a una solución no intencionada, que es bastante simple porque el servidor no comprueba un valor en especial. Básicamente, podemos evaluar el polinomio en $x = 0$, y así $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}
Ahí está. Ahora podemos simplemente obtener la flag cifrada y descifrarla con AES:
query = {"command":"encrypt_flag"}
[+] Here is your encrypted flag : {"iv": "5c336325fedc415ed64ccd1d934316e8", "enc_flag": "3531d154e41df5053ffc5a1db22c9caaa34b3484aaa8c1fd56a0c63c89278697e6ed75905858c116727bc0f6d799a1f1"}.
Flag
Aquí lo tenemos, habla del CRT, que es un concepto que cubro en 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'