infinity

This challenge is about the CSIDH key exchange protocol. I referenced the original paper as well as Craig Costello's tutorial on supersingular isogeny key exchange.

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.