defund - HackMD

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.