I've heard that pwn challenges nowadays are just 'take this github repo and good luck'. What about crypto?
This is a remote challenge, you can connect with:
nc pwnchall.challs.teamitaly.eu 29000
Author: Lorenzo Demeio <@Devrar>
From the Dockerfile provided we see that the challenge clones the github repository LearningToSQI/SQISign-SageMath and applies a patch. With this, it generates and verifies two signatures, which are provided, for the messages "Good" and "luck" and finally it expects a signature for the message "give me the flag". If the signature is correct it outputs the flag.
For an overview of how SQISign works you can read the blog from Maria Corte-Real Santos and Giacomo Pope, which also describes many aspects of the implementation of the repository used for this challenge.
The patch is very small and modifies two main things:
- It removes the
@cached_functiondecorator, which is used only on two functions in the code.# We don't like optimization # @cached_function def torsion_basis(E, D, canonical=False):
# We don't like optimization # @cached_function def has_order_constants(D):
- It allows isogenies of degree up to
l^3000for the signature (but it still has to be a power ofl).# Allowing isogenies of degree higher then 2^1000, but should be doable also with the original verification
As suggested in the comment this last patch is not really part of the vulnerability, but it allows a faster signature forge.
Instead, analyzing the two functions affected by the cache, we see something interesting in torsion_basis:
# This ensures all random points are deterministically
# generated
if canonical:
set_random_seed(0)If the function is called with canonical=True it sets Sage's random seed to 0! Looking for something similar in the rest of the code, we see that the functions generate_random_point (which sets the seed to a custom value, taken in the range (0, 2000)) and generate_linearly_independent_point.
Now we can search for somewhere in the code where one of this functions is called with canonical=True (or seed != None for generate_random_point). Analyzing the decompression function, used during the signature verification, we see that the function generate_random_point is called with a given seed. Thus, at the end of the first verification the seed will be set deterministically from the output of the first signature (which we have!) and thus the commitment for the second isogeny will only depend on this seed. Indeed the commitment is fully determined by P, Q, x generated at
# Generate a random kernel
# of order T_prime
P, Q = torsion_basis(E0, T_prime)
x = randint(1, T_prime)It is important to notice that this is true only because the decorator @cached_function on torsion_basis is removed, otherwise the points P and Q generated in the commitment with
P, Q = torsion_basis(E0, T_prime)would be the same as in the first signature, thus based on the initial random seed of Sage, which we don't know.
Now we can simulate the first signature verification and generate a new commitment which will be equal to the one used for the second signature.
EA = EllipticCurve(Fp4, EA_coeffs)
E10 = EllipticCurve(Fp4, E10_coeffs)
E1 = EllipticCurve(Fp4, E11_coeffs)
verifier.verify(EA, (E10, S0), b"Good")
P, Q = torsion_basis(E0, T_prime)
x = randint(1, T_prime)
ψ_ker = P + x * Q
Iψ = kernel_to_ideal(ψ_ker, T_prime)
ψ = EllipticCurveIsogenyFactored(E0, ψ_ker, order=T_prime)
assert ψ.codomain() == E1At this point we still don't have the private key for "luck" and
Since the verification allows for isogenies of degree up to
First we compute the ideal corresponding to response function:
ϕ1 = EllipticCurveIsogenyFactored(E1, ϕ1_ker, order=Dc)
E2 = ϕ1.codomain()
E2.set_order((p**2 - 1) ** 2)
ψ1_dual = dual_isogeny(ψ1, ψ1_ker, order=T_prime)
Iϕ1_pullback = kernel_to_ideal(ψ1_dual(ϕ1_ker), Dc)
Iψ1Iϕ1 = Iψ1.intersection(Iϕ1_pullback)Since EquivalentSmoothIdealHeuristic in the repo) on it to obtain an ideal which norm is a power of 2 and the corresponding isogeny
Using the same commitment "give me the flag" to obtain another isogeny
This way we have the isogeny
There is still a problem with
def remove_backtracking(sigma):
sigma_chain = isogeny_into_blocks(sigma, l)
curves = [sigma.domain()]
new_sigmas = []
for j, fac in enumerate(sigma_chain):
for i, curve in enumerate(curves):
if fac.codomain().is_isomorphic(curve):
new_sigmas = new_sigmas[:i] + [curve.isomorphism_to(fac.codomain())]
curves = curves[:i+1] + [new_sigmas[-1].codomain()]
break
else:
curves.append(fac.codomain())
new_sigmas.append(fac)
new_sigma = EllipticCurveHom_composite.from_factors(new_sigmas)
return new_sigmaFinally, we can call compression on the result and obtain the signature S.
-
By obtaining the commitment secrets it is actually possible to compute an ideal with left order
$O_0$ and right order$O_1$ , where$O_1$ is the maximal order corresponding to$E_A$ , but I didn't find an efficient way to do it. -
It should be possible to construct the final isogeny in a simpler way by finding ideals equivalent to
$I_{\phi_1}$ and$I_{\phi_2}$ of norm power of 2 and composing the corresponding isogenies with$\sigma$ without passing trhough$E_0$ . I've tried to do it by callingSigningKLPTon$I_{\phi_1}$ with an ideal equivalent to$I_{\psi_1}$ of prime norm, but it wasn't able to find a solution for the StrongApproximation and was quickly running out of new$\gamma$ .
from sage.schemes.elliptic_curves.hom_composite import EllipticCurveHom_composite
import os
import sys
sys.path.insert(1, "SQISign-SageMath")
from setup import Fp4, E0, p, T_prime, l, f_step_max, e, Dc, O0, T
from ideals import left_isomorphism, pushforward_ideal
from isogenies import torsion_basis, EllipticCurveIsogenyFactored, dual_isogeny
from deuring import kernel_to_ideal, IdealToIsogenyFromKLPT
from KLPT import EquivalentSmoothIdealHeuristic, small_equivalent_ideal, EquivalentPrimeIdealHeuristic, SigningKLPT
from compression import decompression, compression, isogeny_into_blocks
from SQISign import SQISign
z4 = Fp4.gens()[0]
### output ###
EA_coeffs = <EA_coeffs>
E10_coeffs = <E10_coeffs>
S0 = <S0>
E11_coeffs = <E11_coeffs>
S1 = <S1>
EA = EllipticCurve(Fp4, EA_coeffs)
E10 = EllipticCurve(Fp4, E10_coeffs)
E11 = EllipticCurve(Fp4, E11_coeffs)
E1 = E11
S = S1
target = "give me the flag"
prover, verifier = SQISign(), SQISign()
prover.pk = EA
def check_secrets(secrets, E1):
P, Q, x = secrets
P = E0(P)
Q = E0(Q)
ψ_ker = P + x * Q
Iψ = kernel_to_ideal(ψ_ker, T_prime)
assert Iψ.norm() == T_prime, "Iψ has the wrong norm"
ψ = EllipticCurveIsogenyFactored(E0, ψ_ker, order=T_prime)
if ψ.codomain() == E1:
print("FOUND")
print(f"{x = }")
return ψ_ker, ψ, Iψ
# print("Nope")
def compute_phipsi_smooth(msg, ψ_ker, ψ, Iψ, E1):
ϕ_ker = prover.challenge_from_message(E1, msg.encode())
ϕ = EllipticCurveIsogenyFactored(E1, ϕ_ker, order=Dc)
E2 = ϕ.codomain()
E2.set_order((p**2 - 1) ** 2)
# Computing IψIϕ
ψ_dual = dual_isogeny(ψ, ψ_ker, order=T_prime)
Iϕ_pullback = kernel_to_ideal(ψ_dual(ϕ_ker), Dc)
IψIϕ = Iψ.intersection(Iϕ_pullback)
assert IψIϕ.norm() == Iψ.norm() * Iϕ_pullback.norm()
# Reducing IψIϕ
IψIϕ_prime = small_equivalent_ideal(IψIϕ)
IψIϕ_prime, _, _ = EquivalentPrimeIdealHeuristic(IψIϕ_prime)
# Computing an ideal equivalente to IψIϕ of norm power of l
IψIϕ_smooth = EquivalentSmoothIdealHeuristic(IψIϕ_prime, l**800)
print(f"{factor(IψIϕ_smooth.norm()) = }")
I_trivial = O0.unit_ideal()
ϕ_trivial = E0.isogeny(E0(0))
ϕψ_smooth = IdealToIsogenyFromKLPT(
IψIϕ_smooth, I_trivial, ϕ_trivial, I_prime=IψIϕ_prime
)
return ϕψ_smooth, E2
def remove_backtracking(sigma):
sigma_chain = isogeny_into_blocks(sigma, l)
curves = [sigma.domain()]
new_sigmas = []
for j, fac in enumerate(sigma_chain):
if j < len(sigma_chain) - 1:
assert fac.codomain() == sigma_chain[j+1].domain()
for i, curve in enumerate(curves):
if fac.codomain().is_isomorphic(curve):
new_sigmas = new_sigmas[:i] + [curve.isomorphism_to(fac.codomain())]
curves = curves[:i+1] + [new_sigmas[-1].codomain()]
break
else:
curves.append(fac.codomain())
new_sigmas.append(fac)
new_sigma = EllipticCurveHom_composite.from_factors(new_sigmas)
return new_sigma
# Getting the secret commitment
verifier.verify(EA, (E10, S0), b"Good")
P, Q = torsion_basis(E0, T_prime)
x = randint(1, T_prime)
secrets = (P, Q, x)
hope = check_secrets(secrets, E1)
if hope:
ψ_ker, ψ, Iψ = hope
else:
print("Secrets not found :(")
exit()
print("\nComputing given_phipsi_smooth")
if not os.path.isfile("dumps/given_phipsi_smooth") or (len(sys.argv) > 1 and sys.argv[1] == "new"):
given_ϕψ_smooth, E2_given = compute_phipsi_smooth("luck", ψ_ker, ψ, Iψ, E1)
with open("dumps/given_phipsi_smooth", "wb") as f:
f.write(dumps((given_ϕψ_smooth, E2_given)))
else:
with open("dumps/given_phipsi_smooth", "rb") as f:
given_ϕψ_smooth, E2_given = loads(f.read())
print("Done")
print("\nComputing target_phipsi_smooth")
if not os.path.isfile("dumps/target_phipsi_smooth") or (len(sys.argv) > 1 and sys.argv[1] == "new"):
target_ϕψ_smooth, E2_target = compute_phipsi_smooth(target, ψ_ker, ψ, Iψ, E1)
with open("dumps/target_phipsi_smooth", "wb") as f:
f.write(dumps((target_ϕψ_smooth, E2_target)))
else:
with open("dumps/target_phipsi_smooth", "rb") as f:
target_ϕψ_smooth, E2_target = loads(f.read())
print("Done")
σ = decompression(EA, E2_given, S, l, f_step_max, e)
# redefining the dual function to deal with isogenies of degree 1
def my_dual(phi):
if is_prime(phi.degree()):
return phi.dual()
else:
return EllipticCurveHom_composite.from_factors([my_dual(x) if x.degree() > 1 else x.codomain().isomorphism_to(x.domain()) for x in phi.factors()[::-1]])
print()
print("Computing composition of isogenies")
if not os.path.isfile("dumps/phi_EA_E0"):
iso = σ.codomain().isomorphism_to(given_ϕψ_smooth.codomain())
phi_EA_E0 = my_dual(given_ϕψ_smooth) * iso * σ
with open("dumps/phi_EA_E0", "wb") as f:
f.write(dumps(phi_EA_E0))
else:
with open("dumps/phi_EA_E0", "rb") as f:
phi_EA_E0 = loads(f.read())
print("Done")
print()
print("Computing final isogeny")
if not os.path.isfile("dumps/final_sigma"):
final_sigma = target_ϕψ_smooth * phi_EA_E0
final_sigma = remove_backtracking(final_sigma)
with open("dumps/final_sigma", "wb") as f:
f.write(dumps(final_sigma))
else:
with open("dumps/final_sigma", "rb") as f:
final_sigma = loads(f.read())
print("Done")
print(f"{factor(final_sigma.degree()) = }")
deg_sigma = factor(final_sigma.degree())[0][1]
print(f"{deg_sigma = }")
if not os.path.isfile("dumps/final_S"):
final_S = compression(EA, final_sigma, l, f_step_max)
with open("dumps/final_S", "w") as f:
f.write(final_S)
else:
with open("dumps/final_S", "r") as f:
final_S = f.read()
print(f"{final_S = }")
ϕ_ker = prover.challenge_from_message(E1, target.encode())
assert verifier.verify_response(EA, E1, final_S, ϕ_ker, deg_sigma=deg_sigma)