マスタースパーク
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 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
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
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:
- En
, sabemos que y que es un generador de ; por tanto, - En
, como , entonces también. Y así, después de aplicar , tenemos - En
, sabemos que , por lo que al aplicar , obtenemos - En
, sabemos que , y al aplicar , se tiene
Entonces, al final, los puntos
Por lo tanto, podemos definir
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 T_T
está relacionado con el punto
Como
Además, como
Luego, obsérvese que el T_T
es
Logaritmo discreto
Como resultado, tenemos:
Entonces, ¡podemos completar el reto resolviendo un logaritmo discreto sobre 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
Luego, el servidor toma los factores primos de choice
. Para factores primos que aparecen más de una vez (exponente mayor de cnt
y se comprueba que el factor primo sea menor que prime_list
. Al final, la función verifica que todos los primos en prime_list
sean menores que cnt
sea igual a 1
.
Entonces, vemos que el primo
Donde todos los
Nótese también que 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é
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
Sin embargo,
Implementación
Primero, nos conectamos a la instancia, definimos algunas constantes, enviamos un número primo y obtenemos los puntos
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
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
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
.