Sun, 12 March 2023 ~ yyyyyyy
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.