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 $n$, $e$ y $c$ tales que
$$ c = m^e \mod{n} $$
donde $m$ es la flag. CUriosamente, $e$ es un número primo de 227 bits ($1024 / 9$).
El servidor también calcula los exponentes privados para el descifrado de RSA-CRT:
$$ d_p = e^{-1} \mod{p - 1} \qquad d_q = e^{-1} \mod{q - 1} $$
Estos son números de 1024 bits, pero solo nos dan los 512 bits más significativos, digamos $d_p^H$ y $d_q^H$.
Los anteriores $d_p$ y $d_q$ se pueden usar para descifrar la flag usando el Teorema Chino del Resto (CRT):
$$ m_p = c^{d_p} \mod{p} \qquad m_q = c^{d_q} \mod{q} $$
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
$$ \begin{align*} d_p = e^{-1} \mod{p - 1} & \iff e \cdot d_p = k_p (p - 1) + 1 \\ & \iff p = \frac{e \cdot d_p - 1}{k_p} + 1 \end{align*} $$
Por lo que:
$$ p = \frac{e \cdot (d_p^H + d_p^L) - 1}{k_p} + 1 \qquad q = \frac{e \cdot (d_q^H + d_q^L) - 1}{k_q} + 1 $$
Y entonces
$$ k_p k_q \cdot n = \left(e \cdot (d_p^H + d_p^L) - 1 + k_p\right) \cdot \left(e \cdot (d_q^H + d_q^L) - 1 + k_q\right) $$
Podemos obtener una buena aproximación de $k_p k_q$ como:
$$ k_p k_q = \left\lceil\frac{\left(e \cdot d_p^H - 1\right) \cdot \left(e \cdot d_q^H - 1\right)}{n}\right\rceil $$
Este número $k_p k_q$ es fácil de factorizar. Luego, podemos considerar pares de números $k_p$ y $k_q$ e intentar buscar raíces pequeñas del polinomio
$$ P(x) = e \cdot (d_p^H + x) - 1 + k_p \pmod{n} $$
Tenemos que $P(d_p^L) = p$, que es lo que necesitamos, pero esto es difícil de resolver ya que $d_p^L$ sigue siendo bastante grande en comparación con $n$.
Ajustando el polinomio
Podemos reducir el espacio de búsqueda con esta condición:
$$ \begin{align*} k_p \cdot p = e \cdot (d_p^H + d_p^L) - 1 + k_p & \iff e \cdot (d_p^H + d_p^L) - 1 \mod{k_p} = 0 \\ & \iff d_p^L = e^{-1} - d_p^H \mod{k_p} \\ & \iff d_{k_p} := e^{-1} - d_p^H \mod{k_p} \end{align*} $$
Entonces, podemos redefinir el polinomio como
$$ P(x) = e \cdot (d_p^H + k_p \cdot x + d_{k_p}) - 1 + k_p \pmod{n} $$
Y ahora $x$ 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 $k_p k_q$ 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 $k_p k_q$ 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 $d_p^L$ y $d_q^L$:
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 $d_{k_p}$, definimos el polinomio e intentamos encontrar una raíz pequeña. Si existe y no es $n$, entonces tenemos el resultado esperado y podemos calcular $p$. 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.