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 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 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 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 EAE_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 li\mathfrak{l}_i edges, EAE_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 EAE_A, and this was consistently correct.

Now that we have EAE_A, we can compute (e1e1,,enen)(e_1 - e_1', \dots, e_n - e_n') for each sample and start making deductions.

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