CA CTF 2022: Exploiting vulnerable Elliptic Curve parameters - MOVs Like Jagger

In this write-up, we'll go over the solution for the medium difficulty crypto challenge MOVs Like Jagger that requires the exploitation of a vulnerable elliptic curve.

Challenge Description 📄

While following the breadcrumbs from the secret messages you managed to recover from Broider, Bonnie gathered more information from his well trusted "Tsirakia" and found out that the messages were about the destinations of a STS (Space Transportation Ship). The STS, named "Paketo", is a notoriously large spaceship that transports military supplies for the Golden Fang mercenary army. After spending some time observing the seemingly random trajectory of Paketo, you and Paulie manually plotted the delivery locations and realized that the STS's orbit forms an elliptic curve. Your spaceship's advanced technology GPS has calculated the exact parameters of the curve. Can you somehow predict Paketo's final destination and hijack it?

The application at-a-glance 🔍

If you visit the homepage of the application, you will see a GPS like system indicating the movement of the STS called "Paketo". The only information available to us is the current coordinates and the coordinates from which the ship started.

We can try entering random data into the secret coordinates field and see what happens when we press the travel button.

We see that we are redirected to a conversation between Klaus and Bonnie, in which Bonnie tells us that we have travelled to Longhir.

At this point, we need to start looking at the source code to understand how things work.

Analysing the source code 📖

There are 3 files available app.py, navigation.py, utils.py

The utils.py script, generates random locations if we enter the wrong coordinates, so we ignore it.

app.py

We can see that in app.py there is an API provided:

@app.route('/api/coordinates', methods=['GET']) def coordinates(): points = { 'departed_x': hex(Q.x()), 'departed_y': hex(Q.y()), 'present_x': hex(P.x()), 'present_y': hex(P.y()) } return points @app.route('/api/get_flag', methods=['POST']) def get_flag(): try: travel_result = checkDestinationPoint(request.json, P, nQ, E) location = generateLocation(travel_result) if travel_result: return {"location": location, "flag": FLAG} else: return {"location": location} except ValueError as error: return {"error": error} if __name__ == '__main__': Q, nQ, P, nP = calculatePointsInSpace() app.run(host='0.0.0.0', port=1337, debug=False, use_reloader=False)

We see that in order to get the flag, we must somehow set travel_result = True. The function that sets travel_result is called checkDestinationPoint() and is imported from navigation.py

navigation.py

The basic workflow of the script is:

1. Initialise and define the parameters for the curve.

2. Compute 2 key pairs (the departed point) and (the present point).

3. Check if the coordinates given by the player are valid.

4. The secret point (destination point) is generated and compared with the point we have given. If they match, we get the flag.

Step 1 is translated into code:

from ecdsa import ellipticcurve as ecc from random import randint a = -35 b = 98 p = 434252269029337012720086440207 Gx = 16378704336066569231287640165 Gy = 377857010369614774097663166640 ec_order = 434252269029337012720086440208 E = ecc.CurveFp(p, a, b) G = ecc.Point(E, Gx, Gy, ec_order)

Step 2 is implemented with the calculatePointsInSpace() and generateKeyPair():

def generateKeyPair(): private = randint(1, 2**64) public = G * private return(public, private) def calculatePointsInSpace(): Q, nQ = generateKeyPair() P, nP = generateKeyPair() return [Q, nQ, P, nP]

Step 3 is implemented with the checkCoordintates() function. This is just a simple method to see if the points entered by the player are valid.

Step 4 is the win condition. If the secret_point and the point we entered match, we get the flag

secret_point = P * nQ same_x = destination_point.x() == secret_point.x() same_y = destination_point.y() == secret_point.y() if (same_x and same_y): return True else: return False

To summarise once again:
To get the flag, we need to make checkDestinationPoint() return True. To do this, we must somehow predict what the secret location   is.
Let’s search for the vulnerability now

Searching for the bugs 👾

One thing that should strike us when we look at the challenge is that the curve appears to use custom parameters. Let us examine these.

a = -35 b = 98 p = 434252269029337012720086440207

There are a lot of vulnerabilities we can check in custom elliptic curves, but really the title of the challenge is a big clue to the attack. If we search for something along the lines of "MOV attack elliptic curves" we will find a lot of resources.

Understanding the vulnerability 🔐

In ECC it is difficult to solve the discrete logarithm problem.

The basic idea of this attack is that the discrete logarithm problem can be moved from an elliptic curve defined over (finite field) to the multiplicative group of the finite field when is divided by . If is small enough (k < 6), the discrete log becomes easier to calculate than on the curve. Let us first check that is small:

from sage.all import * a = -35 b = 98 p = 434252269029337012720086440207 Gx = 16378704336066569231287640165 Gy = 377857010369614774097663166640 E = EllipticCurve(GF(p), [a, b]) k = 1 while (p**k - 1) % E.order(): k += 1 print(k)

In our case everything seems to be set.

┏━[/tmp] ┗━━ ■ python3 check_k.py 2

Exploitation 🔓

MOV attack

Analysing the source code in the above section, we concluded in step 5 that we must somehow find . is known, but is not.

We know  that , but in ECC it is really hard to solve this problem. If only we had a vulnerability... Oh, wait, we do! The MOV attack. Let us implement it.

A good abstraction of the attack algorithm can be found here.

Also a write-up that can help a lot of users with the implementation is this one.

The problem is solved for , , where and nQ = randomint(1, 2**64)

We will start by working in 

Ee = EllipticCurve(GF(p**k, 'y'), [a, b])

We choose such that and are linearly independent.

R = Ee.random_point() m = R.order() d = gcd(m, G.order()) B = (m // d) * R

After that we take the Weil pairing and 

Finally we compute the discrete logarithm in this finite field to find the secret multiplier.

nQ = beta.log(alpha)

The complete function is:

def movAttack(G, Q): k = 1 while (p**k - 1) % E.order(): k += 1 Ee = EllipticCurve(GF(p**k, 'y'), [a, b]) R = Ee.random_point() m = R.order() d = gcd(m, G.order()) B = (m // d) * R assert G.order() / B.order() in ZZ assert G.order() == B.order() Ge = Ee(G) Qe = Ee(Q) n = G.order() alpha = Ge.weil_pairing(B, n) beta = Qe.weil_pairing(B, n) print('Computing log...') nQ = beta.log(alpha) return nQ

There are 2 ways to get the points and calculate the secret coordinates. We can use the UI or the API. I will provide the manual way for aesthetic reasons and then the automatic solver that uses the API.

Manual exploitation

Let’s start by defining the curve:

from sage.all import * a = -35 b = 98 p = 434252269029337012720086440207 Gx = 16378704336066569231287640165 Gy = 377857010369614774097663166640 E = EllipticCurve(GF(p), [a, b])

Let’s visit the website again.

Gather all of the points:

Px = 0x43984282fd683ce8a6ae3b3be Py = 0x566a38eb7dbd4af0ed45421cb Qx = 0x3b505638fdfbf59f732e44805 Qy = 0xb8823b17c3f4047dc20a3afa P = E(Px, Py) Q = E(Qx, Qy)

Run the attack for Q:

nQ = movAttack(G, Q) secret_point = nQ * P

The complete script is:

from sage.all import * a = -35 b = 98 p = 434252269029337012720086440207 E = EllipticCurve(GF(p), [a, b]) def movAttack(G, Q): k = 1 while (p**k - 1) % E.order(): k += 1 Ee = EllipticCurve(GF(p**k, 'y'), [a, b]) R = Ee.random_point() m = R.order() d = gcd(m, G.order()) B = (m // d) * R assert G.order() / B.order() in ZZ assert G.order() == B.order() Ge = Ee(G) Qe = Ee(Q) n = G.order() alpha = Ge.weil_pairing(B, n) beta = Qe.weil_pairing(B, n) print('Computing log...') nQ = beta.log(alpha) return nQ Gx = 16378704336066569231287640165 Gy = 377857010369614774097663166640 Px = 0x43984282fd683ce8a6ae3b3be Py = 0x566a38eb7dbd4af0ed45421cb Qx = 0x3b505638fdfbf59f732e44805 Qy = 0xb8823b17c3f4047dc20a3afa G = E(Gx, Gy) P = E(Px, Py) Q = E(Qx, Qy) nQ = movAttack(G, Q) secret_point = nQ * P print(hex(secret_point[0])) print(hex(secret_point[1]))

And the output:

┏━[/tmp] ┗━━ □ python3 exploit.py Computing log... 0x34b15c6cdfc3233e1a0490134 0x57832f1e17a296d194cceefc3

Entering them to the secret coordinates field.

Give us the flag.

Automated exploitation

The automated solver that uses the API is:

from sage.all import * import requests def movAttack(G, Q): k = 1 while (p**k - 1) % E.order(): k += 1 Ee = EllipticCurve(GF(p**k, 'y'), [a, b]) Ge = Ee(G) Qe = Ee(Q) R = Ee.random_point() m = R.order() d = gcd(m, G.order()) B = (m // d) * R assert G.order() / B.order() in ZZ assert G.order() == B.order() n = G.order() alpha = Ge.weil_pairing(B, n) beta = Qe.weil_pairing(B, n) print('Computing log...') nQ = beta.log(alpha) return nQ url = 'http://127.0.0.1:1337/' a = -35 b = 98 p = 434252269029337012720086440207 Gx = 16378704336066569231287640165 Gy = 377857010369614774097663166640 E = EllipticCurve(GF(p), [a, b]) print("Elliptic Curve defined...\n") coordinates = requests.get(url + 'api/coordinates') departed_x = coordinates.json()['departed_x'] departed_y = coordinates.json()['departed_y'] print("Got Departed point coordinates!!\n") print(f" X: {departed_x}") print(f" Y: {departed_y}\n") present_x = coordinates.json()['present_x'] present_y = coordinates.json()['present_y'] print("Got Present point coordinates!!\n") print(f" X: {present_x}") print(f" Y: {present_y}\n") G = E(Gx, Gy) P = E(present_x, present_y) Q = E(departed_x, departed_y) print("Calculating private key using MOV attack...\n") nQ = movAttack(G, Q) print("Private key found!!\n") print(f"nQ: {hex(nQ)}\n") secret_point = nQ * P print("Calculated Destination point!!\n") print(f"X: {hex(secret_point[0])}") print(f"Y: {hex(secret_point[1])}\n") payload = { 'destination_x': hex(secret_point[0]), 'destination_y': hex(secret_point[1]) } flag = requests.post(url + 'api/get_flag', json=payload) print("Sending coordinates...") flag = flag.json()['flag'] print("Got flag...\n")

And that’s a wrap for this challenge write-up!