MSS
5 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 < 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()}
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 < 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)}
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
El problema de este reto es que el polinomio se define sobre los enteros. Como resultado, si evaluamos $P(n)$ y aplicamos módulo $n$, obtendremos el valor de $\mathrm{key} \mod{n}$.
Sabiendo esto, podemos hacer lo mismo pero con números primos. El objetivo es obtener este sistema de congruencias:
$$ \begin{cases} P(p_1) = \mathrm{key} \mod{p_1} \\ P(p_2) = \mathrm{key} \mod{p_1} \\ \dots \\ P(p_k) = \mathrm{key} \mod{p_k} \\ \end{cases} $$
Este sistema de congruencias modulares se puede resolver utilizando el Teorema Chino del Resto (CRT), que generará el valor de $\mathrm{key} \mod{\prod p_k}$. Si $\prod p_k$ es lo suficientemente grande, el módulo no tendrá efecto y encontraremos el valor exacto de $\mathrm{key}$.
Todos estos números primos deben ser menores que $2^{15}$, y podemos usar un máximo de $k = 19$. Estos límites son suficientes para obtener el valor de $\mathrm{key}$ porque es un número de 256 bits, y $\prod p_k$ tendrá un valor máximo de $15 \cdot 19 = 285$ bits.
Implementación
Podemos programar este procedimiento en Python:
io = get_process()
primes, remainders = [], []
for _ in range(19):
p = getPrime(15)
io.sendlineafter(b'query = ', json.dumps(
{'command': 'get_share', 'x': p}).encode())
r = json.loads(io.recvline().decode()).get('y')
primes.append(p)
remainders.append(r % p)
key = crt(primes, remainders)[0]
io.sendlineafter(b'query = ', json.dumps({'command': 'encrypt_flag'}).encode())
io.recvuntil(b'[+] Here is your encrypted flag : ')
data = json.loads(io.recvuntil(b'}').decode())
iv = bytes.fromhex(data.get('iv'))
enc_flag = bytes.fromhex(data.get('enc_flag'))
key = sha256(str(key).encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(enc_flag), AES.block_size).decode()
io.success(flag)
Flag
Y aquí tenemos la flag:
$ python3 solve.py 94.237.54.170:55965
[+] Opening connection to 94.237.54.170 on port 55965: Done
[+] HTB{sm4ll_thr3sh0ld_n0_pr0bl3m_CRT_ru13s!}
[*] Closed connection to 94.237.54.170 port 55965
El script completo se puede encontrar aquí: solve.py.