Waiting List
7 minutos de lectura
Se nos proporciona el código fuente del servidor en Python (challenge.py):
import json
import signal
import subprocess
import socketserver
from hashlib import sha1
from random import randint
from Crypto.Util.number import bytes_to_long, long_to_bytes
FLAG = 'HTB{dummyflag}'
class ECDSA:
def __init__(self):
self.n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
self.k = 0
self.g = 5
self.key = ... #choose your own key
def sign(self, pt):
h = sha1(pt).digest()
h = bytes_to_long(h)
h = bin(h)[2:]
h = int(h[:len(bin(self.n)[2:])], 2)
self.k = randint(1, self.n-1)
r = pow(self.g, self.k, self.n)
s = (pow(self.k, -1, self.n) * (h + self.key * r)) % self.n
lsb = self.k % (2 ** 7)
return {"h": hex(h)[2:], "r": hex(r)[2:], "s": hex(s)[2:], "lsb": bin(lsb)[2:] }
def verify(self, pt, sig_r, sig_s):
h = sha1(pt).digest()
h = bytes_to_long(h)
h = bin(h)[2:]
h = int(h[:len(bin(self.n)[2:])], 2)
sig_r = int(sig_r, 16)
sig_s = int(sig_s, 16)
c = pow(sig_s, -1, self.n)
k = (c *(h +self.key*sig_r)) %self.n
if sig_r== pow(self.g,k,self.n ):
if pt ==b'william;yarmouth;22-11-2021;09:00':
return 'Your appointment has been confirmed, congratulations!\n' +\
'Here is your flag: ' + FLAG
else:
return 'Your appointment has been confirmed!\n'
else: return 'Signature is not valid\n'
def challenge(req):
cipher = ECDSA()
req.sendall(b'Welcome to the SteamShake transplant clinic where our mission is to deliver the most vintage and high tech arms worldwide.\n'+\
b'Please use your signature to verify and confirm your appointment.\nEstimated waiting for next appointment: 14 months\n> ')
try:
dt = json.loads(req.recv(4096).strip())
res = cipher.verify(dt['pt'].encode(), dt['r'], dt['s'])
req.sendall(res.encode())
except Exception as e:
req.sendall(b'Invalid payload.\n')
exit(1)
class incoming(socketserver.BaseRequestHandler):
def handle(self):
signal.alarm(300)
req = self.request
challenge(req)
class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
def main():
socketserver.TCPServer.allow_reuse_address = True
server = ReusableTCPServer(("0.0.0.0", 2310), incoming)
server.serve_forever()
if __name__ == "__main__":
main()
También nos dan dos archivos CSV llamados appointments.txt y signatures.txt:
$ head appointments.txt
first_name;last_name;date;time
jamesrobert;cornes;05-01-2021;16:00
lyontine;buziak;11-10-2021;09:00
cassandr;carnell;26-09-2021;11:00
jaqueline;brummett;10-01-2021;15:00
norvol;moatz;09-04-2021;14:00
celestina;moog;02-11-2021;13:00
espute;nirjala;21-11-2021;10:00
bosten;inniss;09-05-2021;10:00
kardarius;hernandez-baranda;22-04-2021;17:00
$ head signatures.txt
h;r;s;k_lsb
7a143bfddd768449bf2808513f35f53758020c1f;1a42a9c82c8eb242b832199d068bcfba53089fae7f4fcd02754893943d6bb884;a1c09c0f8ebf0a109673af60e6b5e270f2fa55b73f5314871486d3fe3480d942;1001001
73c9e4487fbebc39eb4dcd1d92a3ba92d9d41ef8;3b1f1f5fb4aab1366ddb9a90dbec9a305606fef4226aa8d29e22f50dca3275f8;772b335fab52f06d7e274cdbb478da9e1dfd4445d3fd58ddad2e8a2f4bd4dd97;110101
21f07d3d82c5f89df812c6d7fea96b5637a9bc0d;848f21ad03f005ddd4bd38d0623dc5042f452c3160315ef203a04f38fd1ca2ad;ef19a1aa75c4430439e7a0900499f03c4c0f65b787c5053ee2a18d24af108f87;1110011
1deebeeddef3d3385703be677f45c2c61c5176aa;e7c43a7d237695d8e74a5e841f1d5c19a4f99cfc34413c5046d6063e7e13430b;3fd1c99cf9aa68def64b829c133c4e142eeb80e36fab8d6d3cd569348af93f20;1100010
b787146842b6faa23e69f1e97c3ce997f1a0612e;8fdc3ab9597442f3b0084a405b8dd4e2e143ec38ef7dc9c92dcff0755f7afef1;c9cd09095cfb5aae68a8eb19049f271e1e7274f115733a9ba4862eb6e9478017;111110
68cf88eda82006e5fdc818b5ac0e9247b5c97db4;e6c69f2947bfc0e94ec41de13a21c50f5041a15ee728b24e6d77103130bc91e;91b9fb3c39ec0cc46f3a65d1e25c7671aeea883a2076ba27d978405a309cd7cf;1001001
4ddacfec5160ee3ffb04108ed575883d7585397d;6284198683d767d4d39ca7631972691719c1af456068811b64fb7e7d3cb6738;301c93e7fa0de59dc9c25869012aa92b18e9117f10fe75b3ff04f448c55003cc;1100100
3ff6701d470eb511e4e8d54d8c28d7e55a4a3f3f;2cdb804e31396d692c8ea5893e3f9aaaa30ab93ac12e7dadb35060ca1cbd4eeb;15995cc5781c30aafb52c2716c364e183876c63daeb6b98cd1aeb4907393dc94;1010101
68f4293eda88207d716bee27cbad956c4ae75e36;107b1829c5a3f7e2c3069f413c51df90fc752f0aa07b1b44dc11400e58b8d492;a79de81c865646c3fe64b1fff6b691b3a0f5b1d62a245bdc9aa164adba15098a;1110000
Análisis del código fuente
El servidor implementa un algoritmo de firma digital sobre curva elíptica (ECDSA) para firmar citas de diferentes usuarios. El mensaje firmado tiene formato first_name;last_name;date;time. El propósito del reto es obtener una firma para el mensaje william;yarmouth;22-11-2021;09:00, como se muestra en verify:
def verify(self, pt, sig_r, sig_s):
h = sha1(pt).digest()
h = bytes_to_long(h)
h = bin(h)[2:]
h = int(h[:len(bin(self.n)[2:])], 2)
sig_r = int(sig_r, 16)
sig_s = int(sig_s, 16)
c = pow(sig_s, -1, self.n)
k = (c *(h +self.key*sig_r)) %self.n
if sig_r== pow(self.g,k,self.n ):
if pt ==b'william;yarmouth;22-11-2021;09:00':
return 'Your appointment has been confirmed, congratulations!\n' +\
'Here is your flag: ' + FLAG
else:
return 'Your appointment has been confirmed!\n'
else: return 'Signature is not valid\n'
Para eso, necesitamos encontrar el valor de self.key, que está oculto:
def __init__(self):
self.n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
self.k = 0
self.g = 5
self.key = ... #choose your own key
Para ello, tenemos que usar los mensajes y firmas proporcionados.
Implementación de ECDSA
El código para el ECDSA es correcto (más información aquí). Para firmar mensajes, usa SHA1 como la función hash y calcula:
$$ h = \mathrm{SHA1}{(m)} $$
$$ r = g^k \mod{n} $$
$$ s = k^{-1} \cdot \left(h + x \cdot r\right) \mod{n} $$
Hemos usado $x$ para self.key y $m$ para pt. La salida de la firma es el par $(r, s)$. El código de la función se explica por sí mismo:
def sign(self, pt):
h = sha1(pt).digest()
h = bytes_to_long(h)
h = bin(h)[2:]
h = int(h[:len(bin(self.n)[2:])], 2)
self.k = randint(1, self.n-1)
r = pow(self.g, self.k, self.n)
s = (pow(self.k, -1, self.n) * (h + self.key * r)) % self.n
lsb = self.k % (2 ** 7)
return {"h": hex(h)[2:], "r": hex(r)[2:], "s": hex(s)[2:], "lsb": bin(lsb)[2:] }
El fallo de seguridad
El problema aquí es que el servidor también devuelve los 7 bits menos significativos de los nonces $k$ (self.k) como lsb:
lsb = self.k % (2 ** 7)
Este regalo nos permite modelar el Hidden Number Problem (HNP) para hallar $x$.
Hidden Number Problem
El HNP generalmente se define como:
$$ t_i \cdot \alpha + a_i \equiv b_i \pmod{p} $$
Donde $\alpha$ ese el número oculto y los valores $t_i$ y $a_i$ son conocidos, dadas $i$ ecuaciones. Podemos transformar la fórmula de la firma ECDSA a este formato:
$$ s_i \equiv k_i^{-1} \cdot \left(h_i + x \cdot r_i\right) \pmod{n} $$
$$ s_i k_i \equiv h_i + x \cdot r_i \pmod{n} $$
$$ r_i \cdot x + h_i \equiv s_i k_i \pmod{n} $$
$$ (s_i^{-1} r_i) \cdot x + (s_i^{-1} h_i) \equiv k_i \pmod{n} $$
Además, sabemos 7 bits de $k_i$, entonces $k_i = 2^7 \cdot k^\mathrm{(MSB)}_i + k^\mathrm{(LSB)}_i$. Se sigue que
$$ (s_i^{-1} r_i) \cdot x + (s_i^{-1} h_i) \equiv 2^7 \cdot k^\mathrm{(MSB)}_i + k^\mathrm{(LSB)}_i \pmod{n} $$
$$ (2^{-7} s_i^{-1} r_i) \cdot x + \left(2^{-7} (s_i^{-1} h_i - k^\mathrm{(LSB)}_i)\right) \equiv k^\mathrm{(MSB)}_i \pmod{n} $$
Podemos definir un retículo que contenga la solución del HNP. En la definición, podemos usar el retículo formado por las columnas de:
$$ M = \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} $$
Donde $X$ ees una cota superior para los valores $b_i$. Obsérvese que el vector $(b_1, \dots, b_i, X \alpha / p, X)$ está en el retículo:
$$ \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} \cdot \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_i \\ \alpha \\ 1 \end{pmatrix} = \begin{pmatrix} c_1 p + \alpha t_1 + a_1 \\ c_2 p + \alpha t_2 + a_2 \\ \vdots \\ c_i p + \alpha t_i + a_i \\ X \alpha / p \\ X \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_i \\ X \alpha / p \\ X \end{pmatrix} $$
Nótese que $c_i$ son solo números enteros arbitrarios, son irrelevantes porque estamos trabajando $\mod{p}$. El vector objetivo debe ser un vector corto para que aparezca en la base reducida al aplicar el algoritmo LLL.
Podemos usar Python para generar la matriz sustituyendo los valores anteriores:
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
g = 5
pt = b'william;yarmouth;22-11-2021;09:00'
hs, rs, ss, ks_lsb = [], [], [], []
with open('signatures.txt') as f:
f.readline()
while (line := f.readline()):
values = line.split(';')
hs.append(int(values[0], 16))
rs.append(int(values[1], 16))
ss.append(int(values[2], 16))
ks_lsb.append(int(values[3], 2))
p = n
a_i = list(
map(
lambda s, h, k_lsb: pow(2, -7, p) * (pow(s, -1, p) * h - k_lsb) % p,
ss, hs, ks_lsb
)
)
t_i = list(
map(
lambda r, s: pow(2, -7, p) * pow(s, -1, p) * r % p,
rs, ss
)
)
X = 2 ** (n.bit_length() - 7)
raw_matrix = []
for i in range(len(a_i)):
raw_matrix.append([0] * i + [p] + [0] * (len(a_i) - i + 1))
raw_matrix.append(t_i + [X / p, 0])
raw_matrix.append(a_i + [0, X])
Si el vector $(b_1, \dots, b_i, \alpha, X \alpha / p, X)$ es suficientemente corto, el algoritmo LLL reducirá la base del retículo y el vector objetivo aparecerá en la base. En otras palabras, estaremos resolviendo el Shortest Vector Problem (SVP). Esto se puede hacer importando algunas funciones de SageMath:
M = Matrix(QQ, raw_matrix)
L = M.LLL()
for row in L.rows():
k = int(row[0] * 2 ** 7 + ks_lsb[0])
if rs[0] == pow(g, k, n) and row[-1] == X:
key = (ss[0] * k - hs[0]) * pow(rs[0], -1, n) % n
h = sha1(pt).digest()
h = bytes_to_long(h)
h = bin(h)[2:]
h = int(h[:len(bin(n)[2:])], 2)
r = pow(g, k, n)
s = (pow(k, -1, n) * (h + key * r)) % n
io = remote(host, port)
io.sendlineafter(b'> ', json.dumps({'pt': pt.decode(), 'r': hex(r), 's': hex(s)}).encode())
io.success(io.recv().decode())
Como se puede ver, estamos iterando sobre las filas de la base reducida (SageMath aplica LLL por filas, de ahí que definimos la matriz de entrada por filas también). Si para una fila determinada, el valor de $r$ es igual a $g^k$ con el correspondiente $k$ (teniendo en cuenta MSB y LSB), y también el último elemento del vector es $X$ (la cota superior), entonces tenemos el vector objetivo y podemos encontrar $x$ (self.key) para obtener una firma del mensaje esperado.
Finalmente, lo enviamos al servidor y esperamos para ver la flag.
Flag
Si ejecutamos el script, veremos la flag:
$ python3 solve.py 142.93.47.151:30991
[+] Opening connection to 142.93.47.151 on port 30991: Done
[+] Your appointment has been confirmed, congratulations!
Here is your flag: HTB{t3ll_m3_y0ur_s3cr37_w17h0u7_t3ll1n9_m3_y0ur_s3cr37_1fam31l}
[*] Closed connection to 142.93.47.151 port 30991
El script completo se puede encontrar aquí: solve.py.