First we’ll consider that Cabal package file may be useful later, when we would run the Haskell application locally. So we will start analyzing the Haskell code. Since it’s a bit unusual to see Haskell code in the crypto challenge, the reading itself isn’t too hard. After spending a few minutes I could slightly understand what’s going on.
Okay, so we’re working with some Elliptic curve. The analysis of encrypt/decrypt functions (or just reading the challenge’s name) helps us to guess the encryption scheme — it’s ElGamal. So, here is ElGamal scheme over the Elliptic curve, right? Yea, looks secure, because discrete logarithm problem is still hard on Elliptic curves (this probem is also known as ECDLP).
The curve is secp256k1, it’s a well-known Elliptic curve, and it provides enough security for this challenge. This curve is even used by Bitcoin. Since we’re working over that curve, let’s start our exploit with curve parameters. We denote the curve E and its base point G:
I’ll describe a bit what the server does:
First it generates an integer x — ElGamal private key. Next it computes H = x * G (where G is the curve base point) and prints out H — ElGamal public key. Since we know the curve, we know all the parameters, except for x. Our goal is find out x and break the cryptosystem.
Then the server gives us 5 attempts to encrypt and decrypt arbitrary messages. We also could ask for the flag, but we need to know the private key. When we send correct x to the server, it will print the flag. But if our x is invalid, the server drops the connection.
How does the server stores a message inside the Elliptic curve? It just transforms it into the Elliptic curve point! Suppose we have an integer M — our message. Server considers M as a part of point’s X-coordinate: it multiplies M by 256 and bruteforces the least significant byte, until it get the correct X-coordinate. Pseudocode:
M = <our message>
for i in range(256):
x = M * 256 + i
if secp256k1 contains a point with such x:
return (x, y)
Retrieving message process is similar: the server just takes the X-coordinate and divides it by 256. But there was some unexpected text-encoding of non-printable characters. For example: "])\229\243Jb)L\200\163\139\239\236U:\ENQ&t\RSH5,\152a\233\227\DC4)\bf\221". I don’t know what it is, so my teammate @ilyaluk helped me and wrote the decoder:
So, now we completely understand what the server does. Let’s try to find some vulnerabilities.
Invalid curve attack
There are no obvious vulnerabilities, because secp256k1 is secure itself, and the code ensures all required security checks. Since we need to recover x, I started to analyze decrypt function, because it was the only one place in the whole code where x is used. Here is decrypt pseudocode:
c1 = input point
assert c1 is on secp256k1
c2 = input point
assert c2 is on secp256k1
s = x * c1
s_inv = -s
m = c2 + s_inv # c2 - s
Luckily, we control the point c1, which are multiplied by x! Looks like a clue. Since we know c1, c2 and resulting m, we can reverse all transformations and retrieve s. But discrete logarithm is still hard.
First I started to think about Small subgroup attack, but quickly realized that the curve base point G has prime order (quite expected). Suddenly my teammate @CerebralObserver pointed out that some security check does not hold! More precisely, this code just does nothing (I don’t know Haskell, so I don’t understand why, but it’s a fact). These errors are never thrown:
When we’re working with Elliptic curves, we need to ensure that all points are on the curve. It means if we have a point (x0, y0) we need to check the equation y0^2 == x0^3 + a*x0 + b (where y^2 == x^3 + a*x + b is our Elliptic curve). If the equation does not hold (or we just don’t check it), the cryptosystem becomes vulnerable to Invalid curve attack.
This attack exploits the fact that we are able to send fake point to the server, and it will perform all Elliptic curve operations with our fake point. To understand the attack, let’s look at the Elliptic curve addition law. If we want to calculate R = P + Q, here are two main cases:
P != Q
s = (P.y - Q.y) / (P.x - Q.x)
R.x = s ^ 2 - P.x - Q.x
R.y = P.y + s * (R.x - P.x)
P == Q
s = (3 * P.x ^ 2 + a) / (2 * P.y)
R.x = s ^ 2 - 2 * P.x
R.y = P.y + s * (R.x - P.x)
As you see, the addition law uses at mosta coefficient from the Elliptic curve equation, and b is never used! So without the correct curve check we could send a fake point from another Elliptic curve (with another b coefficient)! Thats why the attack called Invalid curve — we send a fake point from Invalid (less secure) curve, but the secret remains the same. Using known vulnerabilities in our Invalid curve we could “easily” find the discrete logarithm.
Mapping to additive group
How Invalid curve attack could be exploitable in our case? Let’s look at the secp256k1 equation again: