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

  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.