Keygreed  VolgaCTF 2020 Qualifier
Keygreed
by goulov
Points: 300 (35 solves)
Description:
Some time ago there was a file server which transmitted files over a custom secure protocol...
Our BFF Eva managed to do what she does best  she eavesdropped on a particular communication. We also managed to get our hand on the client server.
Is there any chance of getting something useful?
Given: EvaDump.pcap client.py
Solution:
TLDR

Check that the elliptic curve in the ECDH is supersingular.

Supersingular elliptic curves are unsafe for ECDH as they have a small embedding degree.

With embedding degree 2, implement the MOV attack and solve the dlog on a multiplicative group.
MOV attack
First extract from the pcap
the keyexchange messages between the client and the server. The client.py gives us the elliptic curve we are working in \(E\), over the field \(F_p\), and the used generator \(P\).
Checking that \(E\) is supersingular tells us that the embedding degree (smallest \(k\) such that the order of \(E\) divides \((p^k  1)\)) is small (\(k\leq 6\)). And computing it explicitly tells us that is \(2\).
The MOV attack works by using the Weil pairing (\(e: E[m] \times E[m] \to \mu_m\)) to translate solving the dlog in the elliptic curve group to solving it in the multiplicative group \(\mu_m\) (group of \(m\)th roots of unity), where subexponential algorithms exist.
Then, working in \(F_{p^k}\) (extension of \(F_p\)), take \(Q\) to be a point in \(E[m]\) (group of \(m\)torsion points), such that \(P,Q\) are linearly independent, which can be constructed. Finally, take \(e(P,Q)\) and \(e(xP,Q) = e(P,Q)^x\) (due to bilinearity of \(e\)) as a dlog instance over a fininte field (\(m\)th roots of unity), this is true by the nondegeneracy of the Weil pairing.
Compute the discrete logarithm in this finite field, compute the shared symmetric key, and decrypt the ciphertext, yielding the flag.
VolgaCTF{s0m3_curv35_4r3_sup3r_bu7_s1ngul4r}
I also tried to use PohligHellman, as the order decomposes with the largest prime factor of 63 bits. With a complexity of square root over this factor, this should be possible, unfortunately I didn’t have enough memory for the tradeoff…
Resources:
The solution code can be found in sol.sage.