Composition
8 minutos de lectura
Se nos proporciona el código fuente del servidor en Python:
from Crypto.Util.number import isPrime, getPrime, GCD, long_to_bytes, bytes_to_long
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag
from ecc import EllipticCurve
from hashlib import md5
import os
import random
print("Welcome to the ECRSA test center. Your encrypted data will be sent soon.")
print("Please check the logs for the parameters.")
legendre = lambda x,p: pow(x,(p-1)//2,p)
def next_prime(num):
if num % 2 == 0:
num += 1
else:
num += 2
while not isPrime(num):
num += 2
return num
def getrandpoint(ec,p,q):
num = random.randint(1,p*q)
while legendre(expr(num),p) != 1 or legendre(expr(num),q) != 1:
num = random.randint(1,p*q)
return ec.lift_x(num,p,q)
# Calculate discriminant(ensures elliptic curve is non-singular)
calc_discrim = lambda a,b,n: (-16 * (4 * a**3 + 27 * b**2)) % n
def keygen(bits):
# Returns RSA key in form ((e,n),(p,q))
p = getPrime(bits // 2)
while p % 4 == 1:
p = next_prime(p)
e = next_prime(p >> (bits // 4))
q = next_prime(p)
for i in range(50):
q = next_prime(q)
while q % 4 == 1:
q = next_prime(q)
n = p * q
if n.bit_length() != bits:
return keygen(bits)
return (e,n),(p,q)
print("Generating your key...")
key = keygen(512)
e,n = key[0]
p,q = key[1]
print("Creating ECC params")
# Gotta make sure the params are valid
a,b = random.getrandbits(128),random.getrandbits(128)
discrim = calc_discrim(a,b,n)
expr = lambda x: x**3 + a*x + b
while not discrim:
a,b = random.getrandbits(128),random.getrandbits(128)
discrim = calc_discrim(a,b,n)
ec = EllipticCurve(a,b,n)
g = getrandpoint(ec,p,q)
A = ec.multiply(g,e)
# Use key that has been shared with ECRSA
key = md5(str(g.x).encode()).digest()
iv = os.urandom(16)
cipher = AES.new(key,AES.MODE_CBC,iv)
data = cipher.encrypt(pad(flag,16))
print(f"Encrypted flag: {data.hex()}")
print(f"IV: {iv.hex()}")
print(f"N: {n}")
print(f"ECRSA Ciphertext: {A}")
print("Would you like to test the ECRSA curve?")
if input("[y/n]> ") == 'n':
exit()
print("Generating random point...")
print(getrandpoint(ec,p,q))
print("Thanks for testing!")
Esta cifrando la flag usando ECC, con una librería personalizada (ecc.py):
from collections import namedtuple
from functools import reduce
from operator import mul
from Crypto.Util.number import inverse
import random
Point = namedtuple("Point","x y")
def moddiv(x,y,p):
return (x * inverse(y,p)) % p
def crt(*args):
# Takes a bunch of lists in form [value,modulus]
values = [row[0] for row in args]
ns = [row[1] for row in args]
N = reduce(mul,ns)
_sum = 0
for i in range(len(args)):
yi = N // ns[i]
zi = inverse(yi,ns[i])
_sum += values[i]*yi*zi
return _sum % N
def composite_square_root(num,p,q):
# Only works if num is a quadratic residue mod p and q AND p and q are 3 mod 4
n = p * q
root1 = pow(num,(p+1)//4,p)
root2 = pow(num,(q+1)//4,q)
ans = crt([root1,p],[root2,q])
assert pow(ans,2,n) == (num % n)
return ans
class EllipticCurve:
INF = Point(0,0)
def __init__(self, a, b, p):
self.a = a
self.b = b
self.p = p
def add(self,P,Q):
if P == self.INF:
return Q
elif Q == self.INF:
return P
if P.x == Q.x and P.y == (-Q.y % self.p):
return self.INF
if P != Q:
Lambda = moddiv(Q.y - P.y, Q.x - P.x, self.p)
else:
Lambda = moddiv(3 * P.x**2 + self.a,2 * P.y , self.p)
Rx = (Lambda**2 - P.x - Q.x) % self.p
Ry = (Lambda * (P.x - Rx) - P.y) % self.p
return Point(Rx,Ry)
def multiply(self,P,n):
n %= self.p
if n != abs(n):
ans = self.multiply(P,abs(n))
return Point(ans.x, -ans.y % p)
R = self.INF
while n > 0:
if n % 2 == 1:
R = self.add(R,P)
P = self.add(P,P)
n = n // 2
return R
def lift_x(self,x,p,q):
expr = x**3 + self.a*x + self.b
y = composite_square_root(expr,p,q)
return Point(x,y)
Análisis del código fuente
El servidor crea una clave pública de RSA $(e, n)$, aunque no nos dan $e$:
print("Generating your key...")
key = keygen(512)
e,n = key[0]
p,q = key[1]
# ...
print(f"N: {n}")
RSA
El módulo público $n = p \cdot p$, donde $p$ y $q$ son dos números primos grandes:
def keygen(bits):
# Returns RSA key in form ((e,n),(p,q))
p = getPrime(bits // 2)
while p % 4 == 1:
p = next_prime(p)
e = next_prime(p >> (bits // 4))
q = next_prime(p)
for i in range(50):
q = next_prime(q)
while q % 4 == 1:
q = next_prime(q)
n = p * q
if n.bit_length() != bits:
return keygen(bits)
return (e,n),(p,q)
Como se puede ver, $p$ es un número primo de 256 bits, pero $q$ está bastante cerca de $p$, porque se calcula usando next_prime. Al menos, hay una distancia de 50 números primos entre $p$ y $q$, pero la diferencia sigue siendo corta, por lo que podemos decir
$$ q = p + k $$
Para algún $k \in \mathbb{Z}$ pequeño. Entonces tenemos
$$ n = p \cdot q = p^2 + p \cdot k $$
Como resultado, tenemos una aproximación de $p$ usando la raíz cuadrada:
$$ p \approx \sqrt{n} $$
El resultado no será exactamente $p$, pero podemos usar next_prime hasta que encontremos $q$ (y por tanto también tendremos $p$). El exponente público $e$ depende de $p$, por lo que también tendríamos $e$ en este momento.
ECC
Después de eso, el servidor crea una curva elíptica sobre $\mathbb{Z}/n\mathbb{Z}$ con parámetros aleatorios $a$ y $b$, que no se nos dan:
print("Creating ECC params")
# Gotta make sure the params are valid
a,b = random.getrandbits(128),random.getrandbits(128)
discrim = calc_discrim(a,b,n)
expr = lambda x: x**3 + a*x + b
while not discrim:
a,b = random.getrandbits(128),random.getrandbits(128)
discrim = calc_discrim(a,b,n)
ec = EllipticCurve(a,b,n)
Luego, genera un punto aleatorio $G$, que se utiliza para derivar una clave de AES para cifrar la flag, y se nos da $A = e \cdot G$:
g = getrandpoint(ec,p,q)
A = ec.multiply(g,e)
# Use key that has been shared with ECRSA
key = md5(str(g.x).encode()).digest()
iv = os.urandom(16)
cipher = AES.new(key,AES.MODE_CBC,iv)
data = cipher.encrypt(pad(flag,16))
print(f"Encrypted flag: {data.hex()}")
print(f"IV: {iv.hex()}")
print(f"N: {n}")
print(f"ECRSA Ciphertext: {A}")
Por último, pero no menos importante, tenemos la oportunidad de obtener otro punto aleatorio $R$ dentro de la curva:
print("Would you like to test the ECRSA curve?")
if input("[y/n]> ") == 'n':
exit()
print("Generating random point...")
print(getrandpoint(ec,p,q))
print("Thanks for testing!")
Esto es importante para recuperar los parámetros de la curva, porque tanto $A$ como $R$ se encuentran en la curva, por lo que
$$ \begin{cases} A_y^2 = A_x^3 + a A_x + b \mod{n} \\ R_y^2 = R_y^3 + a R_y + b \mod{n} \end{cases} $$
Restando ambas ecuaciones, tenemos:
$$ A_y^2 - R_y^2 = A_x^3 - R_y^3 + a (A_x - R_y) \mod{n} $$
Entonces, podemos despejar $a$:
$$ a = (A_y^2 - R_y^2 - A_x^3 + R_y^3) \cdot (A_x - R_y)^{-1} \mod{n} $$
Y luego es trivial hallar $b$:
$$ b = A_y^2 - A_x^3 - a A_x \mod{n} $$
Solución
Entonces, hasta este punto, sabemos cómo factorizar $n = p \cdot q$, cómo obtener $e$ y cómo recuperar los parámetros de la curva.
Lo último que necesitamos es encontrar $G$ tal que $A = e \cdot G$. La forma de hacerlo es encontrar un valor $d$ tal que $G = d \cdot A$, por lo que $e$ y $d$ son inversos de algún modo. El problema es que no podemos calcular el orden de la curva porque está definida sobre un módulo compuesto, por lo que no podemos encontrar el inverso de $e$ fácilmente.
Lo que podemos hacer es aplicar el Teorema Chino del Resto de una manera peculiar. Ciertamente, podemos encontrar el inverso de un escalar cuando la curva se define sobre un módulo primo. Como resultado, podemos encontrar el inverso de $e$ en las curvas definidas sobre $\mathbb{F}_p$ y $\mathbb{F}_q$, obtener el punto $G$ en ambas curvas, y luego aplicar el CRT de las coordenadas $\mathrm{x}$ para obtener el punto $G$ sobre $\mathbb{Z}/n\mathbb{Z}$.
Implementación
En primer lugar, obtenemos toda la información necesaria de la instancia de reto:
io = get_process()
io.recvuntil(b'Encrypted flag: ')
flag_enc = bytes.fromhex(io.recvline().strip().decode())
io.recvuntil(b'IV: ')
iv = bytes.fromhex(io.recvline().strip().decode())
io.recvuntil(b'N: ')
n = int(io.recvline().decode())
io.recvuntil(b'ECRSA Ciphertext: Point(x=')
Ax = int(io.recvuntil(b',')[:-1].decode())
io.recvuntil(b'y=')
Ay = int(io.recvuntil(b')')[:-1].decode())
io.sendlineafter(b'[y/n]> ', b'y')
io.recvuntil(b'Point(x=')
Rx = int(io.recvuntil(b',')[:-1].decode())
io.recvuntil(b'y=')
Ry = int(io.recvuntil(b')')[:-1].decode())
Luego, factorizamos $n$ como se explicó anteriormente:
q = isqrt(n)
while n % q != 0:
q = next_prime(q)
p = n // q
io.info(f'{p = }')
io.info(f'{q = }')
En este punto, también tenemos $e$:
e = next_prime(p >> (n.bit_length() // 4))
io.info(f'{e = }')
A continuación, encontramos los parámetros de la curva resolviendo el sistema de ecuaciones:
a = ((pow(Ay, 2, n) - pow(Ax, 3, n) - pow(Ry, 2, n) + pow(Rx, 3, n)) * pow(Ax - Rx, -1, n)) % n
b = (pow(Ay, 2, n) - pow(Ax, 3, n) - a * Ax) % n
io.info(f'{a = }')
io.info(f'{b = }')
Después de eso, podemos definir las curvas sobre $\mathbb{Z}/n\mathbb{Z}$, $\mathbb{F}_p$ y $\mathbb{F}_q$ Para obtener el punto $G$ en las últimas dos curvas y encontrar $G$ sobre la primera usando el CRT:
En = ecc.EllipticCurve(a, b, n)
Ep = EllipticCurve(GF(p), [a, b])
Eq = EllipticCurve(GF(q), [a, b])
Ap = Ep(Ax, Ay)
Aq = Eq(Ax, Ay)
Gp = pow(e, -1, Ep.order()) * Ap
Gq = pow(e, -1, Eq.order()) * Aq
Gn_x = crt([int(Gp.x()]), int(Gq.x()])], [p, q])
assert En.multiply(En.lift_x(Gn_x, p, q), e) == ecc.Point(Ax, Ay)
io.success(f'{Gn_x = }')
En este punto, podemos derivar la clave de AES y obtener la flag:
key = md5(str(Gn_x).encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(flag_enc), AES.block_size).decode()
io.success(flag)
Flag
Si ejecutamos el script, obtendremos la flag:
$ python3 solve.py 94.237.63.83:33306
[+] Opening connection to 94.237.63.83 on port 33306: Done
[*] p = 106858941313638767991828235567490821200125820455933241643545899194829771009579
[*] q = 106858941313638767991828235567490821200125820455933241643545899194829771018591
[*] e = 314030204622581805680811063725039822717
[*] a = 37753997141981190002907126778194883468
[*] b = 37744197496150834695308441384696040008
[+] Gn_x = 4174411158930651296922645398385284926646467052831144880881853434751972793707369366842219778664803546408964829711287940023692621868869243079343630800011414
[+] HTB{Pr1M3_Pr0x1mIty_@nD_C0mP0s1T3_CuRv3?????=>s0_1nS3cUr3!!!}
[*] Closed connection to 94.237.63.83 port 33306
El script completo se puede encontrar aquí: solve.py.