Kernel searcher
6 minutes to read
I have a super secret isogeny. Wanna know where your point ends up? Just send me your favourite coordinates.
Challenge contributed by CryptoHack
Challenge files:
We are given a SageMath script that hides the flag under an isogeny and allows us to evaluate the isogeny in any point we desire.
Source code analysis
The relevant part of the script is this one:
import json
from Crypto.Util.number import bytes_to_long
proof.all(False)
A, B = 2**216, 3**137
p = A * B - 1
F.<i> = GF(p^2, modulus=[1,0,1])
E = EllipticCurve(F, [0, 6, 0, 1, 0])
# Torsion Basis for E[A]
P, Q = canonical_torsion_basis(E, A)
import os
flag = os.environ.get("FLAG", "ECSC{fake_flag_for_testing}").strip().encode()
ker = P + bytes_to_long(flag) * Q
challenge_isogeny = E.isogeny(
ker, algorithm="factored", model="montgomery"
)
def accept_point(data):
data = json.loads(data)
try:
x0 = int(data["x0"], 16)
x1 = int(data["x1"], 16)
x = F([x0, x1])
except Exception as e:
print(e)
return {"error": "Invalid Fp2 value"}
if not E.is_x_coord(x):
return {"error": "Invalid Point"}
P = E.lift_x(x)
imP = challenge_isogeny(P)
return json.dumps({"x0": hex(imP[0][0]), "x1": hex(imP[0][1])})
def main():
print(f"Welcome to my isogeny factory!")
print(f"My isogeny is so secret, I'll let you evaluate any point you like!")
while True:
data = input("Send the point you wish to evaluate: ")
output = accept_point(data)
print(output)
if __name__ == "__main__":
main()
Basically, the server uses a given elliptic curve $E$ on $\mathbb{F}_{p^2}$, where $p = 2^{216} \, 3^{137} - 1$.
The elliptic curve is defined as:
$$ E: y^2 = x^3 + 6 x^2 + x \mod{p, i^2 + 1} $$
Notice that $\mathbb{F}_{p^2}$ is a finite field where the elements are polynomials on $i$ of degree $1$. This elliptic curve is supersingular.
Then, the server finds two points $P$ and $Q$ whose order is $2^{216}$. With those points, the server defines the kernel of the isogeny as $P + d \cdot Q$, where $d$ is the flag.
Isogeny
An isogeny is just a homomorphism between two (supersingular) elliptic curves. And the kernel of a homomorphism is the set of elements that are mapped to the identity element.
Let’s denote the isogeny by $\phi$, so we have that $\phi(P + d \cdot Q) = 0$. Since the kernel is defined by a single point, any multiple of that point is in the kernel (including the point at infinity). Therefore, $\phi(k \cdot (P + d \cdot Q)) = 0$ for any $k \in \mathbb{F}_{p^2}$.
Moreover, since $\phi$ is a group homomorphism, it follows that $\phi(P + d \cdot Q) = \phi(P) + d \cdot \phi(Q) = 0$. So, we have
$$ -\phi(P) = d \cdot \phi(Q) $$
Solution
We can obtain $d$ by solving the elliptic curve discrete logarithm problem (ECDLP). The issue here is that we still don’t know the codomain of the isogeny.
Finding curve parameters
After a bit of research and testing, we can see that the codomain is an elliptic curve with the following structure:
$$ EE: y^2 = x^3 + C x^2 + x \mod{p, i^2 + 1} $$
For some $C \in \mathbb{F}_{p^2}$ that depends on $\ker{\phi}$.
We are able to obtain that $C$ value if we know a point of the codomain curve.
Here, I tried some interesting points. For instance, I sent the point $E(0, 0)$ to the server, and the output was a point $EE(X, 0)$. The server only outputs the $\mathrm{x}$ coordinate, but when testing locally, I saw that the $\mathrm{y}$ coordinate was always equal to $0$. Hence, we can solve the codomain curve equation for $C$:
$$ 0^2 = X^3 + C X^2 + X \iff C = \frac{-X^3 - X}{X^2} $$
io = get_process()
io.sendlineafter(b'Send the point you wish to evaluate: ',
json.dumps({'x0': '0', 'x1': '0'}).encode())
data = json.loads(io.recvline().decode())
x0, x1 = int(data.get('x0'), 16), int(data.get('x1'), 16)
X = F([x0, x1])
C = (- X ** 3 - X) / (X ** 2)
EE = EllipticCurve(F, [0, C, 0, 1, 0])
Discrete logarithm
And now we are ready to solve the discrete logarithm with the image points of $P$ and $Q$:
io.sendlineafter(b'Send the point you wish to evaluate: ',
json.dumps({'x0': hex(P[0][0]), 'x1': hex(P[0][1])}).encode())
data = json.loads(io.recvline().decode())
x0, x1 = int(data.get('x0'), 16), int(data.get('x1'), 16)
imP = EE.lift_x(F([x0, x1]))
io.sendlineafter(b'Send the point you wish to evaluate: ',
json.dumps({'x0': hex(Q[0][0]), 'x1': hex(Q[0][1])}).encode())
data = json.loads(io.recvline().decode())
x0, x1 = int(data.get('x0'), 16), int(data.get('x1'), 16)
imQ = EE.lift_x(F([x0, x1]))
io.close()
And this is easy to solve because the order of $P$ and $Q$ is $2^{216}$, a power of $2$. Therefore, the image points have also a power of $2$ as order.
Let’s say $P_i = \phi(P)$ and $Q_i = \phi(Q)$. We want to solve the equation $-P_i = d \cdot Q_i$
Since the order of $P_i$ and $Q_i$ are powers of $2$, we can express $d$ in binary:
$$ -P_i = d \cdot Q_i = (d_0 + 2 d_1 + 2^2 d_2 + \dots + 2^m d_m) \cdot Q_i $$
If we multiply by the order of $Q_i$, we get $0 = 0$, if we divide the order by $2$ and multiply, we have
$$ \begin{align*} 2^{215} \cdot (-P_i) & = 2^{215} \cdot (d_0 + 2 d_1 + 2^2 d_2 + \dots + 2^m d_m) \cdot Q_i \\ & = 2^{215} d_0 \cdot Q_i \end{align*} $$
Now, if $2^{215} \cdot (-P_i)$ is the point at infinity (the zero element), we know that $d_0 = 0$, otherwise, $d_0 = 1$.
After that, we can see that
$$ -P_i - (d_0) \cdot Q_i = (2 d_1 + 2^2 d_2 + \dots + 2^m d_m) \cdot Q_i $$
Now we multiply both sides by $2^{214}$, and we have
$$ \begin{align*} 2^{214} \cdot (-P_i - (d_0) \cdot Q_i) & = 2^{214} \cdot (2 d_1 + 2^2 d_2 + \dots + 2^m d_m) \cdot Q_i \\ & = 2^{215} d_1 \cdot Q_i \end{align*} $$
Again, if $2^{214} \cdot (-P_i - (d_0) \cdot Q_i)$ is zero, then $d_1 = 0$, otherwise $d_1 = 1$.
Then,
$$ -P_i - (d_0 + 2 d_1) \cdot Q_i = (2^2 d_2 + \dots + 2^m d_m) \cdot Q_i $$
And we multiply by $2^{213}$ to determine $d_2$. We continue all the process until we find all bits from $d_0$ to $d_m$:
def dlog(G, nG):
i = -1
bits = []
order = A
while order:
i += 1
order //= 2
if order * (nG - (sum(bits)) * G) != 0 * G:
bits.append(2 ** i)
return sum(bits)
d = dlog(imQ, -imP)
io.success(bytes.fromhex(hex(int(d))[2:]).decode())
Flag
And finally, we find the flag:
$ python3 solve.py
[+] Starting local process '/usr/bin/sage': pid 7514
[*] Stopped process '/usr/bin/sage' (pid 7514)
[+] ECSC{learning_to_isogeny}
The full script can be found in here: solve.py.