hxp CTF 2022: not_csidh (pseudo)writeup

Here's a very short summary of the ideas behind the cryptography challenge not_csidh from our recent CTF. I wanted to get this out soon after the end of the CTF, but I didn't manage to finish a proper writeup in time, so it's bullet points for now (or maybe forever, depending on how things go 😬).

  • We're looking at the classical CM action (action of the ideal‑class group of the endomorphism ring) on an isogeny graph of ordinary elliptic curves, not unlike the constructions due to Couveignes and Rostovtsev–Stolbunov (but obviously more broken).
  • This construction was briefly discussed in De Feo–Kieffer–Smith, who correctly point out that "the CM method [...] is useless in our setting", but no details about the attack algorithm are given — rendering this the exact opposite of useless in my setting!
  • Parameters were constructed (indeed using the CM method) so that the curve has an order of large conductor inside an imaginary quadratic field with small class number as its endomorphism ring. The class number of such an order is large too, so naïvely brute‑forcing isogenies doesn't work.
  • Instead, the solution lies in the super cool theory of isogeny volcanoes: The isogeny graph in this setting has many "levels", and (for the parameters in the challenge) moving between the levels can be done efficiently.
  • The reason this helps is that the "exponent vectors" used in the cryptosystem to specify a secret group element remain valid when moving up a level in the volcano. Moreover, when moving down a level, the set of possible connecting exponent vectors is seriously restricted by the exponent vector "upstairs". Thus, this can be used to chop up the search problem at hand into many smaller subproblems.
  • At a high level, the solution works as follows: For both starting curve and public‑key curve, walk up to the crater of all isogeny volcanoes. Solve the isogeny problem between the resulting crater curves (easy as the class number of the maximal order is small), which gives an exponent vector that is correct for the maximal order. Then walk down the same paths, at each step brute‑forcing a lift of the previous exponent vector that connects the curves at the lower level.
  • My solver relies on a bunch of unpublished SageMath patches that I hope to submit for inclusion soon. After that has happened, I can hopefully show a standalone solve script that not only works with a standard setup, but should also be much shorter and prettier than the current version.