Mayday Mayday

5 minutos de lectura

Se nos proporciona el código fuente en Python para cifrar la flag:

from Crypto.Util.number import getPrime, GCD, bytes_to_long
from secret import FLAG
from random import randint

class Crypto:
    def __init__(self, bits):
        self.bits = bits
        self.alpha = 1/9
        self.delta = 1/4
        self.known = int(self.bits*self.delta)
    
    def keygen(self):
        while True:
            p, q = [getPrime(self.bits//2) for _ in '__']
            self.e = getPrime(int(self.bits*self.alpha))
            φ = (p-1)*(q-1)
            try:
                dp = pow(self.e, -1, p-1)
                dq = pow(self.e, -1, q-1)
                self.n = p*q
                break
            except:
                pass

        return (self.n, self.e), (dp, dq)

    def encrypt(self, m):
        return pow(m, self.e, self.n)

rsa = Crypto(2048)
_, (dp, dq) = rsa.keygen()

m = bytes_to_long(FLAG)
c = rsa.encrypt(m)

with open('output.txt', 'w') as f:
    f.write(f'N = 0x{rsa.n:x}\n')
    f.write(f'e = 0x{rsa.e:x}\n')
    f.write(f'c = 0x{c:x}\n')
    f.write(f'dp = 0x{(dp >> (rsa.bits//2 - rsa.known)):x}\n')
    f.write(f'dq = 0x{(dq >> (rsa.bits//2 - rsa.known)):x}\n')

Y tenemos el resultado en output.txt:

N = 0x78fb80151a498704541b888b9ca21b9f159a45069b99b04befcb0e0403178dc243a66492771f057b28262332caecc673a2c68fd63e7c850dc534a74c705f865841c0b5af1e0791b8b5cc55ad3b04e25f20dedc15c36db46c328a61f3a10872d47d9426584f410fde4c8c2ebfaccc8d6a6bd1c067e5e8d8f107b56bf86ac06cd8a20661af832019de6e00ae6be24a946fe229476541b04b9a808375739681efd1888e44d41196e396af66f91f992383955f5faef0fc1fc7b5175135ab3ed62867a84843c49bdf83d0497b255e35432b332705cd09f01670815ce167aa35f7a454f8b26b6d6fd9a0006194ad2f8f33160c13c08c81fe8f74e13e84e9cdf6566d2f
e = 0x4b3393c9fe2e50e0c76920e1f34e0c86417f9a9ef8b5a3fa41b381355
c = 0x17f2b5a46e4122ff819807a9d92b6225c483cf93c9804381098ecd6b81f4670e94d8930001b760f1d26bc7aa7dda48c9e12809d20b33fdb4c4dd9190b105b7dab42e932b99aaff54023873381e7387f1b2b18b355d4476b664d44c40413d82a10635fe6e7322543943aed2dcfbe49764b8da70edeb88d6f63ee47f025be5f2f38319611ab74cd5db6f90f60870ecbb57a884f821d873db06aadf0e61ff74cc7d4c8fc1e527dba9b205220c6707f750822c675c530f8ad6956e41ab80911da49c3d6a7d27e93c44ba5968f2f47a9c5a2694c9d6da245ceffe9cab66b6043774f446b1b08ee4739d3cc716b87c8225a84d3c4ea2fdf68143d09f062c880a870554
dp = 0x59a2219560ee56e7c35f310a4d101061aa61e0ae4eae7605eb63784209ad488b4ed161e780811edd61bf593e2d385beccfd255b459382d8a9029943781b540e7
dq = 0x39719131fbfd8afbc972ca005a430d080775bf1a5b3e8b789aba5c5110a31bd155ff13fba1019bb6cb7db887685e34ca7966a891bfad029b55b92c11201559e5

Análisis del código fuente

El servidor usa RSA para cifrar la flag. Se nos da , y tales que

donde es la flag. Curiosamente, es un número primo de 227 bits ().

El servidor también calcula los exponentes privados para el descifrado de RSA-CRT:

Estos son números de 1024 bits, pero solo nos dan los 512 bits más significativos, digamos y .

Los anteriores y se pueden usar para descifrar la flag usando el Teorema Chino del Resto (CRT):

Método de Coppersmith

Cuando el reto elimina algunos bits, probablemente la solución está relacionada con el método de Coppersmith, tratando de recuperar raíces pequeñas de un polinomio módulo un número compuesto.

Haciendo matemáticas

Sabemos que

Por lo que:

Y entonces

Podemos obtener una buena aproximación de como:

Este número es fácil de factorizar. Luego, podemos considerar pares de números y e intentar buscar raíces pequeñas del polinomio

Tenemos que , que es lo que necesitamos, pero esto es difícil de resolver ya que sigue siendo bastante grande en comparación con .

Ajustando el polinomio

Podemos reducir el espacio de búsqueda con esta condición:

Entonces, podemos redefinir el polinomio como

Y ahora es mucho más pequeño, por lo que es más probable que encontremos raíces pequeñas.

Implementación en SageMath

En primer lugar, calculamos y calculamos sus divisores:

with open('output.txt') as f:
    n = int(f.readline().split(' = ')[1], 16)
    e = int(f.readline().split(' = ')[1], 16)
    c = int(f.readline().split(' = ')[1], 16)
    dp_hint = int(f.readline().split(' = ')[1], 16) << 512
    dq_hint = int(f.readline().split(' = ')[1], 16) << 512

kp_kq = (e * dp_hint - 1) * (e * dq_hint - 1) // n + 1

divs = divisors(kp_kq)

Dado que tiene muchos divisores, podemos considerar solo los que tienen más probabilidades de producir un número de 1024 bits dentro del tamaño de y :

possible_kp_kq = set()

for div in divs:
    kp, kq = div, kp_kq // div
    pH = (e * (dp_hint + 2 ** 512) - 1 + kp) // kp
    pL = (e * (dp_hint + 0) - 1 + kp) // kp
    qH = (e * (dq_hint + 2 ** 512) - 1 + kq) // kq
    qL = (e * (dq_hint + 0) - 1 + kq) // kq

    if all(int(x).bit_length() == 1024 for x in [pH, pL, qH, qL]):
        possible_kp_kq.add((kp, kq))

Ahora encontramos el valor de , definimos el polinomio e intentamos encontrar una raíz pequeña. Si existe y no es , entonces tenemos el resultado esperado y podemos calcular . En este punto es trivial descifrar la flag con RSA:

x = PolynomialRing(Zmod(n), 'x').gens()[0]

for kp, kq in possible_kp_kq:
    d_kp = int((pow(e, -1, kp) - dp_hint) % kp)
    P = (e * (dp_hint + kp * x + d_kp) - 1 + kp).monic()
    roots = P.small_roots(beta=0.5)

    if roots and roots[0] != n:
        p = int((e * (dp_hint + kp * roots[0] + d_kp) - 1 + kp) // kp)
        assert n % p == 0
        q = n // p
        d = pow(e, -1, (p - 1) * (q - 1))
        m = pow(c, d, n)
        print(bytes.fromhex(hex(m)[2:]).decode())
        break

Flag

Y esta es la flag. Hace referencia a un paper para realizar el ataque previsto, que también se basa en el método de Coppersmith:

$ python3 solve.py
HTB{f4ct0r1ng_w1th_just_4_f3w_b1ts_0f_th3_CRT_3xp0n3nts!https://eprint.iacr.org/2022/271.pdf}

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