hxp CTF 2021

December 20, 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[k] P is the point at infinity. This occurs with probability 1/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 EA=ilieiE0E_A = \prod_i \mathfrak{l}_i^{e_i} E_0 be Alice’s public curve. Due to the faults, Alice instead computes ilieiE0\prod_i \mathfrak{l}_i^{e_i'} E_0, where eie_i and eie_i' have the same sign, but eiei|e_i'| \leq |e_i|. To sample these faulty cuves, we can submit a public key [b]E0[\mathfrak{b}] E_0 and apply b1\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 EAE_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 EAE_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 EAE_A was the most common sample.

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

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