400Curves Writeup

Challenge Overview

• CTF: Hack The Box
• Challenge: 400Curves
• Category: Cryptography
• Author: WizardAlfredo
• Files: server.py

Introduction

What is a better feeling than solving a HackTheBox challenge when you can sleep at night? This writeup details the solution to 400Curves, a crypto challenge based on elliptic curves. We will show why not checking wether a point is on the curve can cause a lot of problems and how an attack called Invalid Curve Attack allows us solve the DLP to recover the private key. If you are new to Elliptic Curves, you can check this writeup , I gave an introduction on elleptic curves and DLP there. So let’s get going

Initial Analysis

server.py

server.py is the only provided file so we should be checking it out:

from Crypto.Util.number import inverse, bytes_to_long
import socketserver
import signal
from secret import FLAG

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

E = {'a': a, 'b': b, 'p': p}

def add(P, Q, E):
    if (P == (0, 0)):
        return Q
    elif (Q == (0, 0)):
        return P
    else:
        Ea, Ep = E['a'], E['p']
        x1, y1 = P
        x2, y2 = Q
        if ((x1 == x2) & (y1 == -y2)):
            return ((0, 0))
        else:
            if (P != Q):
                l = (y2 - y1) * inverse(x2 - x1, Ep)
            else:
                l = (3 * (x1**2) + Ea) * inverse(2 * y1, Ep)
        x3 = ((l**2) - x1 - x2) % Ep
        y3 = (l * (x1 - x3) - y1) % Ep
        return x3, y3

def multiply(P, n, E):
    Q = P
    R = (0, 0)
    while (n > 0):
        if (n % 2 == 1):
            R = add(R, Q, E)
        Q = add(Q, Q, E)
        n = n // 2
    return R

def main(s):
    sendMessage(s, "Establising the TLS handsake...\n")

    while True:
        C = recieveMessage(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 occured!\n")

The first thing to always check in ECC challenges is the curve parameters. The values of \(a\) , \(b\) , and \(p\) are the usual NIST P-256 parameters. So nothing looks obviously weak there. Say what you want but this is good news for me since it means we will be working with some good stuff here not usual things.

Now we can read the server logic slowly. The server asks us for two integers. Those become the point \((x, y)\) . Then it computes: \(S = [\text{bytes\_to\_long}(FLAG)]P\) , and sends \(S\) back.

So the private key is the flag itself, turned into a big integer. That already tells us what the goal is. If we recover the private key, we recover the flag directly by converting it to bytes.

But on a secure curve, scalar multiplication is supposed to be one-way. So the next thing to check is not the multiplication itself, but the assumptions behind it. multiply() is just double-and-add. There is nothing surprising there, usual stuff. So the next place to look is add(). Reading that function line by line, one detail stands out very quickly: the formulas use \(a\) , they use \(p\) , and of course they use the point coordinates, but they never use \(b\) . That matters more than it may seem at first, here is why:

For short Weierstrass curves of the form

the group law formulas depend on \(a\) , but not on \(b\) . So if the server does not check whether our point is actually on the original curve, then we are free to send a point from another curve of the form

with the same \(a\) and the same field prime \(p\) . Now this starts to look suspicious. The server behaves as if every input point belongs to the original curve, but it never checks it ,poor server trusted the wrong guy.

At that point, the question becomes simple: can we move to other curves where the group order has small factors, then use the server to recover the flag modulo those factors?

That is exactly the weakness here and the attack is called Invalid Curve Attack, one thing we can notice is the name of the challenge is 400Curves which gives us the impression we are on good track since 400 means invalid (hopefully you are a web fella and understand these stuff).

Understanding the Invalid Curve Attack

We understood that the bug is the fact that the server never checks whether our point lies on the original curve. Now let us understand precisely why that is so dangerous.

Curves with the same \(a\) and \(p\)

Recall the curve equation:

The group law formulas for point addition and doubling only depend on \(a\) and \(p\) , not on \(b\) . You can verify this by looking at the add() function: \(b\) never appears. This means that if we send a point \((x, y)\) that satisfies:

for some other value \(b'\) =/= \(b\) , the server will perform scalar multiplication on it using the exact same formulas, because those formulas do not care about \(b\) . In other words, the server is unknowingly computing the scalar multiplication on a completely different curve that we chose.

Why do we get to choose the curve?

Given a target \(b'\) , we need a valid point on:

We can pick any \(x\) we want, compute \(x^3 + ax + b' \bmod p\) , and check whether the result is a quadratic residue modulo \(p\) (i.e. whether it has a square root mod \(p\) ). If it does, we take the square root to get \(y\) , and \((x, y)\) is a valid point on \(E'\) . We are completely free to craft \(b'\) however we like, which means we can play around with the curve to have whatever group order we want.

Small subgroups and the discrete logarithm

Here is the idea behind the attack. The group order \(\#E'(\mathbb{F}_p)\) depends on \(b'\) . By trying different values of \(b'\) , we can find curves whose group order is smooth, meaning it has many small prime factors. For example, suppose we find a curve \(E'\) whose order is divisible by a small prime \(\ell\) . Then there exists a point \(P\) of order exactly \(\ell\) on \(E'\) , meaning:

We send this point \(P\) to the server. The server computes:

where \(d = \text{bytes\_to\_long}(FLAG)\) . Since \(P\) has order \(\ell\) , the result \(S\) is also a point of order dividing \(\ell\) , so there are only \(\ell\) possible values for \(S\) . We can find \(d \bmod \ell\) simply by trying all values \(k \in \{0, 1, \ldots, \ell - 1\}\) and checking which one satisfies \(kP = S\) . Because \(\ell\) is small, this brute force is trivial.

To obtain a point of order exactly \(\ell\) , we take any point \(T\) on \(E'\) and compute:

If \(P\) =/= \(\mathcal{O}\) , then \(P\) has order \(\ell\) .

Repeating across many curves

One small factor gives us \(d\) modulo one small number, which is not enough to recover the full flag. But we can repeat the process with many different curves \(E'_1, E'_2, \ldots\) , each with a different small prime factor \(\ell_1, \ell_2, \ldots\) , giving us:

As long as the primes \(\ell_1, \ell_2, \ldots, \ell_k\) are pairwise coprime and their product exceeds \(d\) , the Chinese Remainder Theorem (CRT) lets us combine all of these residues into the unique value of \(d\) modulo \(\ell_1 \ell_2 \cdots \ell_k\) . Once that product is large enough, we have recovered \(d\) exactly, and converting it back to bytes gives us the flag.

What the Server Lets Us Do

When connecting to the server, the interaction is very small:

Establising the TLS handsake...
Awaiting public key of the client...

So it is clear what the oracle gives us:

• it lets us send any \((x, y)\) pair we want
• it multiplies that point by bytes_to_long(FLAG)
• it returns the resulting point
• it does not check whether our point belongs to the intended curve

At this point the challenge path became clear:

1. Build a point on another curve with the same a and p.
2. Put that point in a small subgroup.
3. Ask the server to multiply it by the flag.
4. Recover the flag modulo that subgroup order.
5. Repeat enough times and combine everything with CRT.

So it is time for what? yes it is time for exploitation

Exploitation

Now that the weak point is identified, the rest is mostly about turning that idea into a clean attack.

The nice thing about this challenge is that the server gives us exactly the kind of oracle we need. Once that is clear, the rest becomes straightforward.

Step 1: Move to another curve

The first step is to stop thinking only about the original P-256 curve.

We keep the same field prime p and the same coefficient a, but we change b. So we work with curves of the form

for random values of b'.

Why does this help?

Because the server never checks curve membership. It will still apply the same addition formulas to points from E_{b'}.

So now we are free to look for curves whose group orders have small prime factors. Once we find one of those factors, we can build a point that lives in a small subgroup.

That is exactly what we want, because discrete logs in small subgroups are easy.

Step 2: Recover the flag modulo one small prime

Suppose we found a curve whose order has a small prime factor q, and suppose we build a point G of order q.

If we send G to the server, the reply is

where

Since G has order q, this result only depends on m \bmod q.

So in that subgroup, what we really have is:

Now the problem is small enough to solve directly. We compute the discrete log of Q with respect to G, and that gives:

So one useful query gives one modular piece of the flag.

Step 3: Repeat on many different subgroups

One congruence is not enough, of course.

So the next step is to repeat the same process on many different invalid curves, each time looking for a new small prime factor.

After a few rounds, we get relations like:

and so on.

As long as these subgroup orders are pairwise coprime, the Chinese Remainder Theorem combines them into one value modulo

Once that product is larger than the integer value of the flag, the result is no longer partial. It is the flag.

Step 4: Converting the flag into bytes

The server uses:

bytes_to_long(FLAG)

So after we combine all congruences with CRT, the result is the full integer form of the flag bytes. The last step is simply:

long_to_bytes(secret)

and that would give the flag

Recap

1. Read the server and notice that it multiplies our point by bytes_to_long(FLAG).
2. Check the addition formulas and see that there is no curve membership check.
3. Send points from curves with the same a and p, but different b.
4. Use small subgroups on those curves to recover the flag modulo many small primes.
5. Combine the congruences with CRT and convert the result back to bytes.

Full Solve Script

from os import environ
environ['TERM'] = 'xterm'
from pwn import *
from sage.all import EllipticCurve, GF, crt
from Crypto.Util.number import long_to_bytes
from ast import literal_eval
import random

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

HOST = '154.57.164.77'
PORT = 32239
conn = remote(HOST, PORT)

def send_point(x, y):
    conn.sendline(f"{x} {y}".encode())
    response = conn.recvuntil(b'Awaiting public key of the client...').decode()
    lines = [line for line in response.splitlines() if line.startswith("Shared secret:")]
    if not lines:
        return None
    secret_line = lines[-1]
    return literal_eval(secret_line.split("Shared secret:")[1].strip())

conn.recvuntil(b'Establising the TLS handsake...\n')
conn.recvuntil(b'Awaiting public key of the client...')
dlogs = []
primes = []
used_primes = set()

while len(dlogs) < 30:
    b_new = random.randint(1, p-1)
    F = GF(p)
    E_new = EllipticCurve(F, [a, b_new])
    order = E_new.order()
    factors = [q for q, e in factor(order)]

    for prime in factors:
        if prime <= 2**40 and prime not in used_primes:
            cofactor = order // prime
            G = E_new.gen(0) * cofactor
            if G.is_zero():
                continue
            x, y = G.xy()
            Q = send_point(int(x), int(y))
            if Q is None:
                continue
            Q_point = E_new(Q[0], Q[1])
            log = Q_point.log(G)
            dlogs.append(log)
            primes.append(prime)
            used_primes.add(prime)
            print(f"Found prime {prime}, dlog {log}")
            break

secret = crt(dlogs, primes)
print(long_to_bytes(int(secret)))

Running that script gives will give us the flag, it might take a bit of time so don’t worry if it takes too long, the important is it will show you the beloved HTB at the end.

This is the end for this writeup, I hope you enjoyed it. In case you did not understand a part just hit me up or email me and I will help you, see you soon on another post.