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 y 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 y , pero podemos ver que y 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 , y no :

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 , pero tenemos , por lo que .

Nótese que es un número par, al igual que :

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

Esto significa que no tiene inverso en módulo , porque comparten un factor común de :

sage: gcd(e, p - 1)
2

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

Pero tenemos la factorización de , digamos , por tanto

Sabemos que tiene un inverso en módulo porque no hay factores comunes. Con esto, podemos calcular , de modo que podamos descifrar RSA parcialmente y encontrar

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 . Tenemos suerte porque :

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:

Esto sucede porque , por lo que es divisible entre . Como resultado, podemos ver que para un residuo cuadrático , tenemos

Pero es un residuo cuadrático, así que debido al símbolo de Legendre. Por tanto:

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

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 y calcula :

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 y , por lo que es trivial encontrar . Además, podemos factorizar 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 , donde . Como resultado, el orden del grupo es . Y este orden es liso.

El orden de un grupo significa que para cualquier , se tiene que . Similarmente, el orden de un elemento es el número entero positivo más pequeño tal que . En relación con esto, el teorema de Lagrange dice que .

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 de
Calculamos y
Sabemos que el orden de los resultados anteriores es
Por lo tanto, como , se cumple que

se puede escribir como para ciertos números enteros tal que . Entonces

La conclusión es que podemos encontrar fácilmente y resolver este DLP más pequeño porque se supone que el factor primo es pequeño también
En otras palabras, estamos hallando

Podemos realizar el procedimiento anterior para todos los factores primos de y obtener un sistema de congruencias:

Y como todos los son factores primos entre sí, podemos usar el CRT para encontrar , que será igual que .

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 que no son coprimos con la base . Además, estamos especificando el orden 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...}'