Este blog es solo para fines educativos y de análisis técnico en CTFs. No promueve actividades maliciosas ni el uso indebido de herramientas descritas.
Entrada

LowkeyRSA - L3AK2025

Reto basado en romper un esquema RSA custom mediante un Wiener attack

LowkeyRSA - L3AK2025

Autor del reto: Black, White, Suvoni

Dificultad: Media

Enunciado

“This RSA might lowkey be insecure, no cap fr fr.”

Archivos

En este reto, tenemos el siguiente archivo.

  • chall.py: Contiene el script principal de cifrado.

Archivos utilizados aquí.

Analizando el reto

Si abrimos el archivo chall.py encontramos lo siguiente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *

def gen_primes(SIZE):
    p = random_prime(1 << (SIZE - 1), 1 << SIZE)
    while True:
        q = random_prime(1 << (SIZE - 1), 1 << SIZE)
        if p < q: 
            p, q = q, p
            if q < p < 2*q:
                break
    return p, q

nbits = 1024
flag = b"L3AK{<REDACTED>}"

R = RealField(nbits)
p, q = gen_primes(nbits//2)
N = p*q
phi = (p**4-1)*(q**4-1)
N_s = R(N**2)
N_ss = R(N**4)   
t = (2*N_ss-49*N_s + 2)/(4*N+170*N_s)

while True:
    d = randint(1, round(sqrt(t)) - 1)
    if gcd(phi-d, phi) == 1:
        break

e = inverse_mod(phi-d, phi)
c = pow(bytes_to_long(flag), e, N)
print(f"e = {e}\nN = {N}\nc = {c}")

'''
e = 370641246943654763647982436393968410523035056803076571952063446221981054741105804986870907803130391736840420704227524827167178043545763070520011423497365360567040835216714988776285676818833967899487393611410406708467049153990487431775151667103817558875154145780446157545062795321820537740212495675608976163877567007753523774447008611976905578477758365862741282887079873779055623972564793977884741350325450634869927603664722967323341473363320613467433998603537242156610765948379449307405122629600556105209482040761323271134932553579828576227233549741862990693111061962892676568398083446001891012661453694340879845386900986024512140441823076068075531089610607812090402852586184229193699718454197060072575595570232588935191272416546819793045623275550409871218062357273309812154110783534714662063322116568964675372602159108306251453500390105034890229052958512010283429459687714879084097494098542745605324460172680461006303552579466987732938596341830436505942616479890554056163452471835707573885837976471753073413505028206370632139586750855217201926605743452826397576584492732225029497982216694648573014796836126574081158869231364821712046050068243878660143909750030922147254462228826952501087389154612318844202411291844150163167021
N = 10222014062768125922601962004686361136447658578111413896046596746110249358112354000488449664371774177977274016313103826803116662735101208575040021998413602496525815373151213550295992813258424882626853824039678993334143891154760939712139640336395595628492284893024078520796288685014103193630287988814952604029
c = 4323184196594280140760873888779221921406692838206184372853784052006066772207175604399047711017170078453742445880600303200397632746051500194774569530024097959399922254605516672962219900174336028512116159752401576376530557036245218800162889461620882177398454137759956927838320086276276377067055171421259852996
'''

En este reto, se cifra la bandera flag con una clave pública e y un módulo N, pero la forma en que e puede ser explotada si entendemos bien la estructura del phi(N) modificado.

Si analizamos en detalle el código podemos desglosar el siguiente funcionamiento.

  1. Se generan los primos siguiendo una relación especial.
    • Se genera dos primos p y q de 512 bits cada uno (nbits // 2).
    • Se asegura que los primos tengan una relación específica \(q<p<2q\)
  2. Construcción del módulo y phi (no estándar).
1
2
N = p * q
phi = (p**4 - 1)*(q**4 - 1)
  • Aquí, phi no es el clásico $(p-1)(q-1)$, sino un valor más extraño:
\[\phi = (p^4 - 1)(q^4 - 1)\]
  • Esto es claramente una modificación artificial del RSA tradicional.
  • Si se reconstruyen los primos $p, q$ podemos computar $\phi$, lo cual permite calcular la clave privada.
  1. Se define el valor de t y la generación de d.
1
2
3
4
5
6
7
8
N_s = R(N**2)
N_ss = R(N**4)
t = (2*N_ss-49*N_s + 2)/(4*N+170*N_s)

while True:
    d = randint(1, round(sqrt(t)) - 1)
    if gcd(phi-d, phi) == 1:
        break
  • Se computa un número real t a partir de $N$, y luego se escoge un valor d < \sqrt{t}.
  • Aquí, d es la clave privada y contienen propiedades controladas.
  • Se garantiza que $\gcd(\phi - d, \phi) = 1$ para que el siguiente paso funcione.
  1. Cálculo del exponente público e.
1
e = inverse_mod(phi - d, phi)
  • Esta es la parte rara e interesante:
  • En lugar de usar $d = e^{-1} \mod \phi$ como en RSA normal,
  • se usa: $e = (\phi - d)^{-1} \mod \phi$
  • Esto permite reconstruir $d = \phi - e^{-1} \mod \phi$, si conoces phi.
  1. Por último, se cifra la flag siguiendo el esquema básico de RSA $c = m^e \mod N$

Solver

Según lo descrito anteriormente, sabemos la siguiente información:

  1. El valor phi está basado en $p^4$ y $q^4$, no en $(p-1)(q-1)$, lo cual rompe cualquier esquema de seguridad estándar.
  2. El exponente público e está vinculado a un valor d muy pequeño (elegido menor que $\sqrt{t}$).
  3. La condición $q < p < 2q$ puede facilitar ataques de factorización de $N$.

En este caso, la resolución de este reto viene dada por aplicar un Wiener attack custom.

El ataque de Wiener es un ataque clásico contra RSA cuando el exponente privado $d$ es demasiado pequeño, concretamente:

Si $d < \frac{1}{3}N^{1/4}$, el ataque de Wiener puede recuperar $d$ a partir de $e$ y $N$ usando fracciones continuas.

Esto funciona ya que si $e$ y $d$ son inversos módulo $\phi(N)$, entonces:

\[\frac{e}{\phi(N)} \approx \frac{k}{d}\]

para algún pequeño $k$. Así que al computar los convergentes de la fracción continua de $\frac{e}{N}$, puedes encontrar el par $(k, d)$.

En este caso, tenemos un esquema RSA custom en el que:

1
e = inverse_mod(phi - d, phi)

Esto implica:

\[e \cdot (\phi - d) \equiv 1 \mod \phi \quad \Rightarrow \quad e(\phi - d) = 1 + k\phi\]

Despejando podemos obtener:

\[\frac{e}{\phi} \approx \frac{k}{\phi - d}\]

Por ende:

\[\frac{e}{\phi} \approx \frac{k}{\phi - d} \Rightarrow \frac{e}{\phi - d} \approx \frac{k}{\phi}\]

Pero como no tenemos el valor de $\phi$, entonces se recurre a un valor estimado de $\phi$.

El script solución es el siguiente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from Crypto.Util.number import *

e = 370641246943654763647982436393968410523035056803076571952063446221981054741105804986870907803130391736840420704227524827167178043545763070520011423497365360567040835216714988776285676818833967899487393611410406708467049153990487431775151667103817558875154145780446157545062795321820537740212495675608976163877567007753523774447008611976905578477758365862741282887079873779055623972564793977884741350325450634869927603664722967323341473363320613467433998603537242156610765948379449307405122629600556105209482040761323271134932553579828576227233549741862990693111061962892676568398083446001891012661453694340879845386900986024512140441823076068075531089610607812090402852586184229193699718454197060072575595570232588935191272416546819793045623275550409871218062357273309812154110783534714662063322116568964675372602159108306251453500390105034890229052958512010283429459687714879084097494098542745605324460172680461006303552579466987732938596341830436505942616479890554056163452471835707573885837976471753073413505028206370632139586750855217201926605743452826397576584492732225029497982216694648573014796836126574081158869231364821712046050068243878660143909750030922147254462228826952501087389154612318844202411291844150163167021
N = 10222014062768125922601962004686361136447658578111413896046596746110249358112354000488449664371774177977274016313103826803116662735101208575040021998413602496525815373151213550295992813258424882626853824039678993334143891154760939712139640336395595628492284893024078520796288685014103193630287988814952604029
c = 4323184196594280140760873888779221921406692838206184372853784052006066772207175604399047711017170078453742445880600303200397632746051500194774569530024097959399922254605516672962219900174336028512116159752401576376530557036245218800162889461620882177398454137759956927838320086276276377067055171421259852996

def expansion(nominator, denominator):
    a = []
    residue = nominator % denominator
    a.append(nominator // denominator)
    while residue != 0:
        nominator = denominator
        denominator = residue
        residue = nominator % denominator
        a.append(nominator // denominator)
 
    return a
 
def convergents(a):
    nominators = []
    denominators = []
 
    for i in range(len(a)):
        if i == 0:
            nominators.append(a[i])
            denominators.append(1)
        elif i == 1:
            nominators.append(1 + a[i] * a[i - 1])
            denominators.append(a[i])
        else:
            nominators.append(nominators[i - 2] + a[i] * nominators[i - 1])
            denominators.append(denominators[i - 2] + a[i] * denominators[i - 1])
 
    return nominators, denominators

R = RealField(1024)
N_s = R(N**2)
N_ss = R(N**4)
t = (2*N_ss - 49*N_s + 2) / (4*N + 170*N_s)

a = expansion(e, N**4)
ks, ds = convergents(a)

for i in range(len(ks)):
    if ds[i] < t and ds[i] > 0:
        try:
            phi = (ds[i] * e + 1) / ks[i]
            flag =pow(c, phi - ds[i], N)
        except:
            continue

flag = long_to_bytes(flag)
print(f"[+] Flag: {flag}")

Flag

L3AK{L0wK3y_Th1S_RSA_i5_kiNda_ScuFf3D_LmA0}'

Esta entrada está licenciada bajo CC BY 4.0 por el autor.