BKPCTF 2017 - Crypto, 600 points
Author: Colin Stanfill
Thanks: Allan Wirth (challenge idea), George Silvis III (Support), Microsoft Research (SIDH library)
We kind of lost the flag to this challenge... I think someone submitted it on the old version of the site though, maybe you can help us find it again?
<file download of TLS packet capture>
The server in the challenge description served static html over https with a special patch to support "Super-singular Isogeny Diffie-Hellman Key Exchange" as an intial key exchange method (in TLSv1.2 only). ALL other ciphersuites and TLS versions were disabled, so any normal browser that connected to the site would fail to finish the SSL handshake. Plain HTTP was not enabled (plaintext requests at port 443 would display an error page, which we couldn't configure out of nginx in time).
However, if an application was compiled to support SIDH as a key exchange method, the server would provide a valid, authenticated LetsEncrypt certificate for its domain.
The packet capture contained https traffic to the server using the ciphersuite in the challenge name. The https session consisted of a single session in which a user POSTed a flag to a submission form on the site.
Server reuses private+public key in SSL key exchange across all connections, which allows recovery of past SSL session keys, including the one in the pcap.
Source for attack (Section 3)
Allan first heard of this attack at a Real World Crypto talk given by Michael Naehrig in 2017, titled "Supersingular Isogeny Diffie-Hellman". Slides for that talk can be found here
Brief but math-heavy summary:
Alice's private key is a number
n_A. Bob's public key a pair of elliptic
Q_B such that
[2^372]P_B = [2^372]Q_B = 0. The shared
secret is calculated by Alice based on the value
Q_B + [n_A]P_B.
Bob calculates his shared secret honestly but sends Alice the public key
Q_B, P_B + [2^371]Q_B, so Alice will calculate her shared secret based on
Q_B + [n_A]P_B + [2^371 * n_A]Q_B instead. If
n_A is even, then the
factor on the second
Q_B will be divisible by
2^372 and the term will
multiply to zero, giving her the same shared secret as Bob. Otherwise, they
will get different shared secrets.
Let us assume that Alice's
n_A was odd, so the low bit is 1 (in practice it
is always 0, but whatever). Now we can repeat the process, but with Bob sending
Q_B - [2^370]Q_B, P_B + [2^370]Q_B.
Q_B - [2^370]Q_B + [n_A]P_B + [2^370 * n_A]Q_B.
We know her low bit is one, so the
-[2^370]Q_B term will cancel out with one
Q_B + [n_A]P_B + [2^370 * (n_A - 1)]Q_B, where
n_A - 1 is even. So now the rightmost
Q_B term will vanish to zero (giving
Alice the same shared secret as Bob) if and only if
n_A - 1 is divisible by 4;
that is, if the second-lowest bit of
n_A is 0.
This is the procedure: lower the exponent of the rightmost
Q_B term depending
on the bit we're trying to find out, and cancel out the bits we know about by
subtracting them from the leftmost
Q_B term. Repeat until we have almost all
of the bits of
n_A (the last bits are hard to detect for mechanical reasons).
We have now effectively recovered Alice's private key!
Googling the challenge name should lead teams to the OpenSSL
which enables support of SIDH key exchange. Once they downloaded and patched
OpenSSL, they should be able to reach the site using openssl
anything else linked against OpenSSL. Brownie points if you managed to compile
your actual browser to be able to view the site, although it's not necessary.
There's nothing useful on the site; all the pages are static html and contain nothing interesting. We just put a POST form asking for flags on the site so that people would be pretty sure that the packet capture contained the flag itself.
However, the site itself is good as an SSL key exchange success oracle. By negotiating SSL using specific faulty key exchange parameters and checking for garbled data, it is possible to recover one bit of the server's private key per connection. See the paper linked above for details, or read the code in this repo. Because the site's server reuses the private key every time, doing this ~372 times allows you to recover the private key fully, modulo one or two high bits .
The ultimate goal is to decrypt the pcap using the server private key that was extracted with the oracle attack; once you know that, you can combine that with the client public key from that session to generate the SSL master key and from there decrypt all data in the pcap. Then you see the client says this to the server:
POST /submit.html HTTP/1.1 Content-Length: ... Content-Type: application/x-www-form-urlencoded flag=...
And you're done! No sweat (?)
Thought process we were looking for:
"OK so the site contents seem to be useless. We're using TLS, so it's probably not a protocol problem. This is crypto not pwning. SIDH is the only thing weird about the crypto setup and it's in the name+url... are there any known vulnerabilities in, uh, SIDH key exchange?"
Yes, there are!
Searching for things like "supersingular isogeny diffie hellman attack" quickly find a paper which lists a few ways for the protocol to be softened:
In this section, we will assume that Alice is using a static key (a1, a2), and that a dishonest user is playing the role of Bob and trying to learn her key
SOLVING THE ISOGENY PROBLEM WHEN THE ENDOMORPHISM RING IS KNOWN
In this section we additionally suppose that we know (or can compute) the endomorphism rings End(E) and End(EA) [...]
ISOGENY HIDDEN NUMBER PROBLEM
In this section we present an algorithm that takes partial information about the shared j-invariant j(EAB) of Alice and Bob, and recovers the entire j-invariant, i.e. their shared key. This algorithm can therefore be used as a tool to obtain the shared key from a side-channel attack and to prove a bit security result
"Number 2 seems really really mathy, and they're using the same curve as that
published Microsoft Research patch, so it's unlikely to be vulnerable to
something that depends mostly on the curve E. Hopefully it's not that!"
"Number 3... oh god, they don't want us to do a side channel attack on
post-quantum ECC, do they??"
"Number 1... well we can at least check easily if Alice (server) is using a
static private key by seeing if the SSL public key handshake is always the same"
"OK so if we can find the private key (the attack lets us do that), we should be able to figure out the SSL master secret and decrypt EVERYTHING in the pcap! Let's see what's in there!"
And then you bang your head against elliptic curve math (in C) for like 18 hours.
Problems with this challenge
No teams solved this challenge at BKP2017, which is unfortunate. Here's some problems we identified with the challenge when we ran it:
- It's very hard. You have to find a vulnerability in an obscure protocol on
elliptic curves, then implement it, which is highly nontrivial. Once you've
done that, you have to then get something to decrypt the pcap which basically
involves manually patching the pcap to trick
wiresharkinto thinking it's something ECDHE-RSA-AES128-GCM-HMAC so it can decrypt the block cipher correctly.
- Implementing also takes a while. A team we contacted figured out the vulnerability with 9 hours left in the CTF and did not think they would be able to complete the attack in time (probably true). This was a launch challenge for our 48 hour CTF for a reason.
- 600 points is our traditional "unbounded difficulty" point value, but it was a step above the previous hardest crypto challenges. Another challenge this year ended up being 750 points with several solves, so based on that point value this could have been more like 900 or even 1000 (our point values this year were all over the place anyway).
- At least one team determined that it was so hard that probably nobody would solve it, so it was a bad time investment to try very much at it. This turned out to be the correct strategy, which is totally lame.
- Finding the vulnerability proved to be more subtle than expected. Several high-level teams we expected to have a real shot at solving it didn't manage to find the paper we pulled the attack from. They may have assumed that the lack of any server code provided meant they could assume the server wasn't doing anything especially unusual (except for providing a bizarre ciphersuite).
- If we could run this challenge again, we would probably include several ssl sessions in the pcap to lead people down the 'reused key exchange' route, or maybe even make the key reuse obvious from the description. Another possibility would be to have the teams implement a custom protocl instead of using SSL, which would encourage them to notice the reused server public key.
See code in this repo. We used:
- the standalone SIDH library from the same Microsoft Research group as the openSSL patch
- the OpenSSL patch
shto drive everything
First, when developing, we simulated this attack entirely locally using the SIDH
library. The testing code is in
local_attack.c; some of it made it into our
For the actual full attack solution, we patched openssl to support SIDH in a
client binary, using
s_client to connect to the server. Then we added some
code to optionally modify the public key just before it goes out on the wire
based global variables that were set by new flags to
s_client. If the
modifications to the public key do not change the shared secret calculated by
the server, then
s_client will succesfully handshakel; otherwise it will fail
(it forgets the modified public key when it sends it, so it does shared secret
calculations based on the unmodified public key, just like the attack in the
This was driven by a
python script that did the logic of keeping track of
which bits had been determined and checked for inconsistencies along the way.
While checking for inconsistencies (and thus doing twice as many queries as is
necessary), this took about 5 minutes locally and 12 minutes against the
server at the beginning of the ctf. While preparing this writeup, it took more
like 30 minutes to run against the production ctf server, for unknown reasons.
Solution is still feasible in 15 minutes, almost all network time, by disabling
the consistency checks.
After we had the private key from the server, we scripted
tshark to extract
the client public key from the session in the pcap, and used that + the
standalone SIDH binary to compute the ssl pre-master key from the pcap.
tshark needs the actual master key to decrypt the session, so
we wrote a quick
python script to go from pre-master to master under our
ciphersuite, feeding it the client + server randoms as well, which were also
Finally, we have the master secret and
tshark can decrypt the session! But we
couldn't figure out how to get it out of
tshark's normal interface so we just
had it debug log to a file and then parsed it with a hacky
python script. You
can also just open the pcap in
wireshark and poke around the interface until
you find the decrypted data.
attack.sh- Full attack driver
util/attack- Uses openssl oracle to determine server private
util/openssl- Precompiled openssl oracle
util/extract- Precompiled SIDH/extract.c
util/generate_master_key- Premaster, client, server rand => master secret
tsharkplugin from the internet
SIDH/- Microsoft Research library
SIDH/local_attack.c- local (serverless) PoC - not needed for attack
SIDH/extract.c- Client pubic, server private => premaster
patches/sidh-1.0.2k.patch- Patch openssl
1.0.2kto support SIDH
patches/server.patch- Patch server further to reuse private SIDH key
patches/client.patch- Patch client further, to act as SIDH oracle
data/accesslog.pcap- Packet capture from competition
conf/nginx.conf- For running nginx server
Dockerfile- For running nginx server, expects cert in data/
site/- Static html served by nginx server
 We forward-ported the patch to work with
OpenSSL 1.0.2k and remade the
patches so that we hopefully wouldn't be vulnerable to any nasty old OpenSSL
bugs on the server. The updated patch is in the patches/ directory.
 It turns out the top bit or so of the private key doesn't seem to really change the shared secret calculated. So you can't fully determine the private key, but you can determine it enough to get the shared secret. And you can always brute force 1-4 bits trivially offline if it's a problem. We deliberately left most of the high bits off of our server private key so that solvers that ran into trouble near the end would by default get the right key if they gave up around bit 370.