CONFidence CTF 2020 Finals — ElGamal
all images are clickable
Challenge sources
The given tararchive contains two files:
 Challenge.cabal — challenge package description designed in Cabal:
name: Challenge
version: 0.1.0.0
buildtype: Simple
cabalversion: >=1.10
executable Challenge
mainis: Main.hs
builddepends: base,
arithmoi,
bytestring,
cryptonite,
cryptoapi,
safe
defaultlanguage: Haskell2010
 Main.hs — server source code written in Haskell:
Analyzing source code
Let’s look on these files.
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 wellknown 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 computesH = x * G
(whereG
is the curve base point) and prints outH
— ElGamal public key. Since we know the curve, we know all the parameters, except forx
. Our goal is find outx
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 ourx
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 considersM
as a part of point’s Xcoordinate: it multipliesM
by 256 and bruteforces the least significant byte, until it get the correct Xcoordinate. 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 Xcoordinate and divides it by 256. But there was some unexpected textencoding of nonprintable 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:
def decrypt(x):
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
return m
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:
putStr "c1: "
c1 < readLn
unless (isPointValid curve c1) $ do
return (error "Point invalid")
putStr "c2: "
c2 < readLn
unless (isPointValid curve c2) $ do
return (error "Point invalid")
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 most a
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:
y^2 = x^3 + 7 (mod 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
See this? a == 0
! And we also could make b == 0
, using Invalid curve attack. With a == 0
and b == 0
our equation becomes “more simple”:
y^2 = x^3 (mod 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
So, we can send a point from a cusp:
Cusp has wellknown property, which becomes useful in our case. One can construct a map from the cusp to an additive group. And the discrete logarithm in an additive group is just division:
source: https://crypto.stackexchange.com/a/67120
So our plan is:
 Send a point
c1 = Point 1 1
,c2 = PointO
(point at infinity)  Receive
s = (x * c1)
. SetQ = s
(using guessing a point Ycoordinate with 1byte bruteforce)  Calculate
x = (Q.x / Q.y)
(wherex
is private key)  Send
x
and get the flag!
Final exploit
Flag: p4{t0O_l4zy_t0_ev@luat3_th3_many_p0ss1bl3_j0k3s_I_c@n_m@k3_h3r3}
Many thanks to the author, the challenge is great!