Colliding Heritage
6 minutos de lectura
Se nos proporciona el código fuente del servidor en Python:
#!/usr/bin/env python3
import signal
from secrets import randbelow
from hashlib import md5
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
FLAG = "HTB{???????????????????????????}"
class MD5chnorr:
def __init__(self):
# while True:
# self.q = getPrime(128)
# self.p = 2*self.q + 1
# if isPrime(self.p):
# break
self.p = 0x16dd987483c08aefa88f28147702e51eb
self.q = (self.p - 1) // 2
self.g = 3
self.x = randbelow(self.q)
self.y = pow(self.g, self.x, self.p)
def H(self, msg):
return bytes_to_long(md5(msg).digest()) % self.q
def sign(self, msg):
k = self.H(msg + long_to_bytes(self.x))
r = pow(self.g, k, self.p) % self.q
e = self.H(long_to_bytes(r) + msg)
s = (k - self.x * e) % self.q
return (s, e)
def verify(self, msg, sig):
s, e = sig
if not (0 < s < self.q):
return False
if not (0 < e < self.q):
return False
rv = pow(self.g, s, self.p) * pow(self.y, e, self.p) % self.p % self.q
ev = self.H(long_to_bytes(rv) + msg)
return ev == e
def menu():
print('[S]ign a message')
print('[V]erify a signature')
return input('> ').upper()[0]
def main():
md5chnorr = MD5chnorr()
print('g:', md5chnorr.g)
print('y:', md5chnorr.y)
print('p:', md5chnorr.p)
for _ in range(3):
choice = menu()
if choice == 'S':
msg = bytes.fromhex(input('Enter message> '))
if b'I am the left hand' in msg:
print('No!')
else:
sig = md5chnorr.sign(msg)
print('Signature:', sig)
elif choice == 'V':
msg = bytes.fromhex(input('Enter message> '))
s = int(input('Enter s> '))
e = int(input('Enter e> '))
if md5chnorr.verify(msg, (s, e)):
if msg == b'I am the left hand':
print(FLAG)
else:
print('Valid signature!')
else:
print('Invalid signature!')
else:
print('Invalid choice...')
if __name__ == '__main__':
signal.alarm(30)
main()
Schnorr signature
El reto implementa un servidor de firma usando Schnorr. El algoritmo para firmar un mensaje $m$ es el siguiente:
- Elegir una clave de firma privada $x$ y un número primo $p$ tal que $q = \displaystyle\frac{p - 1}{2}$ es un número primo también
- elegir un valor nonce $k$ aleatorio
- Sea $r = (g^k \mod{p}) \mod{q}$
- Sea $e = H(r \;||\; m)$ donde $H$ es una función de hash y $||$ denota concatenación
- Sea $s = k - xe$
La firma es la pareja $(s, e)$.
Implementación en el reto
En este reto, la clase MD5chnorr usa MD5 como función de hash $H$ y el valor nonce $k$ no se elige al azar, sino como $k = H(m \;||\; x)$:
def H(self, msg):
return bytes_to_long(md5(msg).digest()) % self.q
def sign(self, msg):
k = self.H(msg + long_to_bytes(self.x))
r = pow(self.g, k, self.p) % self.q
e = self.H(long_to_bytes(r) + msg)
s = (k - self.x * e) % self.q
return (s, e)
El fallo de seguridad
El servidor nos permite usar dos opciones pero solo tres veces. Las dos opciones son firmar un mensaje y verificar un mensaje. La flag aparecerá siempre que podamos verificar un mensaje específico ("I am the left hand"). Obviamente, no podemos usar la opción S para firmar este mensaje específico:
for _ in range(3):
choice = menu()
if choice == 'S':
msg = bytes.fromhex(input('Enter message> '))
if b'I am the left hand' in msg:
print('No!')
else:
sig = md5chnorr.sign(msg)
print('Signature:', sig)
elif choice == 'V':
msg = bytes.fromhex(input('Enter message> '))
s = int(input('Enter s> '))
e = int(input('Enter e> '))
if md5chnorr.verify(msg, (s, e)):
if msg == b'I am the left hand':
print(FLAG)
else:
print('Valid signature!')
else:
print('Invalid signature!')
else:
print('Invalid choice...')
Por lo tanto, usaremos la opción S dos veces y luego V para enviar el mensaje requerido pero firmado adecuadamente. Por lo tanto, con las dos primeras firmas, de alguna manera debemos encontrar la clave privada $x$, necesaria para firmar mensajes arbitrarios.
Los algoritmos de firma digital se pueden comprometer si un valor nonce $k$ se reutiliza en diferentes firmas de mensajes. Dado que la única diferencia entre la firma Schnorr y MD5chnorr es el hecho de que $k$ no se elige al azar, este debe ser el fallo de seguridad.
De hecho, $k$ es el resultado de un hash MD5, que se sabe que tiene colisiones. Investigué un montón de formas de comprometer esta función de hash y encontré HashClash. También investigué sobre ataques de hash length extension y chosen prefix, pero ninguno de ellos era aplicable a este reto. Además, el nombre del reto contiene la palabra “Colliding”, por lo que la forma prevista debe involucrar una colisión, probablemente en MD5.
De hecho, la solución es muy simple porque MD5 es muy vulnerable a colisiones. En Wikipedia podemos encontrar dos cadenas hexadecimales ligeramente diferentes que dan como resultado el mismo hash MD5:
$ echo 'd131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70' | xxd -r -p | md5sum
79054025255fb1a26e4bc422aef54eb4 -
$ echo 'd131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70' | xxd -r -p | md5sum
79054025255fb1a26e4bc422aef54eb4 -
Lo que me costó mucho descubrir es que agregar el mismo bloque a las cadenas hexadecimales anteriores sigue produciendo el mismo hash MD5:
$ echo 'd131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70
0123456789abcdef 0123456789abcdef 0123456789abcdef 0123456789abcdef' | xxd -r -p | md5sum
5e1b7ce6b54d7313d856753d9d48f17c -
$ echo 'd131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70
0123456789abcdef 0123456789abcdef 0123456789abcdef 0123456789abcdef' | xxd -r -p | md5sum
5e1b7ce6b54d7313d856753d9d48f17c -
Esta es la clave para resolver el reto porque el nonce $k = H(m \;||\; x)$. Entonces, si ingresamos las cadenas especiales anteriores, podemos estar seguros de que ambos valores de $k$ serán iguales y, por lo tanto, comprometerán la firma para encontrar $x$.
Reutilización de nonce
Una vez que tenemos dos mensajes $m_1$ y $m_2$ que usan el mismo valor nonce $k$, podemos resolver el siguiente sistema de ecuaciones en variables $k$ y $x$:
$$ \begin{cases} s_1 = k - x e_1 \mod{q} \\ s_2 = k - x e_2 \mod{q} \\ \end{cases} $$
Por lo tanto, restando ambas ecuaciones tenemos que
$$ s_1 - s_2 = x e_2 - x e_1 \mod{q} $$
Y así despejamos $x$:
$$ x = (s_1 - s_2) \cdot (e_2 - e_1) \mod{q} $$
Una vez que tenemos $x$, podemos firmar cualquier mensaje.
Python implementation
Esta es la función main del script de la solución:
def main():
host, port = sys.argv[1].split(':')
io = remote(host, port)
msg1 = 'd131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70'
msg2 = 'd131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70'
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'Enter message> ', msg1.encode())
io.recvuntil(b'Signature: ')
s1, e1 = eval(io.recvline().decode())
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'Enter message> ', msg2.encode())
io.recvuntil(b'Signature: ')
s2, e2 = eval(io.recvline().decode())
x = (s2 - s1) * pow(e1 - e2, -1, q) % q
def sign(msg):
k = H(msg + long_to_bytes(x))
r = pow(g, k, p) % q
e = H(long_to_bytes(r) + msg)
s = (k - x * e) % q
return (s, e)
s, e = sign(b'I am the left hand')
io.sendlineafter(b'> ', b'V')
io.sendlineafter(b'Enter message> ', b'I am the left hand'.hex().encode())
io.sendlineafter(b'Enter s> ', str(s).encode())
io.sendlineafter(b'Enter e> ', str(e).encode())
io.success(io.recvline().decode())
Flag
Una vez que lo ejecutemos, encontraremos la flag:
$ python3 solve.py 161.35.36.167:32629
[+] Opening connection to 161.35.36.167 on port 32629: Done
[+] HTB{MD5_c0111510n_4nd_5chn022'5}
[*] Closed connection to 161.35.36.167 port 32629
El script completo se puede encontrar aquí: solve.py.