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 $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:
$$ A := 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$ no es fácil de factorizar. Pero podemos reducir la ecuación anterior $\mod{e}$:
$$ \begin{align} k_p k_q \cdot n \mod{e} & = \left(-1 + k_p\right) \cdot \left(-1 + k_q\right) \mod{e} \\ k_p k_q \cdot n \mod{e} & = k_p k_q - (k_p + k_q) + 1 \mod{e} \\ k_p + k_q \mod{e} & = k_p k_q (1 - n) + 1 \mod{e} \end{align} $$
Y por lo tanto,
$$ S := k_p + k_q = A \cdot (1 - n) + 1 \mod{e} $$
Entonces, podemos intentar encontrar $k_p$ y $k_q$ resolviendo el siguiente sistema de ecuaciones:
$$ \begin{cases} k_p \cdot k_q & = A \\ k_p + k_q & = S \end{cases} $$
En realidad, el valor exacto de $S$ es $k_p + k_q$ o $k_p + k_q + e$, porque tanto $k_p$ como $k_q$ tienen un tamaño de bits similar en comparación con $e$.
Una vez que tengamos $k_p$ y $k_q$, podemos 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_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 $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$:
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 $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 = (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. 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{4ny_l34k4g3_0f_pr1v4t3_1nf0rm4t10n_r3su1ts_1n_br0k3n_crypt0}
El script completo se puede encontrar aquí: solve.py.