owned this note
owned this note
Published
Linked with GitHub
# infinity
This challenge is about the CSIDH key exchange protocol. I referenced the original [paper](https://eprint.iacr.org/2018/383) as well as Craig Costello's [tutorial](https://eprint.iacr.org/2019/1321) 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.