マスタースパーク
12 minutos de lectura
Se nos proporciona un script en SageMath llamado challenge.sage:
from Crypto.Util.number import *
import os
from timeout_decorator import timeout, TimeoutError
load("GA.sage")
FLAG = os.getenv("FLAG")
secret = getPrime(256)
choice = set()
@timeout(60)
def T_T(p, primes, secret):
assert isPrime(p)
assert len(primes) > 3
Fp = GF(p)
Fp2.<j> = GF(p ^ 2, modulus=x ^ 2 + 1)
ls = len(factor(p + 1)) - 2
m = ceil((sqrt(p) ** (1 / ls) - 1) / 2)
alice_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
bob_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
EC = montgomery(Fp2, 0)
P = EC.gens()[0]
k = 1
alice_pub, Q = group_action(p, primes, Fp, Fp2, 0, alice_priv, k * P)
share_bob, Q = group_action(p, primes, Fp, Fp2, alice_pub, bob_priv, secret * Q)
bob_pub, P = group_action(p, primes, Fp, Fp2, 0, bob_priv, P)
share_alice, P = group_action(p, primes, Fp, Fp2, bob_pub, alice_priv, P)
return P, Q
def check(p):
assert isPrime(p)
assert p.bit_length() <= 96
assert ((p + 1) // 4) % 2 == 1
prime_list = []
cnt = 0
for p, i in factor((p + 1) // 4):
assert not p in choice
if i > 1:
cnt += 1
choice.add(p)
assert int(p).bit_length() <= 32
else:
prime_list.append(p)
choice.add(p)
assert all([int(p).bit_length() <= 16 for p in prime_list])
assert cnt == 1
return prime_list
def main():
while True:
try:
p = int(input("input your prime number or secret > "))
if int(p).bit_length() == 256:
if p == secret:
print(FLAG)
exit()
print("not flag T_T")
else:
prime_list = check(p)
P, Q = T_T(p, prime_list, secret)
print(P.xy())
print(Q.xy())
except:
print("T_T")
exit()
main()
Además, tenemos GA.sage con algunas funciones utilizadas por el script principal:
from random import randint
# I received advice from Mitsu to write this program. I appreciate it very much
def montgomery(Fp2, A):
return EllipticCurve(Fp2, [0, A, 0, 1, 0])
def to_montgomery(Fp, Fp2, E, G):
Ep = E.change_ring(Fp).short_weierstrass_model()
a, b = Ep.a4(), Ep.a6()
P.<x> = PolynomialRing(Fp)
r = (x^3 + a*x + b).roots()[0][0]
s = sqrt(3 * r^2 + a)
if not is_square(s):
s = -s
A = 3 * r / s
phi = E.isomorphism_to(EllipticCurve(Fp2, [0, A, 0, 1, 0]))
return Fp(A), phi(G)
def group_action(p, primes, Fp, Fp2, pub, priv, G):
E = montgomery(Fp2, pub)
es = priv[:]
while any(es):
x = Fp.random_element()
P = E.lift_x(x)
s = 1 if P[1] in Fp else -1
S = [i for i, e in enumerate(es) if sign(e) == s and e != 0]
k = prod([primes[i] for i in S])
Q = ((p + 1) // k) * P
for i in S:
R = (k // primes[i]) * Q
if R.is_zero():
continue
phi = E.isogeny(R)
E = phi.codomain()
Q, G = phi(Q), phi(G)
es[i] -= s
k //= primes[i]
return to_montgomery(Fp, Fp2, E, G)
Análisis del código fuente
En este reto, se nos permite ingresar números primos, con algunas propiedades, que se utilizarán para un protocolo de intercambio de claves:
def main():
while True:
try:
p = int(input("input your prime number or secret > "))
if int(p).bit_length() == 256:
if p == secret:
print(FLAG)
exit()
print("not flag T_T")
else:
prime_list = check(p)
P, Q = T_T(p, prime_list, secret)
print(P.xy())
print(Q.xy())
except:
print("T_T")
exit()
El protocolo de intercambio de claves se implementa en T_T:
@timeout(60)
def T_T(p, primes, secret):
assert isPrime(p)
assert len(primes) > 3
Fp = GF(p)
Fp2.<j> = GF(p ^ 2, modulus=x ^ 2 + 1)
ls = len(factor(p + 1)) - 2
m = ceil((sqrt(p) ** (1 / ls) - 1) / 2)
alice_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
bob_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
EC = montgomery(Fp2, 0)
P = EC.gens()[0]
k = 1
alice_pub, Q = group_action(p, primes, Fp, Fp2, 0, alice_priv, k * P)
share_bob, Q = group_action(p, primes, Fp, Fp2, alice_pub, bob_priv, secret * Q)
bob_pub, P = group_action(p, primes, Fp, Fp2, 0, bob_priv, P)
share_alice, P = group_action(p, primes, Fp, Fp2, bob_pub, alice_priv, P)
return P, Q
CSIDH
Como se puede ver, se define una curva elíptica sobre $\mathbb{F}_{p^2}$. Específicamente, esta es una curva elíptica supersingular. Luego, el protocolo de intercambio de claves se basa en acciones sobre grupos. Por lo tanto, este es un protocolo CSIDH. De hecho, la función group_action es la misma que se usa en CSIDH:
def group_action(p, primes, Fp, Fp2, pub, priv, G):
E = montgomery(Fp2, pub)
es = priv[:]
while any(es):
x = Fp.random_element()
P = E.lift_x(x)
s = 1 if P[1] in Fp else -1
S = [i for i, e in enumerate(es) if sign(e) == s and e != 0]
k = prod([primes[i] for i in S])
Q = ((p + 1) // k) * P
for i in S:
R = (k // primes[i]) * Q
if R.is_zero():
continue
phi = E.isogeny(R)
E = phi.codomain()
Q, G = phi(Q), phi(G)
es[i] -= s
k //= primes[i]
return to_montgomery(Fp, Fp2, E, G)
Para obtener más información sobre criptografía basada en la isogenias, recomiendo CryptoHack.
En resumen, la clave privada de Alice es una lista de enteros aleatorios entre $-m$ y $m$. El protocolo CSIDH utiliza esta lista para caminar desde una curva elíptica base $E_0$ a otra curva elíptica $E_a$ calculando varias isogenias. Bob hace lo mismo con su clave privada para caminar desde $E_0$ hasta $E_b$. Las claves públicas son el coeficiente de Montgomery de las curvas elípticas $E_a$ y $E_b$. Luego, Alice puede usar su clave privada para caminar desde $E_b$ hasta $E_{ba}$, mientras que Bob usa su clave privada para caminar desde $E_a$ hasta $E_{ab}$. Ambas curvas elípticas finales son las mismas, por lo que el secreto compartido es el coeficiente de Montgomery de las curvas.
He dejado muchos conceptos sin explicar sobre CSIDH e isogenias, pero no los necesitamos para resolver este reto. Solo hay que tener en cuenta que una isogenia es un homomorfismo entre dos curvas elípticas supersingulares.
Solución
Si observamos T_T con detenimiento, vemos que los valores públicos de CSIDH de Alice y Bob no se devuelven de la función:
EC = montgomery(Fp2, 0)
P = EC.gens()[0]
k = 1
alice_pub, Q = group_action(p, primes, Fp, Fp2, 0, alice_priv, k * P)
share_bob, Q = group_action(p, primes, Fp, Fp2, alice_pub, bob_priv, secret * Q)
bob_pub, P = group_action(p, primes, Fp, Fp2, 0, bob_priv, P)
share_alice, P = group_action(p, primes, Fp, Fp2, bob_pub, alice_priv, P)
return P, Q
En cambio, se nos dan dos puntos $P$ y $Q$ que son transformados por las isogenias. Definamos las isogenias:
$$ \phi_a: E_0 \to E_a \qquad \phi_b: E_0 \to E_b $$
Isogenias
Siguiendo el protocolo de intercambio de claves, las líneas anteriores del código SageMath se pueden expresar en términos matemáticos como:
$$ \begin{split} {}^{(1)} \quad & Q \leftarrow \phi_a(k \cdot P) \\ {}^{(2)} \quad & Q \leftarrow \phi_b(\mathrm{secret} \cdot Q) \\ \\ {}^{(3)} \quad & P \leftarrow \phi_b(P) \\ {}^{(4)} \quad & P \leftarrow \phi_a(P) \\ \end{split} $$
- En ${}^{(1)}$, sabemos que $k = 1$ y que $P$ es un generador de $E_0$; por tanto, $Q \in E_a$
- En ${}^{(2)}$, como $Q \in E_a$, entonces $\mathrm{secret} \cdot Q \in E_a$ también. Y así, después de aplicar $\phi_b$, tenemos $Q \in E_{ab}$
- En ${}^{(3)}$, sabemos que $P \in E_0$, por lo que al aplicar $\phi_b$, obtenemos $P \in E_b$
- En ${}^{(4)}$, sabemos que $P \in E_b$, y al aplicar $\phi_a$, se tiene $P \in E_{ab}$
Entonces, al final, los puntos $P$ y $Q$ que nos dan pertenecen a $E_{ab}$.Como resultado, podemos calcular los parámetros de la ecuación de la curva. Específicamente, podemos usar un solo punto para obtener el coeficiente de Montgomery $A$:
$$ P_\mathrm{y}^2 = P_\mathrm{x}^3 + A P_\mathrm{x}^2 + P_\mathrm{x} \iff A = (P_\mathrm{y}^2 - P_\mathrm{x}^3 - P_\mathrm{x}) \cdot (P_\mathrm{x}^2)^{-1} $$
Por lo tanto, podemos definir $E_{ab}$. Ahora, estamos interesados en encontrar $\mathrm {secret}$, que es un valor que necesitamos saber para conseguir la flag:
FLAG = os.getenv("FLAG")
secret = getPrime(256)
# ...
def main():
while True:
try:
p = int(input("input your prime number or secret > "))
if int(p).bit_length() == 256:
if p == secret:
print(FLAG)
exit()
Obsérvese que el valor $Q$ que tenemos de la función T_T está relacionado con el punto $P$ inicial (el generador de $E_0$), podemos etiquetarlo como $P_G$:
$$ Q = \phi_b(\mathrm{secret} \cdot \phi_a(k \cdot P_G)) $$
Como $\phi_a$ y $\phi_b$ son isogenias (homomorfismos entre grupos), la suma de puntos se conserva (y el producto por escalar), por lo tanto
$$ \begin{split} Q & = \phi_b(\mathrm{secret} \cdot \phi_a(k \cdot P_G)) \\ & = \phi_b(\mathrm{secret} \cdot k \cdot \phi_a(P_G)) \\ & = (\mathrm{secret} \cdot k) \cdot \phi_b(\phi_a(P_G)) \\ \end{split} $$
Además, como $k = 1$ lo podemos simplificar a $Q = \mathrm{secret} \cdot \phi_b(\phi_a(P_G))$.
Luego, obsérvese que el $P$ que devuelve T_T es $P = \phi_a(\phi_b(P_G))$. Se parece a la expresión anterior de $Q$, pero el orden de las isogenias se invierte. Sin embargo, estamos hablando de CSIDH, donde la “C” indica la propiedad conmutativa, por lo tanto $\phi_a(\phi_b(P_G)) = \phi_b(\phi_a(P_G))$.
Logaritmo discreto
Como resultado, tenemos:
$$ \begin{cases} P = \phi_a(\phi_b(P_G)) \\ Q = \mathrm{secret} \cdot \phi_b(\phi_a(P_G)) \end{cases} \quad \Longrightarrow Q = \mathrm{secret} \cdot P $$
Entonces, ¡podemos completar el reto resolviendo un logaritmo discreto sobre $E_{ab}$! Este es fácil de resolver porque la curva es supersingular, por lo que el orden de la curva es smooth (tiene muchos factores pequeños). Un algoritmo como Pohlig-Hellman encontrará la solución rápidamente. En SageMath, basta con usar el método log.
Generación de primos
Nos hemos saltado una parte del reto, que tiene que ver con los números primos que podemos enviar al servidor:
def check(p):
assert isPrime(p)
assert p.bit_length() <= 96
assert ((p + 1) // 4) % 2 == 1
prime_list = []
cnt = 0
for p, i in factor((p + 1) // 4):
assert not p in choice
if i > 1:
cnt += 1
choice.add(p)
assert int(p).bit_length() <= 32
else:
prime_list.append(p)
choice.add(p)
assert all([int(p).bit_length() <= 16 for p in prime_list])
assert cnt == 1
return prime_list
Como se puede ver, los primos deben ser $p < 2^{96}$ y también $\frac{p + 1}{4} \mod{2} = 1$. Lo que significa que
$$ \frac{p + 1}{4} = 2 \cdot n + 1 \iff p + 1 = 8 n + 4 \iff p = 8n + 3 $$
Luego, el servidor toma los factores primos de $\frac{p + 1}{4}$ y los agrega a un conjunto llamado choice. Para factores primos que aparecen más de una vez (exponente mayor de $1$), se incrementa un contador cnt y se comprueba que el factor primo sea menor que $2^{32}$. Por otro lado, el factor primo que aparece solo una vez que se añade a prime_list. Al final, la función verifica que todos los primos en prime_list sean menores que $2^{16}$ y que cnt sea igual a 1.
Entonces, vemos que el primo $p$ debe tener la siguiente estructura (un poco más restrictiva que antes):
$$ p = 4 \cdot q_1 \cdot q_2 \cdots q_l \cdot r^e - 1 $$
Donde todos los $q_i$ y $r$ son números primos impares y $e$ es un exponente superior a $1$, de modo que
$$ \frac{p + 1}{4} = q_1 \cdot q_2 \cdots q_l \cdot r^e \equiv 1 \pmod{2} $$
Nótese también que $l > 3$, porque se verifica en T_T:
@timeout(60)
def T_T(p, primes, secret):
assert isPrime(p)
assert len(primes) > 3
# ...
La forma en la que generé estos números primos no es tan interesante, ya que solo usé números primos aleatorios dentro del rango permitido y verifiqué que los factores primos no estuvieran ya en el conjunto choice. También usé $l = 4$ y $e = 2$ por simplicidad:
def gen_prime():
global choice
prev_choice = set(choice)
while True:
p = 4 * prod(random_prime(2 ** 8) for _ in range(4)) * random_prime(2 ** 14) ** 2 - 1
try:
check(p)
return p
except AssertionError:
choice = set(prev_choice)
CRT
Finalmente, podemos enviar un primo conocido y resolver el logaritmo discreto $Q = \mathrm{secret} \cdot P$ en la curva $E_{ab}$, la cual podemos recuperar usando un punto.
Sin embargo, $\mathrm{secret}$ es un número de 256 bits, mientras que los primos que estamos enviando son como mucho números de 96 bits. Por lo tanto, necesitaremos resolver varios logaritmos discretos utilizando diferentes primos. Con todos los resultados intermedios, podemos usar el CRT para unirlos y encontrar el valor $\mathrm{secret}$ (esto es una especie de algoritmo de Pohlig-Hellman).
Implementación
Primero, nos conectamos a la instancia, definimos algunas constantes, enviamos un número primo y obtenemos los puntos $P$ y $Q$:
io = get_process()
dlogs, mods = [], []
for _ in range(8):
p = gen_prime()
Fp = GF(p)
Fp2 = GF(p ** 2, modulus=[1, 0, 1], names='j')
j = Fp2.gens()[0]
io.sendlineafter(b'input your prime number or secret > ', str(p).encode())
io.recvuntil(b'(')
Px = j * int(io.recvuntil(b'*j + ', drop=True).decode()) + int(io.recvuntil(b', ', drop=True).decode())
Py = j * int(io.recvuntil(b'*j + ', drop=True).decode()) + int(io.recvuntil(b')', drop=True).decode())
io.recvuntil(b'(')
Qx = j * int(io.recvuntil(b'*j + ', drop=True).decode()) + int(io.recvuntil(b', ', drop=True).decode())
Qy = j * int(io.recvuntil(b'*j + ', drop=True).decode()) + int(io.recvuntil(b')', drop=True).decode())
Ahora encontramos la curva $E_{ab}$:
A = (Py ** 2 - Px ** 3 - Px) / (Px ** 2)
Eab = EllipticCurve(Fp2, [0, A, 0, 1, 0])
P = Eab(Px, Py)
Q = Eab(Qx, Qy)
Después de eso, podemos resolver el logaritmo discreto y agregar el resultado y el orden para dlogs y mods para su uso posterior con el CRT:
dlogs.append(Q.log(P))
mods.append(P.order())
Este proceso se repite 8 veces, que es suficiente información. En este punto, podemos calcular el CRT. Obsérvese que debemos considerar valores positivos y negativos de los resultados intermedios:
for signs in product((-1, 1), repeat=len(dlogs)):
try:
secret = crt([s * d for s, d in zip(signs, dlogs)], mods)
if secret.bit_length() != 256:
continue
io.info(f'Testing {secret = }')
io.sendlineafter(b'input your prime number or secret > ', str(secret).encode())
if 'not flag T_T' not in (msg := io.recvlineS()):
io.success(msg)
break
except ValueError:
pass
No estoy muy seguro de por qué esto es necesario, pero creo que es porque $\phi_a(\phi_b(P))$ no siempre es lo mismo que $\phi_b(\phi_a(P))$, solo por la diferencia de signo.
Flag
Si ejecutamos el script, obtendremos la flag:
$ python3 solve.py master-spark.chals.sekai.team 1337
[+] Opening connection to master-spark.chals.sekai.team on port 1337: Done
[+] Starting local process '/usr/bin/bash': pid 109
[*] Stopped process '/usr/bin/bash' (pid 109)
[*] Testing secret = 92697392149653184017438929759734443022953789135986999376605724801638735010341
[+] SEKAI{(h0w_4b0u7_70uh0u_pr0j3c7??_OH_WAIT_Help_me,ERINNNNNNNNNNNN!!_https://youtu.be/X8z23t428kU?si=4ufTbouKxwQ6Lbhm}
[*] Closed connection to master-spark.chals.sekai.team port 1337
El script completo se puede encontrar aquí: solve.py.