why is a raven.. – Union CTF 2021

Points: 826 (12 solves)

tldr

We are given an implementation of SIDH, but with some unusual extra information \(\phi_A(P_A),\phi_A(Q_A)\) shared by Alice.
Exploit this extra information to compute the kernel of Alice’s secret isogeny \(\phi_A\), by solving the discrete log in \(E[2^{e_A}]\).
With Alice’s secret key and Bob’s public key compute the shared curve, and take its \(j\)-invariant as the secret symmetric key to decrypt the flag.

attack

intro to SIDH

The cryptosystem we are dealing with here is the Supersingular isogeny Diffie–Hellman (SIDH). This key-exchange protocol starts with a public supersingular elliptic curve \(E\) defined over \(\mathbb{F} _ {p^2},\, (p=2^{e_A} 3^{e_B}-1)\), where Alice and Bob each have assigned a torsion subgroup \(E[2^{e_A}]\) and \(E[3^{e_B}]\), represented by the public bases \(\langle P_A,Q_A\rangle\) and \(\langle P_B, Q_B \rangle\) respectively.

First, Alice and Bob each choose random secret subgroups, by taking (secret) linear combinations of their bases. Alice computes \(\langle A \rangle = \langle P_A + [k_A] Q_A \rangle \subset E[2^{e_A}]\), and Bob computes \(\langle B \rangle = \langle P_B + [k_B] Q_B \rangle \subset E[3^{e_B}]\). Then, taking these subgroups as the kernel, they define their secret isogenies as \(\phi_A: E\to E/\langle A\rangle\) and \(\phi_B: E\to E/\langle B\rangle\). Note that these isogenies can be computed by composing \(e_A\) degree-2 (or \(e_B\) degree-3) isogenies sequentially (computing it otherwise is believed to be computationally hard).

And, they share auxiliary information with one another (the messages of the DH protocol), including the codomain of their isogeny, and the image of their secret isogeny on the other party points (it is not enough to send \(E_A, E_B\) to each other, since \(\phi_A\) can’t act on \(E_B\), nor \(\phi_B\) on \(E_A\)). Thus, \[\text{Alice sends } (E_A, P_B’, Q_B’) = (E/\langle A\rangle,\phi_A(P_B),\phi_A(Q_B)) \text{ to Bob.}\] \[\text{Bob sends } (E_B, P_A’, Q_A’) = (E/\langle B\rangle,\phi_B(P_A),\phi_B(Q_A)) \text{ to Alice.}\]

Finally, they are able to compute a shared final curve \(E/\langle A,B\rangle\) (up to isomorphism), where Alice recomputes her secret isogeny \(\phi_A’: E_B\to E_{AB}\) but with domain \(E_B\), \(\langle A’\rangle = \langle P_A’ + [k_A]Q_A’ \rangle\), \(E_{AB} = E_B/\langle A’\rangle\); and Bob recomputes his secret isogeny \(\phi_B’: E_A\to E_{BA}\) but with domain \(E_A\), \(\langle B’\rangle = \langle P_B’ + [k_B]Q_B’ \rangle\), \(E_{BA} = E_A/\langle B’\rangle\). They compute the shared symmetric secret corresponding to the \(j\)-invariant of the codomain of these new isogenies. \[j(E_{AB}) = j(E/\langle A,B\rangle) = j(E/\langle B,A\rangle) = j(E_{BA}).\]

where’s the catch?

Here, Alice also sends something dangerous when she sends her message \((E_A, P_B’, Q_B’)\) to Bob, she also sends the image of her secret isogeny \(\phi_A\) of her own public basis of \(E[2^{e_A}]\), \((\phi_A(P_A), \phi_A(Q_A))\). But, since the kernel of \(\phi_A\) is \(\langle P_A + [k_A]Q_A\rangle\), we have \(\phi_A(P_A + [k_A]Q_A)=0\), and isogenies are group homomorphisms, so \[\phi_A(P_A + [k_A]Q_A) = \phi_A(P_A) + [k_A]\phi_A(Q_A) = 0,\] and we can solve this discrete logarithm for \(k_A\) (Alice’s secret) using Pohlig-Hellman, since \(E[2^{e_A}]\) is a group of smooth order \(2^{e_A}\).

Given Alice’s secret key, we can take Bob’s public key and finish the protocol by computing \(j(E_{AB})\), and using it as the AES symmetric key to decrypt the ciphertext and get the flag:

union{al1c3_in_t0r51ongr0upl4nd}

resources

The code for the solution can be downloaded here.