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 is essentially a no-op, 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 prime ideals as edges. Since faults don’t occur that often, the sample 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.

The next task is to identify $E_A$, which may not necessarily be the most common sample. However, we can eliminate all curves “situated between” samples. What I mean is that for any path with two $\mathfrak{l}_i$ edges, $E_A$ cannot in the middle of the path. This is because Alice can only “undercalculate” the group action. After filtering out samples according to this condition, I chose the most common sample remaining to be $E_A$, and this was consistently correct.

Now that we have $E_A$, we can compute $(e_1 - e_1', \dots, e_n - e_n')$ for each sample and start making 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.

Using this logic, I was able to roughly guess private keys in order of likelihood and decrypt the flag within a few tries.