Biased Heritage
7 minutos de lectura
Este reto es una especie de continuación de Colliding Heritage. Se nos proporciona el código fuente del servidor en Python:
#!/usr/bin/env python3
import signal
from secrets import randbelow
from hashlib import sha256
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
FLAG = "HTB{???????????????????????????????????????}"
class SHA256chnorr:
def __init__(self):
# while True:
# self.q = getPrime(512)
# self.p = 2*self.q + 1
# if isPrime(self.p):
# break
self.p = 0x184e26a581fca2893b2096528eb6103ac03f60b023e1284ebda3ab24ad9a9fe0e37b33eeecc4b3c3b9e50832fd856e9889f6c9a10cde54ee798a7c383d0d8d2c3
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(2 * sha256(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():
sha256chnorr = SHA256chnorr()
print('g:', sha256chnorr.g)
print('y:', sha256chnorr.y)
print('p:', sha256chnorr.p)
for _ in range(3):
choice = menu()
if choice == 'S':
msg = bytes.fromhex(input('Enter message> '))
if b'right hand' in msg:
print('No!')
else:
sig = sha256chnorr.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 sha256chnorr.verify(msg, (s, e)):
if msg == b'right 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 SHA256chnorr usa SHA256 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 ("right 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, cómo forzamos en Colliding Heritage. Este enfoque ya no es factible ya que SHA256 es resistente a colisiones.
Cuando vi la palabra “Biased” en nombre del reto, me acordé de un artículo llamado Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies. En este documento, se utiliza la reducción de retículo (lattice) mediante LLL para resolver el Hidden Number Problem (HNP) en el algoritmo de firma digital de curva elíptica (ECDSA) cuando los nonces $k$ no se eligen correctamente (por ejemplo, su valor es mucho más corto que el valor de $q$).
HNP en nonces sesgados
Sabía que este era el enfoque previsto ya que SHA256 genera un número de 256 bits (64 bytes) y el número primo $p$ es enorme (y, por lo tanto, $q$ también). Por lo tanto, tenemos la siguiente configuración dado que debemos firmar dos mensajes arbitrarios $m_1$ y $m_2$:
$$ s_1 = k_1 - x e_1 \mod{q} \\ s_2 = k_2 - x e_2 \mod{q} \\ $$
El HNP trata de resolver la ecuación $a_i + k_i = \alpha \cdot t_i \mod{n}$, donde $\alpha$ es el número oculto y $k_i < 2^l$, para cierto $l \in \mathbb{Z}$. Se conocen los valores de $ a_i $ y $ b_i $.Podemos reformular el HNP para nuestra situación de la siguiente manera:
- Sea $a_i = -s_i$
- Sea $t_i = e_i$
- Sea $\alpha = x$
- Sea $n = q$
Entonces obtenemos la ecuaciónn $s_i = k_i - x \cdot e_i \mod{q}$. Antes de continuar con la solución, obsérvese que la función de hash realmente genera dos veces el hash:
def H(self, msg):
return bytes_to_long(2 * sha256(msg).digest()) % self.q
Este hecho rompió mis planes por un minuto, porque ahora $k$ tenía 512 bits y era mucho más cercano a $q$ que antes. Sin embargo, luego me di cuenta de que el HNP todavía era resoluble porque el hash se repetía, así que si $k’$ es el hash implementaco, tenemos que $k’ = k \;||\; k = 2^{256} k + k = (2^{256} + 1) k$. Entonces podemos agregar esta condición a la ecuación del HNP de la siguiente manera (sea $M = (2^{256} + 1)^{-1} \mod{q}$):
$$ s_i = k'_i - x \cdot e_i \mod{q} $$
$$ s_i = (2^{256} + 1) k_i - x \cdot e_i \mod{q} $$
$$ M s_i = k_i - x \cdot M e_i \mod{q} $$
Tomando nuevamente los parámetros del HNP estándar, tenemos:
- Sea $a_i = - M s_i$
- Sea $t_i = M e_i$
En este punto, el HNP se puede solucionar utilizando la siguiente base de lattice ($R = 2^{256}$, una cora superior para $k_i$):
$$ \begin{pmatrix} q & 0 & 0 & 0 \\ 0 & q & 0 & 0 \\ t_1 & t_2 & R / q & 0 \\ a_1 & a_2 & 0 & R \\ \end{pmatrix} $$
El algoritmo para resolver el HNP implica el uso de LLL para reducir la base del lattice y encontrar un vector corto cuyos componentes son $(-k_1, -k_2, R \alpha / q, R)$. Se puede encontrar más información en este artículo.
Una vez que tenemos el valor de $k_1$ o $k_2$, es trivial encontrar $x$ y, por lo tanto, firmar el mensaje requerido para encontrar la flag.
Implementación en Python
Usando algunas funciones de SageMath, podemos escribir estas instrucciones para resolver el reto:
io = get_process()
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'Enter message> ', b'A'.hex().encode())
io.recvuntil(b'Signature: ')
s1, e1 = eval(io.recvline().decode())
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'Enter message> ', b'B'.hex().encode())
io.recvuntil(b'Signature: ')
s2, e2 = eval(io.recvline().decode())
R = 2 ** 256
M = pow(R + 1, -1, q)
a1 = -M * s1 % q
a2 = -M * s2 % q
t1 = M * e1 % q
t2 = M * e2 % q
M = matrix(QQ, [
[q, 0, 0, 0],
[0, q, 0, 0],
[t1, t2, R / q, 0],
[a1, a2, 0, R],
])
B = M.LLL()
for row in B.rows():
k1, k2 = -row[0], -row[1]
x1 = ((R + 1) * k1 - s1) * pow(e1, -1, q) % q
x2 = ((R + 1) * k2 - s2) * pow(e2, -1, q) % q
if (s1, e1) == sign(b'A', x1):
x = x1
elif (s2, e2) == sign(b'B', x2):
x = x2
else:
continue
s, e = sign(b'right hand', x)
io.sendlineafter(b'> ', b'V')
io.sendlineafter(b'Enter message> ', b'right hand'.hex().encode())
io.sendlineafter(b'Enter s> ', str(s).encode())
io.sendlineafter(b'Enter e> ', str(e).encode())
io.success(io.recv().decode())
break
Flag
El algoritmo no es completamente fiable, pero eventualmente imprimirá la flag:
$ python3 solve.py 209.97.134.50:30631
[+] Opening connection to 209.97.134.50 on port 30631: Done
[+] HTB{full_s1z3_n0nc3_l4cks_ful1_s1z3_3ntr0py}
[*] Closed connection to 209.97.134.50 port 30631
El script completo se puede encontrar aquí: solve.py.