# 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?


### Solution:

#### TLDR

1. Check that the elliptic curve in the ECDH is supersingular.

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

3. With embedding degree 2, implement the MOV attack and solve the dlog on a multiplicative group.

#### MOV attack

First extract from the pcap the key-exchange 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 sub-exponential 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 non-degeneracy 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 Pohlig-Hellman, 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 trade-off…

# Resources:

The solution code can be found in sol.sage.