Write-Ups
WizardAlfredo,
Nov 19
2022
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.
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?
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... Loading Preview... Loading Preview...
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.
There is one file available: server.py
Looking at the script, we can see that the basic workflow is as follows:
It waits for our public key.
It computes the shared secret for the ECDH protocol.
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?
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...
We are now in a position to determine the attack, and as mentioned in the Idea section, this Loading Preview...
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.
Choose a random b.
Initialise the new curve.
Calculate the order of the curve.
Factorise the order.
Choose a sufficiently small factor.
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.
A pretty basic script for connecting to the server with pwntools:
if __name__ == '__main__':
r = remote('0.0.0.0', 1337)
pwn()
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)
# 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.
A final summary of all that has been said above:
Create the malicious point.
Send the point to the server.
Compute the discrete logs of the prime.
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!
Community
Blog Upcoming Events Meetups Affiliate Program SME Program Ambassador Program Parrot OSGet Help
Help Center Contact SupportCommunity
Blog Upcoming Events Meetups Affiliate Program SME Program Ambassador Program Parrot OSGet Help
Help Center Contact Support