M0lecon CTF 2022

Organisers played m0leconCTF 2022 last weekend, a 24 hour CTF hosted by pwnthem0le, and managed to grab first place! I didn’t have much time to play with everyone, but I did get nerd sniped into solving this really nice isogeny challenge! Thanks to Drago_1729 for writing the challenge and pwnthem0le for hosting the CTF.

SIDHalf

Challenge

• Author: @Drago_1729
• Solves: 3
• Points: 424

It seems a new isogeny hash function, but maybe it’s not too hard to invert…

with open("flag.txt") as f:
    flag = f.read().strip()

flag = flag.encode()

# Setup SIDH params
lA,eA, lB,eB = 2,91, 3,57
p = lA^eA * lB^eB - 1
F.<i> = GF(p^2, modulus=x^2+1)
E0 = EllipticCurve(F, [1,0])
PA, QA = (lB^eB * G for G in E0.gens())
PB, QB = (lA^eA * G for G in E0.gens())
print(PA, QA, PB, QB)

# Some new isogeny encoding
def encode_byte(val):
    privB = randrange(lB^eB)
    KB = PB + privB*QB
    phiB = E0.isogeny(KB, algorithm="factored")
    EB = phiB.codomain()
    GB, HB = phiB(PA), phiB(QA)

    U = lB^eB * EB.random_element()
    V = lB^eB * EB.random_element()

    G = GB-val*U
    H = HB-val*V

    return ((EB.a4(), EB.a6()), G, H, U, V)


out = []
for b in flag:
    out.append(encode_byte(b))

print(out)

Solution

Isogenies! The challenge is a custom encryption algorithm which starts looking like SIDH but instead hides some secret information within the torsion points. Before discussing the solution, let’s look at what the challenge is doing.

First, generators of Alice and Bob’s torsion groups are computed $E[2^a] = \langle P_A, Q_A \rangle$ and $E[3^b] = \langle P_B, Q_B \rangle$. In SIDH and related schemes, these are public parameters, and in the challenge we are indeed given them.

The beginnging of encode_byte() follows the key exchange protocol SIDH. Bob computes a secret point $K_B = P_B + [x]Q_B$ where $x$ is the random integer denoted privB. In SIDH this value is the private key.

Bob then uses this new point $K_B$ to compute an isogeny. To do this, we consider the subgroup generated by the secret point $\langle K_B \rangle$. This is used as the kernel of some isogeny $\phi: E \rightarrow E_B = E / \langle K_B \rangle$. The degree of the isogeny is the size of the kernel $\ker \phi = \langle K_B \rangle$ which we know is $3^b$.

Explicit computation for the isogeny is done using Velu’s formula, but here we can just rely on Sage to do the heavy lifting (Thanks to the Sage master Lorenz Panny for algorithm=factored).

privB = randrange(lB^eB)
KB = PB + privB*QB
phiB = E0.isogeny(KB, algorithm="factored")
EB = phiB.codomain()

Given the Isogeny generated by $\langle K_B \rangle$, the public key for SIDH is the tuple $(E_B, \phi(P_A), \phi(Q_A))$. In SIDH, the shared secret is found by chaining Alice and Bob’s isogenies to find a shared curve $E_{AB}$ (up to isomorphism), where the j-invariant of the curve is used as the shared secret. The image of the torsion points $(\phi(P_A), \phi(Q_A))$ are required to ensure Alice and Bob agree on their shared secret.

This is where this encryption scheme diverges from SIDH. Rather than sending to Alice the image of the torsion points, the byte to be encrypted is used to create a new point.

First, “generators” of the torsion group for Bob’s new curve are found: $E_B[2^a] = \langle U,V \rangle$ (note these aren’t necessarily generators as they’re just random points with order at most $2^a$. That doesn’t matter here though).

We encrypt the byte $v$ by mixing together the image of the torsion points $(G_B, H_B) = (\phi(P_A), \phi(P_B))$ as

The challenge then gives us the curve $E_B$ and $(G,H,U,V)$. To grab our flag, we must find a way to efficiently recover val from this data.

The first thing to notice is that we are encrypting a byte, so at most we would only have to check $256$ values $G_B \stackrel{?}{=} G + xU$ for some guess $x$. The problem now is, how would we know when we had made the correct guess $x$, as we don’t know the value for $G_B$ itself.

The solution comes from understanding the relationship between pairings and isogenies. A great introduction to this is Luca De Feo’s notes.

In particular, we have that for an isogeny $\phi: E \rightarrow \tilde{E}$ we can compute pairings on each curve, and find that

Where $\hat{\phi}$ is the dual isogeny of $\phi$ such that their composition is the multiplication by $d$ map, where $d$ is the degree of the isogeny: $\phi \circ \hat{\phi} = [d]$.

Similarly, we have that

and it’s in this expression that we have our solution! Let’s go back to the challenge. We know that $G_B = \phi(P_A)$ and $H_B = \phi(Q_A)$. We then know that

This gives us the perfect test for when we have found the correct guess $x$, as the above equality will only hold when $x = v$. We then solve the challenge with a short loop in Sage

bytes_found = []
goal = PA.weil_pairing(QA, lA^eA)^(lB^eB)

# Load in the data from the challenge
# in the form ((a,b), G, H, U, V)
for data_val in data:
    ab, G_data, H_data, U_data, V_data = data_val
    a, b = ab
    EB = EllipticCurve(F, [a,b])
    G, H = EB(G_data), EB(H_data)
    U, V = EB(U_data), EB(V_data)

    # Guess the encrypted byte
    for val in range(256):
        # Reconstruct G_B, H_B and use the 
        # Weil pairing to check when it's correct
        GG = G + val*U
        HH = H + val*V
        if GG.weil_pairing(HH, lA^eA) == goal:
            bytes_found.append(val)
            print(bytes(bytes_found))
            break

Does’t take long to find the flag!

ptm{w31l_p41r1ng_c0mpu73s_53cr37_150g3n13s!!}