Business CTF 2022: Invalid curve attack - 400 Curves

In this blog post, we'll go over the solution for the medium difficulty crypto challenge 400Curves, which requires the exploitation of an insecure ECDH implementation that doesn’t check the validity of public keys. 

Description 📄

After the takeover of Felonious Forums

Loading Preview...

, we've managed to identify and apprehend a low-level MonkeyBusiness APT operative. The developer was in charge of reselling components of the Zoid malware family. During a forensics investigation of the operative's computer, we obtained the prototype source code of the TLS-based proxy service, which was used to obfuscate C2 traffic between the compromised machines to evade interception/detection. The remote host is still up, but the ssh keys we found have since been invalidated. During an assessment of the component's source code, it looks like the key for the TLS-encrypted traffic is generated using the ECDH protocol with the P-256 curve, which is the most common curve on the Internet. Can you find a way to retrieve the proxy service's private key?

🎮 PLAY THE TRACK

The Idea 💡

In my research on real-world attacks on ECC, I came across an attack called an invalid curve attack. I first learned about this attack when I read this

Loading Preview...

write-up by Joseph about a Google CTF 2021 challenge called Tiramisu. At the time, I didn't have enough knowledge to understand the underlying math behind the exploitation, so I gave up. As I gained more experience, I became more confident and started taking notes and reading more articles about it. I was lucky enough to find this

Loading Preview...

presentation from OWASP that showed an example with a simple curve. I also found this

Loading Preview...

write-up and was ready to take on the challenge. In my research, I also found that old versions of JCE and Bouncy Castle are known to be vulnerable to this attack, which could be useful for future pentesting projects.

The application at-a-glance 🔍

When we try to connect to the tcp server with something like nc, we are greeted with a message that a TLS handshake is trying to be established. 

┏━[~]
┗━━ ■ nc 0.0.0.0 1337
Establishing the TLS handshake...
Awaiting public key of the client...

The server asks us to enter our public key. We can try to enter a random key. A message appears that an error has occurred.

1234
Error occurred!

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

Analyzing the source code 📖

There is one file available: server.py

server.py

Looking at the script, we can see that the basic workflow is as follows:

1. It waits for our public key.

2. It computes the shared secret for the ECDH protocol.

3. It sends back the shared secret.

This is translated into code:

    while True:
        C = receiveMessage(s, "Awaiting public key of the client...\n")
        try:
            x, y = [int(i) for i in C.strip().split()]
            S = multiply((x, y), bytes_to_long(FLAG), E)
            sendMessage(s, f"Shared secret: {S}\n")
        except:
            sendMessage(s, f"Error occurred!\n")

If we examine the multiplication function. It looks like a textbook implementation of the double and add algorithm. So there is nothing interesting to discover. So where is the bug?

Searching for the bugs 👾

The name of this challenge is a hint at what the vulnerability is. Searching for ECC attacks, we can find a lot of resources. A great paper for CTFs in general is this

Loading Preview...

one. Unfortunately, our case does not fit any of the cases described in the paper. Searching for practical ECDH attacks on TLS as mentioned in the description, we find an attack called "Invalid Curve Attack". Another look at the challenge name shows that 400 is the response code for Bad or Invalid HTTP requests. So the name of the challenge means "Invalid Curves". These attacks exploit the fact that many applications do not verify the attacker's public key, and by sending malicious payloads, it is possible to extract the private key. More precisely, the attacker can send a public key that does not belong to the server's curve and solve the DL problem much faster.

Exploitation 🔓

Mathematics

We are now in a position to determine the attack, and as mentioned in the Idea section, this

Loading Preview...

article can be easily found. Let us use it to understand the mathematical background.

Suppose we have the curve

a = 9, b = 17, p = 23
E = EllipticCurve(GF(p), [a, b])
E.plot()

If we plot the curve using Sage, we can see all 32 points that can be generated.

Looking at the diagram below that explains the ECDH protocol, we can start implementing the protocol with our custom curve.

Suppose and then the shared secret will be .

But what happens if we compute a Q' outside the curve E? Q' can have a small order. That is, if we multiply a number by Q', the possible results will be a small number. To generate such points, we can use the following algorithm.

1. Choose a random b.

2. Initialise the new curve.

3. Calculate the order of the curve.

4. Factorise the order.

5. Choose a sufficiently small factor.

6. Generate the malicious point that has this factor as an order.

Let us continue with the hypothetical curve we initialized above. Suppose the new curve is

a = 9, b2 = 5, p = 23
E_2 = EllipticCurve(GF(p), [a, b2])
E_2.plot()

The new curve has fewer points. Let's follow the algorithm.

Step 3:

order = E_2.order()
order
18

Step 4:

factors = prime_factors(order)
factors
[2, 3]

Since 3 is quite small, we choose 3 as our prime number.

prime = 3

Step 5:

Finally, we will create the point with order 3 with:

Q = E_2.gen(0) * int(order / prime)
Q
(3 : 6 : 1)
Q.order()
3

Suppose that the server's secret key is . If we send this point to the server, the result we get is . We have 3 possible values that the output can be.

>>> for i in range(10):
...     print(i * Q)
...
(0 : 1 : 0)
(3 : 6 : 1)
(3 : 17 : 1)
(0 : 1 : 0)
(3 : 6 : 1)
(3 : 17 : 1)
(0 : 1 : 0)
(3 : 6 : 1)
(3 : 17 : 1)
(0 : 1 : 0)

(0 : 1 : 0), (3 : 6 : 1) or (3 : 17 : 1)

If we use the multiply function:

multiply((3, 6), 8, E)
(3, 17)

So let's now solve the discrete log problem:

G.discrete_log(E_2(3, 17))
2

And we have our first result . Repeating this process for different primes is sufficient to extract the private key, simply by using the CRT.

Connecting to the server

A pretty basic script for connecting to the server with pwntools:

if __name__ == '__main__':
    r = remote('0.0.0.0', 1337)
    pwn()

Generating the points

The mathematics behind this section has already been explained in the Mathematics section. The only thing that should be pointed out is the prime number limits. In order to solve the DL problem in a relatively short time, the prime number we choose must not be greater than 2**40. 

    b = randint(1, p)
    E = EllipticCurve(GF(p), [a, b])
    order = E.order()
    factors = prime_factors(order)

    valid = []
    for factor in factors:
        if factor <= 2**40:
            valid.append(factor)

    prime = valid[-1]

    G = E.gen(0) * int(order / prime)

Sending, receiving, and DL

    # Here we send G to the server
    tmp_point = G.xy()
    tmp_x, tmp_y = str(tmp_point[0]), str(tmp_point[1])
    tmp_point = tmp_x + " " + tmp_y
    message = b"Awaiting public key of the client...\n"
    r.sendlineafter(message, bytes(tmp_point, "Latin"))

    # We get back Q which is G * k
    data = r.recvline()
    print(data)

    if b"Error" in data:
        print("An error on the server occured")
        return None, None

    Q = eval(data[len("Shared secret: "):])

Now we have the shared secret and we are ready to solve the DL problem.

    try:
        Q = E(Q[0], Q[1])
        print("Computing the discrete log problem")
        log = G.discrete_log(Q)
        print(f"DL found: {log}")
        return (log, prime)
    except Exception as e:
        print(e)
        return None, None

All the above are calculated with the function getDLs(). If we repeat the process enough times, in our case it should be 16, we can find the secret key with the CRT.

Getting the flag

A final summary of all that has been said above:

1. Create the malicious point. 

2. Send the point to the server.  

3. Compute the discrete logs of the prime. 

4. Perform CRT to find the server of the key aka the flag.

This recap can be represented by code using the pwn() function.

def pwn():
    dlogs, primes = getDLs()
    print(f"dlogs: {dlogs}")
    print(f"primes: {primes}")
    super_secret = CRT_list(dlogs, primes)
    print(long_to_bytes(super_secret))

The final script is:

from Crypto.Util.number import long_to_bytes
from sage.all_cmdline import *
from pwn import *

a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff


def solveDL():
    b = randint(1, p)
    E = EllipticCurve(GF(p), [a, b])
    order = E.order()
    factors = prime_factors(order)

    valid = []
    for factor in factors:
        if factor <= 2**40:
            valid.append(factor)

    prime = valid[-1]

    G = E.gen(0) * int(order / prime)

    # Here we send G to the server
    tmp_point = G.xy()
    tmp_x, tmp_y = str(tmp_point[0]), str(tmp_point[1])
    tmp_point = tmp_x + " " + tmp_y
    message = b"Awaiting public key of the client...\n"
    r.sendlineafter(message, bytes(tmp_point, "Latin"))

    # We get back Q which is G * k
    data = r.recvline()
    print(data)

    if b"Error" in data:
        print("An error on the server occured")
        return None, None

    Q = eval(data[len("Shared secret: "):])
    try:
        Q = E(Q[0], Q[1])
        print("Computing the discrete log problem")
        log = G.discrete_log(Q)
        print(f"DL found: {log}")
        return (log, prime)
    except Exception as e:
        print(e)
        return None, None


def getDLs():
    dlogs = []
    primes = []
    for i in range(1, 16):
        log, prime = solveDL()
        if log != None:
            dlogs.append(log)
            primes.append(prime)
        print(f"counter: {i}")
    return dlogs, primes


def pwn():
    dlogs, primes = getDLs()
    print(f"dlogs: {dlogs}")
    print(f"primes: {primes}")
    super_secret = CRT_list(dlogs, primes)
    print(long_to_bytes(super_secret))


if __name__ == "__main__":
    r = remote("0.0.0.0", 1337)
    pwn()

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

🎮 PLAY THE TRACK