# hxp CTF 2021

December 20, 2021

This is a writeup for infinity, which centers around the CSIDH key exchange protocol. I referenced the original paper as well as Craig Costello’s tutorial on supersingular isogeny key exchange. Solution code is here.

We’re given a “buggy” CSIDH implementation which does not actually work — in fact, the computation is not even deterministic. On a remote server, Alice generates a private key and performs up to 500 key exchanges with us.

Comparing against Algorithm 2 in the CSIDH paper, I found that the implemention does not check whether $$[k] P$$ is the point at infinity. Recall that $$[k] P$$ is intended to be of order $$\ell$$, so that we obtain an $$\ell$$-isogeny. But this is impossible if $$\ell$$ does not divide the order of the randomly generated point, which occurs with probability $$1/\ell$$. When this happens, the order of $$[k] P$$ is $$1$$ and we obtain the identity map. This is essentially a no-op, but the exponent is still decremented as if we performed an $$\ell$$-isogeny!

The upshot is that Alice will often fail to apply the full class-group action given by her private key. Let $$E_A = [\cdots \mathfrak{l}_i^{e_i} \cdots] E_0$$ be Alice’s public curve. Due to the faults, Alice instead computes $$[\cdots \mathfrak{l}_i^{e_i - k_i} \cdots] E_0$$, where $$e_i, k_i$$ have the same sign and $$|k_i| \leq |e_i|$$. To sample curves near $$E_A$$, we can submit a public key $$[\mathfrak{b}] E_0$$ and apply $$\mathfrak{b}^{-1}$$ to the response (make sure to patch the implementation).

Let’s visualize a graph with curves as vertices and prime ideals as edges. Since faults don’t occur that often, the sample curves are close to $$E_A$$ and hence one another. Finding paths between them can be done with a meet in the middle algorithm. The idea is to perform a depth-2 search from each sample and cache all visited curves. The collisions will identify all paths of length at most 4. In practice, I was able to consistently unify all 500 samples into a connected component.

To identify $$E_A$$, consider the following: 1. Alice still reaches $$E_A$$ with significant probability. 2. $$E_A$$ is the furthest away in the sense that Alice can only "undercalculate" the class-group action.

The first fact implies that the public curve appears many times among the samples. The second fact is not as useful as it sounds: suppose the ideal mapping one sample to another decomposes into a product containing $$\mathfrak{l}_i$$. If $$e_i$$ is positive, the latter curve is further away. But if $$e_i$$ is negative, it is closer since the inverse contains $$\mathfrak{l}_i^{-1}$$. Still, this lets us eliminate any curves situated "in between" samples. I chose the most common sample which remained, which seemed to work.

With the public curve, we can compute the $$k_i$$ values for each sample. We can make deductions like "$$k_i = 2$$ implies $$e_i = 2$$", but to further constrain the private key I turned to statistical arguments. For example, when $$e_i = 1$$ the probability of no faults across all samples is $$(1 - 1/\ell_i)^{500}$$. Even for the largest prime $$113$$, this is around one percent. Thus if $$k_i = 0$$ for all samples, we can safely guess $$e_i = 0$$.

Another case is where some $$k_i = 0$$, while others are $$1$$. Clearly $$e_i$$ is positive, and we can attempt to determine it based on the number of faults — in general we expect to see $$500 \cdot (1 - (1 - 1/\ell_i)^{e_i})$$ of them. For the largest prime $$113$$, the expected values are $$4.24$$ and $$8.81$$ for $$e_i = 1, 2$$ respectively. Using these heuristics, I was able to roughly guess private keys in order of likelihood and decrypt the flag within a few tries.