Rookie Mistake

8 minutos de lectura

Se nos proporciona el código fuente en Python donde se cifra la flag:

import os
from Crypto.Util.number import bytes_to_long, getPrime
from sympy import *
from secret import flag

flag1 = bytes_to_long(flag[:len(flag)//2] + os.urandom(69))
flag2 = bytes_to_long(flag[len(flag)//2:] + os.urandom(200))  

def genprime():
    p = 2
    while p.bit_length() < 1020:
        p *= getPrime(30)
    while True:
        x = getPrime(16)
        if isprime((p * x) + 1):
            return (p * x) + 1
            break
      
p,q = [genprime() for _ in range(2)]

print("-" * 10 + "RSA PART" + "-" * 10)

e = 0x69420
ct1 = pow(flag1,e,p)

print(f'p: {hex(p)}')
print(f'e: {hex(e)}')
print(f'ct: {hex(ct1)}')

print("-" * 10 + "DH PART" + "-" * 10)

n = p * q
g = 0x69420
ct2 = pow(g, flag2, n)

print(f'n: {hex(n)}')
print(f'g: {hex(g)}')
print(f'ct: {hex(ct2)}')

También tenemos la salida del script:

----------RSA PART----------
p: 0x16498bf7cc48a7465416e0f9ec8034f4030991e73aff9524ef74cc574228e36e6e1944c7686f69f0d1186a69b7aa77d7e954edc8a6932f006786f4648ecc8d4f4d3f6c03d9a1ee9fe61b28b6dd2791a63be581b8811a8ac90a387241ea68b7d36b4a274f64c7a721ad55cfcef23cd14c72542f576e4b507c11c4fa198e80021d484691b
e: 0x69420
ct: 0xa82b37d57b6476fa98f6ee7c278d934bd96c49aa1c5399552d25211230d76cb16ade049572bf631e3849903638d41c884957b9592d0aa072b2bdc3105fe0e3253284f85286ec613966f9cde77ae06e2053dc2254e44ca673b4c76879eff84e5fc32af976c1bfafe147a277d72aad674db749ed8f34d2ebe8189cf12afc9baa17764e4b
----------DH PART----------
n: 0xbe30ccaf896c16f53515e298df25df9158d0a95295c119f0444398b94fae26c0b4cf3a43b120cf0fb657069e0621eb1d2dd832eef3065e80ddbc35854dd4585cc41fd6a5b36339c0d9fcc066272be6818be6a624f75482bbb9c408010ac8c27b20397d870bfcb14e6318097b1601f99e391c9b68c5c586f8da561ff8507be9212713b910b748370ce692c11afa09b74ce80c5f5dd72046415aeed85e1ecedca14abe17ed19ab97729b859120699d9f80dd13f8483773df15b938b8399702a6e846b8728a70f1940d4c6e5835a06a89925eb1ec91a796f270e2d9be1a2c4bee5517109c161f04333d9c0d4034fbbd2dcf69fe734b759a89937f4d8ea0ee6b8385aae14a2cce361
g: 0x69420
ct: 0x65d57a564b8a8667a956705442063392b9b975b8ef869a6dbed04d6e585351f559fe6f5d96823f60b7306740fe2cf5aa81e4a12736d4f0a4826cbc8b4312643af19c75432b4ab222837031851f312df5d707b39bdf2d272f25c1947f3e2943f3592cb0519fee8f4b458021b6b8ee4eabeeae5127d412df4f6a88f66d7cc34c6bb77e0a1440737d0e167f9489f0c7fbfd7f6a5870b4b2865d29b91f6c2b375951e85b1b9f03887d4d3c4a6218111a95021ed1d554c57269e7830c3e7b8e17d13e1fb75ee9f305833d0cb6bfab738572cdbbc8b33b878ad25f78d47d7f449a6c348f5f9f1df3e09f924534a3669b4e69bd0411d154ec756b210691e2efc4a55aa664d938a868f4d

El código divide la flag en dos partes y cifra la primera parte con RSA y la segunda parte se usa para una especie de algoritmo de Diffie-Hellman.

Parte de RSA

Aquí, el programa genera dos números de primos $p$ y $q$ con la siguiente función:

def genprime():
    p = 2
    while p.bit_length() < 1020:
        p *= getPrime(30)
    while True:
        x = getPrime(16)
        if isprime((p * x) + 1):
            return (p * x) + 1
            break
      
p,q = [genprime() for _ in range(2)]

Esta función genera números primos $p$ y $q$, pero podemos ver que $p - 1$ y $q - 1$ son lisos (smooth), lo que significa que son producto de factores pequeños, por lo que se pueden factorizar fácilmente:

$ sage -q
sage: p = 0x16498bf7cc48a7465416e0f9ec8034f4030991e73aff9524ef74cc574228e36e6e1944c7686f69f0d1186a69b7aa77d7e954edc8a6932f006786f4648ecc8d4f4d3f6c03d9a1ee9fe6
....: 1b28b6dd2791a63be581b8811a8ac90a387241ea68b7d36b4a274f64c7a721ad55cfcef23cd14c72542f576e4b507c11c4fa198e80021d484691b
sage: factor(p - 1)
2 * 36209 * 547798523 * 585495871 * 603764827 * 620106793 * 620486891 * 622959187 * 624928979 * 642300709 * 643598621 * 644170013 * 670656013 * 675669877 * 676128059 * 679467623 * 685343431 * 715193489 * 721280123 * 721341683 * 733843933 * 738509881 * 803591153 * 845584237 * 855999569 * 864585809 * 864781919 * 875862569 * 879413083 * 895364923 * 902987851 * 919851767 * 951702877 * 995048801 * 1025446181 * 1030369169 * 1047227333

Sin embargo, el cifrado RSA es incorrecto, porque usa solo $n = p$, y no $n = p \cdot q$:

e = 0x69420
ct1 = pow(flag1,e,p)

print(f'p: {hex(p)}')
print(f'e: {hex(e)}')
print(f'ct: {hex(ct1)}')

Inverso modular

Entonces, para descifrar RSA necesitamos encontrar $d = e^{-1} \mod{\phi(n)}$, pero tenemos $n = p$, por lo que $\phi(p) = p - 1$.

Nótese que $e$ es un número par, al igual que $p - 1$:

sage: factor(e)  
2^5 * 3^3 * 499

Esto significa que $e$ no tiene inverso en módulo $p - 1$, porque comparten un factor común de $2$:

sage: gcd(e, p - 1)  
2

Sin embargo, podemos hacer un simple truco. Sabemos que este es el texto cifrado:

$$ \mathrm{ct}_1 = (F_1)^e \mod{p} $$

Pero tenemos la factorización de $e$, digamos $e = 2^5 \cdot e’ = 32 \cdot e’$, por tanto

$$ \mathrm{ct}_1 = (F_1)^{32 \cdot e'} \mod{p} = \Big((F_1)^{32}\Big)^{e'} \mod{p} $$

Sabemos que $e’$ tiene un inverso en módulo $p - 1$ porque no hay factores comunes. Con esto, podemos calcular $d’ = (e’)^{-1} \mod{p - 1}$, de modo que podamos descifrar RSA parcialmente y encontrar

$$ (F_1)^{32} = (\mathrm{ct}_1)^{d'} \mod{p} $$

sage: e_prime = e // 32
sage: d_prime = pow(e_prime, -1, p - 1)  
sage: F1_32 = pow(ct1, d_prime, p)

Raíz cuadrada modular

En este punto, necesitamos calcular cinco raíces cuadradas modulares para obtener $F_1$. Tenemos suerte porque $p \equiv 3 \pmod{4}$:

sage: p % 4  
3

Como resultado, la raíz cuadrada modular es muy fácil de calcular (no es necesario usar los algoritmos de Tonelly-Shanks o de Cipolla). En realidad, simplemente necesitamos hacer la siguiente operación:

$$ \sqrt{a} \mod{p} = a^{\frac{p + 1}{4}} \mod{p} $$

Esto sucede porque $p \equiv 3 \pmod{4}$, por lo que $p + 1$ es divisible entre $4$. Como resultado, podemos ver que para un residuo cuadrático $a$, tenemos

$$ \Big(a^{\frac{p + 1}{4}}\Big)^2 \equiv a^{\frac{p + 1}{2}} \equiv a^{\frac{p - 1}{2} + 1} \equiv a^{\frac{p - 1}{2}} \cdot a \pmod{p} $$

Pero $a$ es un residuo cuadrático, así que $a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$ debido al símbolo de Legendre. Por tanto:

$$ a \equiv \Big(a^{\frac{p + 1}{4}}\Big)^2 \pmod{p} \iff \sqrt{a} \mod{p} = a^{\frac{p + 1}{4}} \mod{p} $$

En el reto, necesitamos calcular un total de 5 raíces cuadradas modulares, lo que significa que

$$ \begin{align} \sqrt{\sqrt{\sqrt{\sqrt{\sqrt{a}}}}} \mod{p} & = \left(\left(\left(\left(a^{\frac{p + 1}{4}}\right)^{\frac{p + 1}{4}}\right)^{\frac{p + 1}{4}}\right)^{\frac{p + 1}{4}}\right)^{\frac{p + 1}{4}} \mod{p} \\ \\ & = a^{\left(\frac{p + 1}{4}\right)^5} \mod{p} \end{align} $$

Además, obsérvese que podemos tener dos valores (“positivo” y “negativo”):

sage: F1_pos = pow(F1_32, ((p + 1) // 4) ** 5, p)
sage: F1_neg = - pow(F1_32, ((p + 1) // 4) ** 5, p) % p  
sage: pow(F1_pos, 32, p) == F1_32
True
sage: pow(F1_neg, 32, p) == F1_32
True

Ambos resultados son correctos, ahora podemos transformar los números enteros a bytes y encontrar la primera parte de la flag:

sage: from Crypto.Util.number import long_to_bytes
sage: 
sage: long_to_bytes(F1_pos)
b"\x01d\x98\xbf|\xc4\x8ateAm\xc7J\x85\x87\xd7\xd7\xb79\xbaBK\x99\xd9\x1e\x81\xedX@\xaf\x1a\xd7\xb3k`\xd9\xfd\x12\x8em\x9e\xaa'1+\x1bv\t\x0b5\xe0\xac\x16\t\xbe\x87\xd2\x04\x0f\xde\x14zd.y\x08Z\x93\xda\xfd\xd0\x98\xb4\x8fA\x0e\x07N\x8c;\\$\xfe\x1d\xb5\xe1,!\xf0b\xd1U9\xa8:\xe3\xef\xf1X\x16\x07\xb4_\xad\x8a\xf6\x82\x99\xea\x99\x8b\x85L\xe3\xb2l\xe3\xa1E\xb2\xb2j\xca\xad3W\xdcy\xa2\xb7\xda\xdc"  
sage: long_to_bytes(F1_neg)
b'HTB{why_d1d_y0u_m3ss_3v3ryth1ng_up_1ts_n0t_th4t_h4rd\xa6{\xcb\x9c,b\x9cNQI\xd2q}f\x83\xec\xdf\x07\x99Y\xfd\xd20|\x8a\xa0@\xb5\xce\xe4\xfeP\x99F\xc3J^\xee\x98\x1a\xc4\x8f\xde\xdac\x04\x8aA\x8fzA\x90\x88\x93CoU\x0e\xb1\x84\xf4e\x90#\xa81\xcc\x8e?'
sage: 
sage: flag_1 = long_to_bytes(F1_neg)[:-69]
sage: flag_1
b'HTB{why_d1d_y0u_m3ss_3v3ryth1ng_up_1ts_n0t_th4t_h4rd'

Vale la pena mencionar que SageMath ya tiene una función incorporada para calcular raíces cuadradas modulares. Obviamente, el resultado es el mismo:

sage: F1_pos
4201194382473724823946245664476268770218779530267745631798277601475967345630248107533462798803204288137779509787564780504966343462663924226975569401791847021826701859300016252917662627194197632101762089232321707672259836580168886302616280071328841634356403810182532413499230647098791128541962463909881376626892593884
sage: F1_neg
704870176009839943295001005721824489658707968101575547302884245480223451122699901534421255763466589831492608647316303534144245099881861784549081734244119834897278951901021794139800755949365192687382593739705762118319271568111895419695283389845409501392586562162954626526287954893771121659455
sage: Mod(F1_32, p).nth_root(32, all=True)
[4201194382473724823946245664476268770218779530267745631798277601475967345630248107533462798803204288137779509787564780504966343462663924226975569401791847021826701859300016252917662627194197632101762089232321707672259836580168886302616280071328841634356403810182532413499230647098791128541962463909881376626892593884,  
 704870176009839943295001005721824489658707968101575547302884245480223451122699901534421255763466589831492608647316303534144245099881861784549081734244119834897278951901021794139800755949365192687382593739705762118319271568111895419695283389845409501392586562162954626526287954893771121659455]

Parte de Diffie-Hellman

Aquí, el script toma $n = p \cdot q$ y calcula $\mathrm{ct}_2 = g^{F_2} \mod{n}$:

n = p * q
g = 0x69420
ct2 = pow(g, flag2, n)

print(f'n: {hex(n)}')
print(f'g: {hex(g)}')
print(f'ct: {hex(ct2)}')

Problema de logaritmo discreto

Por lo tanto, necesitamos resolver un problema de logaritmo discreto (DLP). Hay que tener en cuenta que tenemos $n$ y $p$, por lo que es trivial encontrar $q$. Además, podemos factorizar $q - 1$ porque es liso:

sage: n = 0xbe30ccaf896c16f53515e298df25df9158d0a95295c119f0444398b94fae26c0b4cf3a43b120cf0fb657069e0621eb1d2dd832eef3065e80ddbc35854dd4585cc41fd6a5b36339c0d9
....: fcc066272be6818be6a624f75482bbb9c408010ac8c27b20397d870bfcb14e6318097b1601f99e391c9b68c5c586f8da561ff8507be9212713b910b748370ce692c11afa09b74ce80c5f5dd7
....: 2046415aeed85e1ecedca14abe17ed19ab97729b859120699d9f80dd13f8483773df15b938b8399702a6e846b8728a70f1940d4c6e5835a06a89925eb1ec91a796f270e2d9be1a2c4bee5517
....: 109c161f04333d9c0d4034fbbd2dcf69fe734b759a89937f4d8ea0ee6b8385aae14a2cce361
sage: g = 0x69420
ct2 = 0x65d57a564b8a8667a956705442063392b9b975b8ef869a6dbed04d6e585351f559fe6f5d96823f60b7306740fe2cf5aa81e4a12736d4f0a4826cbc8b4312643af19c75432b4ab222
....: 837031851f312df5d707b39bdf2d272f25c1947f3e2943f3592cb0519fee8f4b458021b6b8ee4eabeeae5127d412df4f6a88f66d7cc34c6bb77e0a1440737d0e167f9489f0c7fbfd7f6a5870
....: b4b2865d29b91f6c2b375951e85b1b9f03887d4d3c4a6218111a95021ed1d554c57269e7830c3e7b8e17d13e1fb75ee9f305833d0cb6bfab738572cdbbc8b33b878ad25f78d47d7f449a6c34
....: 8f5f9f1df3e09f924534a3669b4e69bd0411d154ec756b210691e2efc4a55aa664d938a868f4d
sage: 
sage: n % p
0
sage: q = n // p
sage: factor(q - 1)
2 * 40063 * 551582609 * 555256837 * 567856451 * 573405799 * 583336199 * 592968841 * 604811437 * 607714537 * 631781797 * 642077581 * 658176689 * 693045383 * 696054091 * 783195877 * 803763223 * 816799999 * 831612053 * 831917677 * 854559229 * 859490563 * 878834741 * 888267077 * 898662421 * 914208679 * 926926393 * 973394783 * 982425319 * 995929153 * 1014167779 * 1021103537 * 1026380813 * 1030635341 * 1059922679 * 1067331847 * 1072990939

El DLP en sí es difícil de resolver. Sin embargo, ¡esta vez no lo es! En este contexto, estamos trabajando en el grupo $\mathbb{Z}_n$, donde $n = p \cdot q$. Como resultado, el orden del grupo es $\phi(n) = \phi(p) \cdot \phi(q) = (p - 1) \cdot (q - 1)$. Y este orden $\phi(n)$ es liso.

El orden de un grupo significa que para cualquier $a \in \mathbb{Z}_n$, se tiene que $a^{\phi(n)} \equiv 1 \mod{n}$. Similarmente, el orden de un elemento es el número entero positivo más pequeño $k$ tal que $a^k \equiv 1 \mod{n}$. En relación con esto, el teorema de Lagrange dice que $k \;|\; \phi(n)$.

Dicho esto, el enfoque que seguiremos es el algoritmo de Pohlig-Hellman, que resuelve un logaritmo discreto en un grupo con un orden liso al resolver logaritmos discretos más pequeños y luego juntar todos los resultados utilizando el teorema chino del resto (CRT).

Algoritmo de Pohlig-Hellman

La idea es la siguiente:

Tomamos un factor primo $k$ de $\phi(n)$
Calculamos $(\mathrm{ct}_2)^{\frac{\phi(n)}{k}} \mod{p}$ y $g^{\frac{\phi(n)}{k}} \mod{p}$
Sabemos que el orden de los resultados anteriores es $k$
Por lo tanto, como $\mathrm{ct}_2 = g^{F_2} \mod{p}$, se cumple que

$$ (\mathrm{ct}_2)^{\frac{\phi(n)}{k}} = (g^{F_2})^{\frac{\phi(n)}{k}} \mod{p} = (g^{\frac{\phi(n)}{k}})^{F_2} \mod{p} $$

$F_2$ se puede escribir como $F_2 = \alpha \cdot k + r$ para ciertos números enteros $\alpha, r$ tal que $0 \leqslant r < k$. Entonces

$$ \begin{align} (\mathrm{ct}_2)^{\frac{\phi(n)}{k}} & = (g^{\frac{\phi(n)}{k}})^{F_2} \mod{p} \\ & = (g^{\frac{\phi(n)}{k}})^{\alpha \cdot k + r} \mod{p} \\ & = (g^{\frac{\phi(n)}{k}})^{\alpha \cdot k} \cdot (g^{\frac{\phi(n)}{k}})^r \mod{p} \\ & = (g^{\phi(n)})^\alpha \cdot (g^{\frac{\phi(n)}{k}})^r \mod{p} \\ & = 1^\alpha \cdot (g^{\frac{\phi(n)}{k}})^r \mod{p} \\ & = (g^{\frac{\phi(n)}{k}})^r \mod{p} \\ \end{align} $$

La conclusión es que podemos encontrar fácilmente $r$ y resolver este DLP más pequeño porque se supone que el factor primo $k$ es pequeño también
En otras palabras, estamos hallando $r = F_2 \mod{k}$

Podemos realizar el procedimiento anterior para todos los factores primos de $\phi(n)$ y obtener un sistema de congruencias:

$$ \begin{cases} F_2 \equiv r_1 \pmod{k_1} \\ F_2 \equiv r_2 \pmod{k_2} \\ \dots \\ F_2 \equiv r_m \pmod{k_m} \\ \end{cases} $$

Y como todos los $k_i$ son factores primos entre sí, podemos usar el CRT para encontrar $F_2 \mod{\prod_i k_i}$, que será igual que $F_2$.

Podemos usar SageMath para implementarlo:

sage: order = (p - 1) * (q - 1)
sage: factors = factor(order)
sage:
sage: Zn = Zmod(n)
sage: g = Zn(g)
sage: ct2 = Zn(ct2)
sage:
sage: dlogs = []
sage: crt_moduli = []
sage:
sage: for prime, exponent in factors:
....:     if int(g) % prime == 0:
....:         continue
....:     k = prime ** exponent
....:     dlog = discrete_log(ct2 ** (order // k), g ** (order // k), ord=k, algorithm='bsgs')  
....:     crt_moduli.append(k)
....:     dlogs.append(dlog)
....:
sage: F2 = crt(dlogs, crt_moduli)

Observe que necesitamos omitir los factores primos de $\phi(n)$ que no son coprimos con la base $g$. Además, estamos especificando el orden $k$ de los elementos en discrete_log, para dejarlo ir más rápido. Además, usamos Baby-step Giant-step, que es suficientemente rápido para grupos de orden pequeño.

Vale la pena mencionar que la función discrete_log incorporada en SageMath ya utiliza el algoritmo de Pohlig-Hellman cuando es posible:

sage: discrete_log(ct2, g, order)
2804476603085107565027707255749331066295103785426224861629602201861680712499854130377652576076102338557402972269310646835886484491716329948655731491481860234974607399319663254766286986177485599417063421968583069450861571804348897620247729058365086491428960261457881020586798485365714478651540371063176262146817288318452782818035727600844973213824528482080917545525357109160391608446961425726431705862033416482182497028540360742130961638707993186618482030415914893938295007102503532179843459346182484919123109958806129275887177866427746552590289190952679504543771881453032958846129549284558335743189694513183  
sage: discrete_log(ct2, g, order) == F2
True

Con esto, hemos encontrado la segunda parte de la flag:

sage: long_to_bytes(F2)
b'_ju5t_us3_pr0p3r_p4r4m3t3rs_f0r_4ny_crypt0syst3m...}\xed\xe3\xe5\x10\xb3\xa0f\x95E\xb8\xc6!\xf4\x881\xb1\xd1\xc9\xef\x12\'\x9a,\x9ba\x18i\x8a\xc9\xcd\t#\x92\xf4%\x8d\xe2\xd4g-1\xf4\x0bM$\x13\xe0\x1cO>y\xb0Y\x07\x12\xa1\xb0\x85\x7f\x9e\xb8\xeav\xf7C\x8ff\xb6\xe9\xf7\xe8R\xa9\xc6o^\xd9\x16\x03\xb4\x93\xf5\xecr}\x9f\xd4*\xf5\\\xa3?F\xa4d\x08\x8d\xe6>\xa8\xe1\x8bJ\x9a\xa4oN\xed3\xe2\xffe\xd6\x14\xcd\xb0\x89;+f\xacf\xa0"\'\xc6\xd0d!\x1f\x16U@(\x84\xb0\xab<s\x98Oimb\xe53,l\x1a\x11\x1c\x8b\xb9\x9c\xf1\x07;|\x94O\x13\x9b\r\x99R\xd7\xfb\xb3\xe1\xff\x99\x03\xb2i\xbb\xdc\xb8\xc1U\xf7\xf8\x03\xe4\xbf1O\x9en\x94\xe3\x92\xc0z\x05J\x17w\xf7\x80\x1f'  
sage: 
sage: flag_2 = long_to_bytes(F2)[:-200]
sage: flag_2
b'_ju5t_us3_pr0p3r_p4r4m3t3rs_f0r_4ny_crypt0syst3m...}'

Flag

Finalmente, podemos unir las dos partes y leer la flag:

sage: flag_1 + flag_2
b'HTB{why_d1d_y0u_m3ss_3v3ryth1ng_up_1ts_n0t_th4t_h4rd_ju5t_us3_pr0p3r_p4r4m3t3rs_f0r_4ny_crypt0syst3m...}'