In KalmarCTF 2024, there was a hard unsolved challenge called “Shipwrecked Lattices”, authored by jo_k_er (Jonathan). In the end, I spent ~16 hours on it and was the first person to solve it (post-contest). There was one hint released post-contest (but pre-solve) which pulled me out of a deep rabbit hole. It can be found below Problem Statement.

At first galnce, it is just a challenge related to a mysterious group action and quaternions, but upon studying it carefully, one sees that it is closely related to isogeny theory of supersingular elliptic curves. In this post, we will go through how to solve the challenge itself without too much explanation into the theory itself - that will have to wait for the next posts. This post will build on the material introduced in the previous three posts (SIDH 1, SIDH 2, CSIDH*) to solve this challenge.

In this post, for a quaternion ideal \(I\) we write \(\mathcal{O}_L(I)\) and \(\mathcal{O}_R(I)\) to be its left and right order The meaning of (ring) “order” is completely different from the meaning of group order or element order. You can think of it as a subring of the larger quaternion algebra. , respectively. Also, given a quaternion order \(\mathcal{O}\), we write \(I(\mathcal{O})\) for its unit ideal. The precise definitions for these terms can be found in Voight, Chapter 10 or my next post.

As always, we won’t pay too much attention into details like “up to isomorphism” and “ideal classes vs ideals”.

Author’s writeup can be found at his blog. A brief writeup by myself can be found at this Gist.

Some Thoughts

I truly believe this challenge, along with not-csidh by yx7 (Lorenz), are the two peaks of my 3 years of CTF journey thusfar. These two challenges pushed me through a ton of pressure and obstacles, but in the end the experience is 100% worth it. I gained so much knowledge in so little time just by feeling miserable and Googling around (especially under time pressure), without a CTF environment or at least someone pushing me, it is hard to replicate this level of learning. In the end, I am very very proud that I solved the two challenges, not-csidh with Rémy’s help and this with just a small hint. Thanks to both problem authors 💖

Problem Statement

We are given a challenge Sage file and an output file. The Sage file contains two main blobs of code:

1. A Diffie-Hellman exchange based on the GroupAction

from ... import invariant, encrypt_flag

p = next_prime(2**512)
B = QuaternionAlgebra(-1, -p)
i, j, k = B.gens()
O0 = B.maximal_order()

omega = 820*i + 362*j + 153*k
d = -ZZ(omega**2)

assert is_prime(d)
assert omega in O0
assert (1 + omega)/2 not in O0

O0_oriented = (O0, omega)

ells = [ell for ell in Primes()[:150] if kronecker(-d, ell) == 1]
gens = [ZZ(mod(-d, ell).sqrt()) for ell in ells]

alice_secret = [randint(-3, 3) for _ in range(len(ells))]
bob_secret = [randint(-3, 3) for _ in range(len(ells))]

O_A = GroupAction(O0_oriented, alice_secret, ells, gens)
O_B = GroupAction(O0_oriented, bob_secret, ells, gens)

assert O_A[1] in O_A[0]
assert O_B[1] in O_B[0]

print("Alice's public key:")
print(f"O_A = {O_A[0].basis()}\nomega_a = {O_A[1]}")
print("\n\nBob's public key:")
print(f"O_B = {O_B[0].basis()}\nomega_b = {O_B[1]}")

O_BA = GroupAction(O_B, alice_secret, ells, gens)
O_AB = GroupAction(O_A, bob_secret, ells, gens)

assert invariant(O_BA[0]) == invariant(O_BA[0])

shared_secret = invariant(O_BA[0])
iv, ct = encrypt_flag(shared_secret)
print(f"\n\nEncrypted flag: iv = {iv}, ct = {ct}")

2. A GroupAction function

from ... import reduceHeight

def GroupAction(O_oriented, es_in, ells, gens):
    O, omega = O_oriented

    es = es_in.copy()
    O_i = O
    while not all([e == 0 for e in es]):
        frak_l = O_i*1
        for i in range(len(es)):
            if es[i] != 0:
                if es[i] > 0:
                    gen = (gens[i] + omega)
                    es[i] -= 1
                else:
                    gen = (gens[i] - omega)
                    es[i] += 1
                frak_l = frak_l.intersection(O_i*gen + O_i*ells[i])

        O_i = frak_l.right_order()

        O_i, beta = reduceHeight(O_i)
        omega = beta*omega*beta^(-1)

    return O_i, omega

Hint

After the competition, there was a bounty on first blood for this problem. A hint was given:

All isogeny based cryptosystems break when you leak the endomorphism ring, but not necessarily because of KLPT.

As you can guess, this hint was targetted to me, as I was banging my head trying to figure out why KLPT wasn’t working - I was trying to use KLPT to recover a smooth norm ideal, from which I can read off the norm for the secret exponent. There’s approximately 20 reasons why this won’t work, but I will defer this self-deprecation process to the next post. But hey, at least I know what KLPT does now.

Initial Analysis

Let us first analyse the input and output of the function.

Input:

• An oriented quaternion order \((\mathcal{O}, \omega)\) with \(\omega^2 + d = 0\),
• A list of \(75\) Elkies primes \(\ell_i\) such that \(\left(\frac{-d}{\ell_i}\right) = 1\),
• A list of \(75\) generators \(g_i\) such that \(g_i^2 + d \equiv 0 \pmod{\ell_i}\),
• A secret vector \(\vec{s} \in [-3, 3]^{75}\).

Output:

• An oriented quaternion order \((\mathcal{O}’, \omega’)\) still with \(\omega’^2 + d = 0\).

Just from the inputs and outputs, we see the close connection between this and CSIDH. In fact, the line frak_l = frak_l.intersection(O_i*gen + O_i*ells[i]) should set off alarms immediately as the derivation of the CSIDH action by Elkies primes. For now, let’s pretend that \(\omega’ = \omega\) is unchanged throughout the algorithm, and see how we can make the correspondence between CSIDH and the provided GroupAction precise. Below, we write \([\star]\) to indicate a group action, not a plain group multiplication.

Recall that in the setting of CSIDH, we have an imaginary quadratic order \(\mathcal{O} = \mathbb{Z}[\sqrt{-p}]\), and the ideal class group \(\mathrm{Cl}(\mathcal{O})\) acts on supersingular elliptic curves \(E\) with \(\mathcal{O}\) as their \(\mathbb{F}_p\)-endomorphism ring, where \(\pi = \sqrt{-p}\) is fixed, which also means \(\mathcal{O} = \mathbb{Z}[\pi]\). We then take Elkies primes \(\ell_i\) such that \(\pi^2 \equiv 1 \pmod{\ell_i}\). This is because Elkies primes split nicely in \(\mathcal{O}\) - we have \(\ell_i\mathcal{O} = \mathfrak{l}_i\overline{\mathfrak{l}_i}\), where \(\mathfrak{l}_i = \langle \ell, \pi + 1 \rangle\) and \(\overline{\mathfrak{l}_i} = \langle \ell, \pi - 1 \rangle\) are prime ideals whose action on \(E\) is easy to compute - it is a low degree isogeny. From there, we proceed as usual according to group action-based Diffie-Hellman, and the result of the group action is \(\underbrace{\left[\prod_i \mathfrak{l}_i^{\vec{s}_i}\right]}_{\subseteq \mathbb{Z}[\sqrt{-p}]} E_0\).

From the inputs and outputs, we can guess which part of CSIDH match up with what in GroupAction already. For example, in our case we have \(\mathcal{O}_0 = \mathbb{Z}[\sqrt{-d}] = \mathbb{Z}[\omega]\), where some group (presumably also a class group) acts on oriented quaternion orders \((\mathcal{O}, \omega)\) with \(\mathcal{O}_0\) as their orientation. We then take Elkies primes \(\ell_i\) and generators \(g_i\) such that \(g_i^2 \equiv -d \pmod{\ell_i}\). This is because Elkies primes split nicely in \(\mathcal{O}_0\) - we have \(\ell_i\mathcal{O}_0 = \mathfrak{l}_i\overline{\mathfrak{l}_i}\), where \(\mathfrak{l}_i = \langle \ell, \omega + g_i \rangle\) and \(\overline{\mathfrak{l}_i} = \langle \ell, \omega - g_i \rangle\) are prime ideals whose action on \(E\) is easy to compute - it is an order intersection. From there, we proceed as usual according to group action-based Diffie-Hellman, and the result of the group action is Might not be entirely accurate, especially concerning the exponent, but whatever. \(\mathcal{O}_R\left(\underbrace{\left[\prod_i \mathfrak{l}_i^{\vec{s}_i}\right]}_{\subseteq \mathbb{Z}[\sqrt{-d}]} I(\mathcal{O})\right)\).

Hence, we have identified a connection between the CSIDH group action and the provided quaternion group action.

Theorising Attack Directions

But wait… isn’t that a bad thing? I mean, as far as we know, CSIDH is secure, so this should imply that the given quaternion group action is secure too. This means there must be something special about the oriented quaternion orders that is not applicable to supersingular elliptic curves! Let’s look at the result of the group action again.

For CSIDH, the ideal class group acts on elliptic curves, sending \(E_0 \mapsto E_1 \coloneqq \left[\prod_i \mathfrak{l}_i^{\vec{s}_i}\right]E_0\). The reason why this is secure is because from an attacker perspective, all you are given is \((E_0, E_1, E_2) = (E_0, [\mathfrak{a}]E_0, [\mathfrak{b}]E_0)\), and would like to compute \([\mathfrak{a}\mathfrak{b}]E_0\). Is this possible? No, this is a hard problem for isogenies.

What about our quaternion group action? Similar to CSIDH, we also have a group action acting on oriented quaternion orders, sending \((\mathcal{O}, \omega) \mapsto \left(\mathcal{O}_A \coloneqq \mathcal{O}_R\left([\mathfrak{a}] I(\mathcal{O})\right), \omega\right)\). As an attacker, now we are given \((\mathcal{O}, \mathcal{O}_A, \mathcal{O}_B) = (\mathcal{O}, \mathcal{O}_R([\mathfrak{a}]I(\mathcal{O})), \mathcal{O}_R([\mathfrak{b}]I(\mathcal{O})))\). From here, it is possible to recover \([\mathfrak{a}]\) and \([\mathfrak{b}]\) directly. However, to understand this, we must study the quaternion group action closer.

Quaternion Group Action

In our Initial Analysis, we understood the majority of the problem by simply comparing it with CSIDH and performing pattern matching. However, this is not sufficient, both for our curiosity and for getting the flag. In particular, we want to understand how the group action \([\mathfrak{a}]I\) works, for a imaginary quadratic ideal \(\mathfrak{a} \subseteq \mathbb{Z}[\sqrt{-d}]\) and a quaternion ideal \(I \subseteq \mathcal{O}\) works. Fortunately, we can refer back to the code for answers.

The following line is the key (again):

# gen = gens[i] ± omega
frak_l = frak_l.intersection(O_i*gen + O_i*ells[i])

As we can see, for a imaginary quadratic ideal \(\mathfrak{a} = \langle \ell_i, \omega \pm g_i \rangle\), we would have \([\mathfrak{a}]I = I \cap {\color{gold} (\mathcal{O} \cdot (\omega + g_i) + \mathcal{O} \cdot \ell_i) }\). Not surprisingly, we have \(\sqrt{-d} \in \mathbb{Z}[\sqrt{-d}] \mapsto \omega \in \mathcal{O}\). This is an example of a quaternion embedding, but we won’t even need this terminology in this blog. An important property to note here is that since \(\mathfrak{a} \subseteq \mathbb{Z}[\sqrt{-d}]\), its action ideal (i.e. its embedding) will live inside \(\mathcal{O} + \mathcal{O} \cdot \omega\).

Attack Idea

Before we switched to studying the quaternion group action, we were considering the scenario where the attackers are given \((\mathcal{O}, \mathcal{O}_R([\mathfrak{a}]I(\mathcal{O})), \mathcal{O}_R([\mathfrak{b}]I(\mathcal{O})))\), where \(\mathfrak{a}, \mathfrak{b} \subseteq \mathbb{Z}[\sqrt{-d}]\). Since \([\mathfrak{a}] \subseteq \mathbb{Z}[\sqrt{-d}] \hookrightarrow I(\mathcal{O})\), we can simplify \([\mathfrak{a}]I(\mathcal{O})\) to simply \([\mathfrak{a}]\), understood as the image of the embedding \(\sqrt{-d} \mapsto \omega\). Since I know the answer already, I will further simplify the problem by forgetting about \(\mathfrak{b}\) altogether, arriving at the following problem:

Is this easy?

Connecting Ideals

In some sense, group actions “connect” elements in the set being acted on together. For example, the CSIDH group action \([\mathfrak{a}]\) is concretely an isogeny \(\varphi_{\mathfrak{a}}\), so e.g. \(E_1 = [\mathfrak{a}]E_0\) corresponds to \(\varphi_{\mathfrak{a}} : E_0 \to E_1 \). In the same way, our quaternion group action also connects quaternion orders in the same way.

Let \(I\) be a quaternion ideal with left order \(\mathcal{O}_0 = \mathcal{O}_L(I)\) and right order \(\mathcal{O}_1 = \mathcal{O}_R(I)\). We say that \(\mathcal{O}_0\) and \(\mathcal{O}_1\) are connected by \(I\), and \(I\) is the connecting ideal from \(\mathcal{O}_0\) to \(\mathcal{O}_1\).

Curiously, the challenge code contains a function connectingIdeal, which simply returns (I := O1 * O2) * I.norm().denominator(). I will defer the proof to the next post, but it is a natural consequence of the definitions of left and right orders (which we didn’t define).

Now that we have a connecting ideal \(I\) with left order \(\mathcal{O}\) and right order \(\mathcal{O}_A\), we still have to find an imaginary quadratic ideal \(\mathfrak{a}\) in \(\mathbb{Z}[\sqrt{-d}]\) that embeds to \(I\). Note that \(\mathfrak{a} \subseteq I \cap \mathrm{span}_{\mathbb{Z}}\{1, \omega\}\), so a natural candidate would be to guess that equality holds and use that to compute \(\mathfrak{a}\). As it turns out, when \(\mathcal{O}\) and \(\mathcal{O}’\) are oriented “in the same way”, i.e. the orienting element \(\omega\) is the same for the two orders, the equality does hold (see Jonathan’s blog).

We are very close to finishing the challenge, as once we have recovered \(\mathfrak{a}\), the rest is simply applying it to \(\mathcal{O}_B = [\mathfrak{b}]\mathcal{O}_0\) to derive the shared secret. However, we glossed over some details above, namely the orientation \(\omega\) and \(\omega’\).

Adjusting Orientations

Back in our Initial Analysis, we pretended that \(\omega’ = \omega\) is unchanged throughout the algorithm. However, if you run the GroupAction in a REPL a few times, you will see that the assumption is clearly wrong. The reason is that reduceHeight attempts to multiply everything by a scalar in the quaternion algebra to reduce the height, somewhat like a change of basis. However, this will also move \(\omega\) around, which is undesirable. Indeed, we can see that after reduceHeight returns a scalar element \(\beta\), the operation \(\omega \mapsto \beta\omega\beta^{-1}\) is performed. Hence, we would like to “undo” this by finding \(\beta\) such that \(\beta\omega’\beta^{-1} = \omega\), i.e. \(\beta\omega’ = \omega\beta\).

Write \(\beta = a + bi + cj + dk\). Since we know \(\omega\), we have \(\omega\beta = a\omega + b(i\omega) + c(j\omega) + d(k\omega)\). We can also do the same for \(\beta\omega’\) on the left hand side. Expanding and rearranging, we notice that we obtain an equation of the form \(A + Bi + Cj + Dk = 0\), where \(A, B, C, D\) are all linear combinations of \(a, b, c, d\). As a result, we obtain a set of linear equations in \(a, b, c, d\), and can recover a plausible \(\beta\). Apparently Jonathan was involved in a project which implemented the function as findIsom already. However, I provided my implementation below too, which is slower but easier to understand.

Partial Solve Script

First, let’s import the variables and outputs.

p = next_prime(2**512)
B = QuaternionAlgebra(-1, -p)
i, j, k = B.gens()
O0 = B.maximal_order()

omega = 820*i + 362*j + 153*k
d = -ZZ(omega**2)
ells = [ell for ell in Primes()[:150] if kronecker(-d, ell) == 1]
gens = [ZZ(mod(-d, ell).sqrt()) for ell in ells]

for line in open("output.txt", "r").readlines()[:4]:
    exec(preparse(line.strip()))

Next, we adjust the oriented quaternion orders such that the initial \(\omega\) and \(\omega_A, \omega_B\) agree.

def findIsom(omega1, omega2):
    mat1 = Matrix([list(b * omega1) for b in [1, i, j, k]])
    mat2 = Matrix([list(omega2 * b) for b in [1, i, j, k]])
    return B((mat1 - mat2).left_kernel().basis()[0])

OA_ = B.quaternion_order(O_A)
alpha = findIsom(omega_a, omega)
assert alpha * omega_a * alpha^-1 == omega
OA = B.quaternion_order([alpha * b * alpha^-1 for b in OA_.basis()])

OB_ = B.quaternion_order(O_B)
alpha = findIsom(omega_b, omega)
assert alpha * omega_b * alpha^-1 == omega
OB = B.quaternion_order([alpha * b * alpha^-1 for b in OB_.basis()])

Then, we follow the Attack Idea by computing a connecting ideal from \(O_0\) to \(O_A\), then intersecting it with \(\mathrm{span}_{\mathbb{Z}}\{1, \omega\}\).

I = connectingIdeal(O0, OA)
M = Matrix(ZZ, [list(B(1)), list(B(omega))])
M1 = I.free_module()
M2 = (ZZ^4).span(M)
_gens = M.solve_left((M1 & M2).basis_matrix())

Now, we can transfer this imaginary quadratic ideal \(\mathfrak{a}\) onto \(O_B\)!

frak = OB * (_gens[0, 0] + _gens[0, 1] * omega) + OB * (_gens[1, 0] + _gens[1, 1] * omega)
OAB = frak.right_order()

The rest is decrypting the flag.

shared_secret = invariant(OAB)
key = SHA256.new(data=str(shared_secret).encode()).digest()[:128]
AES.new(key, AES.MODE_CBC, iv).decrypt(ct)

Flag: kalmar{1s_th1s_l4tt1c3_b4s3d_crypt0?_meme.jpg}

For no reason, here’s a song I like recently.