hxp CTF 2021

This is a writeup for infinity, a challenge based on CSIDH. This was actually my first time working with CSIDH, and I found the original paper quite helpful. If you aren’t familiar with isogenies in general, I would suggest reading section 3 of Craig Costello’s tutorial (the rest is only relevant to SIDH, a different isogeny-based cryptosystem). Also, here’s my solution code.

In this challenge, the server generates a private key and performs up to 500 key exchanges with us. However, this implementation of CSIDH is buggy — in fact, the computation is not even deterministic! Comparing against Algorithm 2 in the CSIDH paper, I found that the implementation does not check whether $[k] P$ is the point at infinity. This occurs with probability $1/\ell$, and when it happens, we obtain the identity map rather than an $\ell$-isogeny. Evaluating it does nothing, but the code still decrements the exponent as if it evaluated 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 = \prod_i \mathfrak{l}_i^{e_i} E_0$ be Alice’s public curve. Due to the faults, Alice instead computes $\prod_i \mathfrak{l}_i^{e_i'} E_0$, where $e_i$ and $e_i'$ have the same sign, but $|e_i'| \leq |e_i|$. To sample these faulty cuves, 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 $\ell$-isogenies as edges. Since faults don’t occur very often, the faulty curves are all clustered in one area of the graph. Finding paths between them can be done with a meet in the middle algorithm. For example, suppose we perform a depth-2 search from each sample and cache every curve we visit. Every time we encounter a collision, we obtain a path between curves. It follows that we recover all paths of length 4 or less. In practice, I was able to consistently link all 500 samples into a single connected component.

As an intermediate step, let’s identify $E_A$. Suppose the first and last edges of a path in the connected component are isogenies of the same degree. Then none of the intermediate vertices in the path are $E_A$, since Alice can only under-calculate the group action. This observation allows us to rule out many curves. Out of the remaining ones, I consistently found that $E_A$ was the most common sample.

Using $E_A$, we can compute $(e_1 - e_1', \dots, e_n - e_n')$ for each sample and make the following deductions:

• If any $e_i - e_i' = 2$, then $e_i = 2$. This is because we know $0 \leq e_i' \leq e_i \leq 2$. Similarly, if any $e_i - e_i' = -2$, then $e_i = -2$.

• If $e_i = 1$, then we would expect to observe some faults. In fact, the probability of no faults across is $(1 - 1/\ell_i)^{500}$. Even for the largest prime 113, this is around one percent. Therefore if $e_i - e_i' = 0$ for all samples, we can safely guess $e_i = 0$.

• In general, we expect to see $500 \cdot (1 - (1 - 1/\ell_i)^{|e_i|})$ faults for each $i$. For the largest prime 113, the expected values are 4.24 and 8.81 for $e_i = 1, 2$ respectively.

By guessing private keys in order of likelihood, I was able to decrypt the flag within a few tries.