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 es el siguiente:

Elegir una clave de firma privada y un número primo tal que es un número primo también
elegir un valor nonce aleatorio
Sea
Sea donde es una función de hash y denota concatenación
Sea

La firma es la pareja .

Implementación en el reto

En este reto, la clase SHA256chnorr usa SHA256 como función de hash y el valor nonce no se elige al azar, sino como :

    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 , necesaria para firmar mensajes arbitrarios.

Los algoritmos de firma digital se pueden comprometer si un valor nonce 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 no se eligen correctamente (por ejemplo, su valor es mucho más corto que el valor de ).

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 es enorme (y, por lo tanto, también). Por lo tanto, tenemos la siguiente configuración dado que debemos firmar dos mensajes arbitrarios y :

El HNP trata de resolver la ecuación , donde es el número oculto y , para cierto . Se conocen los valores de y . Podemos reformular el HNP para nuestra situación de la siguiente manera:

Entonces obtenemos la ecuaciónn . 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 tenía 512 bits y era mucho más cercano a 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 es el hash implementado, tenemos que . Entonces podemos agregar esta condición a la ecuación del HNP de la siguiente manera (sea ):

Tomando nuevamente los parámetros del HNP estándar, tenemos:

En este punto, el HNP se puede solucionar utilizando la siguiente base de lattice (, una cota superior para ):

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 . Se puede encontrar más información en este artículo.

Una vez que tenemos el valor de o , es trivial encontrar 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 157.245.38.221:31207
[+] Opening connection to 157.245.38.221 on port 31207: Done
[+] HTB{unf027un4731y_7h3_n0nc3_1uck5_3n720py!!}
[*] Closed connection to 157.245.38.221 port 31207

El script completo se puede encontrar aquí: solve.py.