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
Where
In ECC, the above elliptic curve is considered under a finite field (for example,
As a result, the points in the curve form an abelian group under addition:
- The operation is internal (i.e.
) - There is a unique identity element usually called
, such that . This is also known as “point at infinity” - Every point has a unique inverse point, that is
. We can also say that 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:
In order to use ECC, we must take a generator point
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
The security flaw
As said before, the addition operation has a certain algorithm, which is implemented in the above source code. When adding points
Moreover, the algorithm operations are basic operations with numbers. There is no restriction on the values
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
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
Since the server does not check the input points, we can define a curve similar to the server’s curve (secp256r1), changing the
So, first of all, let’s use different values for
#!/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
Attack implementation
To implement the Invalid Curve Attack, we must take the vulnerable curve and find a generator point
#!/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
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
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 writeup at Hack The Box blog.
The full script can be found in here: solve.py
.