<- CRYPTO

400curves

9 minutes to read

We are provided with the server source code in Python:

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}


class Handler(socketserver.BaseRequestHandler):

    def handle(self):
        signal.alarm(0)
        main(self.request)


class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):  
    pass


def sendMessage(s, msg):
    s.send(msg.encode())


def recieveMessage(s, msg):
    sendMessage(s, msg)
    return s.recv(4096).decode().strip()


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")


if __name__ == '__main__':
    socketserver.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer(("0.0.0.0", 1337), Handler)
    server.serve_forever()

The server uses Elliptic Curve Cryptography (ECC) with curve secp256r1.

ECC background

Elliptic Curve Cryptography is a public-key cryptosystem, so there is a public key and a private key.

Let $E$ be an elliptic curve defined in Weierstrass form as:

$$ E: \; y^2 = x^3 + ax + b $$

Where $(x, y)$ are points within the curve.

In ECC, the above elliptic curve is considered under a finite field (for example, $\mathbb{F}_p$, with $p$ a prime number). Hence, the curve can be renamed as $E(\mathbb{F}_p)$.

As a result, the points in the curve form an abelian group under addition:

  • The operation is internal (i.e. $P + Q \in E(\mathbb{F}_p) \; \forall P, Q \in E(\mathbb{F}_p)$)
  • There is a unique identity element usually called $O$, such that $P + O = O + P = P$. This is also known as “point at infinity”
  • Every point has a unique inverse point, that is $\exists! Q \in E(\mathbb{F}_p) \;|\; P + Q = O \;\; \forall P \in E(\mathbb{F}_p)$. We can also say that $Q = -P$ abusing additive notation
  • The operation is associative (and also commutative)

The addition operation has a certain algorithm, which is implemented in the above source code. Once the addition is defined, we can express the product of a point by a scalar like this:

$$ kP = \underbrace{P + \dots + P}_{k\; \text{times}} $$

In order to use ECC, we must take a generator point $G$ of the curve, then take a number $n$ and multiply $n$ by $G$. The public key is formed by the points $G$ and $nG$ (apart from the curve parameters $a$, $b$ and the finite field $\mathbb{F}_p$); and the private key is the number $n$.

ECC can be used for Diffie-Hellman key exchange protocol (ECDH), Digital Signature Algorithm (ECDSA) or encryption (ECIES), among others. This cryptosystem relies on the difficulty to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP), that is, find $n$ given $G$ and $nG$.

The security flaw

As said before, the addition operation has a certain algorithm, which is implemented in the above source code. When adding points $P(x_1, y_1)$ and $Q(x_2, y_2)$, the algorithm depends only on $x_1$, $x_2$, $y_1$, $y_2$, $a$ and $p$. Notice that $b$ is never used.

Moreover, the algorithm operations are basic operations with numbers. There is no restriction on the values $x_1$, $x_2$, $y_1$, $y_2$. I mean, if $P(x_1, y_1)$ and $Q(x_2, y_2)$ are points of $E(\mathbb{F}_p)$, the result $R(x_3, y_3)$ will be another point of the curve. However, if $P$ and $Q$ are not in the curve, neither is $R$.

The above reasoning is the key to understand the flaw and the attack for this challenge. The server allows us to enter a public key $C(x, y)$ (a point within the elliptic curve). Then, the server will take our point and multiply it by the flag in decimal format ($S = \mathrm{flag} \cdot C$):

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 implementations of add and multiply are correct, but the server does not verify that the input points belong to the curve… Therefore, the server is vulnerable to an Invalid Curve Attack.

Invalid Curve Attack

We know that ECC relies on the difficulty to solve the ECDLP, that is, find $n$ given $G$ and $nG$. This problem is easier to solve when the order of the curve has small prime factors (also known as smooth), using Pohligh-Hellman algorithm.

Since the server does not check the input points, we can define a curve similar to the server’s curve (secp256r1), changing the $b$, until the order of the curve is smooth. Then, we will take a generator point $G$ of this new curve and send it to the server. The server will compute $S = \mathrm{flag} \cdot G$. Obviously, $S$ is not a point of the server’s curve, but it belongs to our curve. Now we can solve the ECDLP and find $\mathrm{flag}$ from $G$ and $\mathrm{flag} \cdot G$ because the order of our curve is smooth.

So, first of all, let’s use different values for $b$ until we find one that results in a smooth order. In SageMath, we can use the following code:

#!/usr/bin/env sage

a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff

for b in range(10):
    try:
        print(f"{b = }. Curve's order:", factor(EllipticCurve(GF(p), [a, b]).order()))  
    except:
        pass

And we have these results:

$ sage test_parameters.sage
b = 0. Curve's order: 2^96 * 7 * 274177 * 67280421310721 * 11318308927973941931404914103
b = 1. Curve's order: 71 * 823 * 1229 * 7489 * 30203 * 1275057701 * 5590685618197487513633360286414913886653362665945221
b = 3. Curve's order: 2^4 * 3 * 7 * 13 * 37 * 97 * 113 * 65364863466230065009299609518518318921279098632127819301704248465833
b = 4. Curve's order: 2^2 * 13 * 19 * 179 * 13003 * 1307093479 * 218034068577407083 * 16884307952548170257 * 10464321644447000442097  
b = 5. Curve's order: 2^2 * 3 * 7 * 13 * 2447 * 43333351749528183857746664058033075385207938864390055103100636196733549
b = 6. Curve's order: 2^2 * 5 * 4003 * 16033 * 102001 * 884390526899024919222120216398419141830968591728388637593606029
b = 7. Curve's order: 2^3 * 1151 * 7103 * 68360856945170627439059632547237 * 25897883110213973866199776436038742629
b = 8. Curve's order: 2^2 * 3 * 5 * 179 * 81173 * 132819857987697940358590682448908949725127147465817820814841295533643
b = 9. Curve's order: 2^2 * 7 * 653 * 72337 * 119591 * 88586821697531 * 8263795586816543575234964957311495031799816731687

It looks like $b = 4$ gives an order that is smooth enough. Maybe the last three factors are still big, but the small ones should be enough to solve the ECDLP.

Attack implementation

To implement the Invalid Curve Attack, we must take the vulnerable curve and find a generator point $G$. Then, send it to the server and solve the ECDLP. These tasks are implemented in the following Python code (importing SageMath functions):

#!/usr/bin/env python3

from Crypto.Util.number import long_to_bytes
from pwn import log, remote, sys
from sage.all import crt, discrete_log, EllipticCurve, factor, GF

a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
Fp = GF(p)
host, port = sys.argv[1].split(':')


def get_S(b):
    E = EllipticCurve(Fp, [a, b])
    order = E.order()
    factors = factor(order)
    G = E.gens()[0]
    log.info(f'ord(E_{b}) = {factors}')

    io = remote(host, int(port))

    io.sendlineafter(b'Awaiting public key of the client...\n', f'{G[0]} {G[1]}'.encode())  
    io.recvuntil(b'Shared secret: ')
    S_tuple = eval(io.recvline().decode())
    io.close()

    return order, G, factors, E(S_tuple)


def get_dlogs(S, G, order, factors, new_factors, dlogs):
    for prime, exponent in factors:
        log.info(f'{prime = }, {exponent = }')
        new_factors.append(prime ** exponent)
        t = order // new_factors[-1]
        dlogs.append(discrete_log(t * S, t * G, operation='+'))


def main():
    order, G, factors, S = get_S(4)

    new_factors, dlogs = [], []

    get_dlogs(S, G, order, factors[:-3], new_factors, dlogs)

    flag = crt(dlogs, new_factors)
    log.success(long_to_bytes(flag).decode())


if __name__ == '__main__':
    main()

However, it looks that the flag does not fit in the CRT modulus:

$ python3 solve.py 142.93.33.226:32737
[*] ord(E_4) = 2^2 * 13 * 19 * 179 * 13003 * 1307093479 * 218034068577407083 * 16884307952548170257 * 10464321644447000442097  
[+] Opening connection to 142.93.33.226 on port 32737: Done
[*] Closed connection to 142.93.33.226 port 32737
[*] prime = 2, exponent = 2
[*] prime = 13, exponent = 1
[*] prime = 19, exponent = 1
[*] prime = 179, exponent = 1
[*] prime = 13003, exponent = 1
[*] prime = 1307093479, exponent = 1
Traceback (most recent call last):
  File "solve.py", line 56, in <module>
    main()
  File "solve.py", line 52, in main
    log.success(long_to_bytes(flag).decode())
UnicodeDecodeError: 'utf-8' codec can't decode byte 0xb4 in position 1: invalid start byte

Notice that the order of the legitimate curve is very large, compared to the CRT modulus:

$ python3 -q
>>> 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
115792089210356248762697446949407573530086143415290314195533631308867097853951  
>>> 2 ** 2 * 13 * 19 * 179 * 13003 * 1307093479
3005800733613248324

Therefore, we should solve the complete ECDLP, which is very difficult and time-consuming. But there is an alternative: we can apply the same attack multiple times. For instance, let’s take also $b = 0$ and $b = 1$:

def main():
    order_0, G_0, factors_0, S_0 = get_S(0)
    order_1, G_1, factors_1, S_1 = get_S(1)
    order_4, G_4, factors_4, S_4 = get_S(4)

    new_factors, dlogs = [], []

    get_dlogs(S_0, G_0, order_0, factors_0[:-2], new_factors, dlogs)
    get_dlogs(S_1, G_1, order_1, factors_1[:-1], new_factors, dlogs)
    get_dlogs(S_4, G_4, order_4, factors_4[1:-3], new_factors, dlogs)  

    flag = crt(dlogs, new_factors)
    log.success(long_to_bytes(flag).decode())

Notice that we are skipping factor $2^2$ for the curve with $b = 4$ because there is a factor $2^{96}$ for the curve with $b = 0$ (CRT moduli must be coprime).

Flag

And now it works. Here we have the flag:

$ python3 solve.py 142.93.33.226:32737
[*] ord(E_0) = 2^96 * 7 * 274177 * 67280421310721 * 11318308927973941931404914103
[+] Opening connection to 142.93.33.226 on port 32737: Done
[*] Closed connection to 142.93.33.226 port 32737
[*] ord(E_1) = 71 * 823 * 1229 * 7489 * 30203 * 1275057701 * 5590685618197487513633360286414913886653362665945221
[+] Opening connection to 142.93.33.226 on port 32737: Done
[*] Closed connection to 142.93.33.226 port 32737
[*] ord(E_4) = 2^2 * 13 * 19 * 179 * 13003 * 1307093479 * 218034068577407083 * 16884307952548170257 * 10464321644447000442097  
[+] Opening connection to 142.93.33.226 on port 32737: Done
[*] Closed connection to 142.93.33.226 port 32737
[*] prime = 2, exponent = 96
[*] prime = 7, exponent = 1
[*] prime = 274177, exponent = 1
[*] prime = 71, exponent = 1
[*] prime = 823, exponent = 1
[*] prime = 1229, exponent = 1
[*] prime = 7489, exponent = 1
[*] prime = 30203, exponent = 1
[*] prime = 1275057701, exponent = 1
[*] prime = 13, exponent = 1
[*] prime = 19, exponent = 1
[*] prime = 179, exponent = 1
[*] prime = 13003, exponent = 1
[*] prime = 1307093479, exponent = 1
[+] HTB{1nv411d_cu2v3_4774cks_ftw!!}

For more information on this challenge, I recommend reading the write-up at Hack The Box blog.

The full script can be found in here: solve.py.