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 = 0x8415befe8ed2f11bc9980dca665d9f011ca1993cac84cbfa19b5b467ad66719eb5dca91f802d3cedd78395b3f94b7f937af8bd0789601b7b68f62e833d1304f2e49058e024a2fc60611017466dcc07c67121604f04d700a15a2e6d2bd146a433b004905c76e543bf1ad3cc26536592bb27081e77c39728535c8d44294dcf28d2199bc1f96ccebe018d12cc8660804f88555887208d4685465ffaa6433e8c0c6bbed3d8ce3f10e1b15962811246292dd9f52728f94a520449db79c9f1cf056d0600dbeb32f6206f9e80ad76570433f4c58fc46c33aa5f1dd7082fdbd2b92981f290d2fca9c135b2cd3d12e794da78f10f8548df11858e2c79af9218e97f09c1a1
e = 0x447a951fc908492e818cad6d6f0ab1b0212b57f952575e391bec5ad43
c = 0x23e6597702fba920abcbd5502b4102c0d88c9cac2186231444f4f23bf3e721031bb45cff4fa7dc325c9fc6d7fd51a216afa2161478e8e6610c350c9d5568506c8c94d0385cc77565b402db266e73e301473c0aa5149e920b66e3c81391b488812ef42a451d3003d1ba9d18befbdc38adfb5ca8f67a098ffb86e6aaa1230be7bc54fbade19f2f6d273f62ce07d92aa0356b979f108135c8fb33c77bd6b4eb07cce383f82ae3693feb1ebe3370974db1ae05919661558ce637c922caceb295a5c7717f5fdfd353d6b3b05113194fea4573b7a205ae0c2b034997d1bbbf1eee029499d7116b75413558d09a57b74315b45a9f17b2099dd647da1d63ccb5cb92cb2e
dp = 0xc8c6f6c4408d9d34b18948d976313329f4e09e722df217fe8dbd0684dbe52bccdcf4de9e6697d788601d753221886b1bc689e68e9745d1297a39cdd2de9bdcdf
dq = 0x230ba63327b3480c4cf80369f10af726baacf61e631b07178d5aa62dc4b9017b30bf28c5ada9486817d71f0587dd23eea5162ff60880eb0cf7f866c695e1b369

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 no es fácil de factorizar. Pero podemos reducir la ecuación anterior :

Y por lo tanto,

Entonces, podemos intentar encontrar y resolviendo el siguiente sistema de ecuaciones:

En realidad, el valor exacto de es o , porque tanto como tienen un tamaño de bits similar en comparación con .

Una vez que tengamos y , podemos 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_H = int(f.readline().split(' = ')[1], 16) << 512
    dq_H = int(f.readline().split(' = ')[1], 16) << 512


A = (e * dp_H - 1) * (e * dq_H - 1) // n + 1
S = (A * (1 - n) + 1) % e

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 :

kp_var, kq_var = var('kp, kq')
assume(kp_var, 'integer')
assume(kq_var, 'integer')

possible_kp_kq = []

while True:
    sols = solve([
        kp_var * kq_var == A,
        kp_var + kq_var == S
    ], kp_var, kq_var, algorithm='sympy')

    if not sols:
        S += e
        continue

    for sol in sols:
        kp, kq = map(int, sol.values())
        possible_kp_kq.append((kp, kq))

    break

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 = (pow(e, -1, kp) - dp_H) % kp
    P = (e * (dp_H + kp * x + d_kp) - 1 + kp).monic()
    roots = P.small_roots(beta=0.5)

    if roots and roots[0] != n:
        dp_L = kp * roots[0] + d_kp
        p = int((e * (dp_H + dp_L) - 1 + kp) // kp)
        assert n % p == 0 and 1 < p < n
        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:

$ python3 solve.py
HTB{4ny_l34k4g3_0f_pr1v4t3_1nf0rm4t10n_r3su1ts_1n_br0k3n_crypt0}

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