HITCON CTF QUALS 2016 – PAKE / PAKE++ (Crypto 250 + 150)


Summary: attacking password-based key exchange schemes based on SPEKE with MITM.

In these two challenges we were given a service which simply sends a flag after a session of some Password Authenticated Key Exchange (PAKE) scheme.

PAKE (The first challenge)

  fail unless is_safe_prime(p)
  # each password is an integer in 1..16
  passwords = IO.readlines('passwords').map(&:to_i)
  fail unless passwords.grep_v(1..16).empty?
  fail unless passwords.size == 11
  passwords.map!{|pass| Digest::SHA512.hexdigest(pass.to_s).to_i(16)}
  key = 0
  puts "p = #{p}"
  passwords.each.with_index(1) do |password, i|
    puts "Round #{i}"
    w = pow(password, 2, p)  # NO to Legendre
    b = 2 + SecureRandom.random_number(p - 2)
    bb = pow(w, b, p)
    puts "Server send #{bb}"
    aa = gets.to_i
    if aa < 514 || aa >= p - 514
      puts 'CHEATER!'
    k = pow(aa, b, p)
    key ^= Digest::SHA512.hexdigest(k.to_s).to_i(16)
  flag ^= key
  puts "Flag is (of course after encryption :D): #{flag}"

The server has 11 very small password – integers from 1 to 16. For each password a simple Diffie-Hellman key exchange is done, however the generator depends on the password (this is SPEKE protocol). Then all the resulting keys for all passwords are xored.

Clearly, we can’t guess all the keys at once. On the other hand, if we don’t guess even a single key, the final key is xored with something “random” to us, something about what we don’t have any information at all. From this point of view this challenge looks unsolvable and I was stuck on it for the whole day. The challenge author even increased the points from 150 to 250 since nobody solved it for some time.

The key idea is that we can do a Man-In-The-Middle attack here, between the server and… the server itself! Indeed, the server is the only “person” who knows the passwords and can pass the protocol in a meaningful way. We can maintain two connections and for each password $p$ we will exchange the $g_p^a$ and $g_p^b$ send to us by the server in two connections. Then they will obtain same secret for each of the passwords: $g_p^{ab}$ and the same final master key too!

It is cool that we managed to connect the server to itself, but.. the flag is still encrypted… However, now we can perform attacks on single passwords! Indeed, if we guess a password $p$ correctly, then we can compute the generator $g_p$ and perform the basic MITM attack against classical Diffie-Hellman. For example, we allow the servers to exchange keys related to the first 10 passwords, and then for the 11-th password $p$ we try to guess it and send $g_p^1$ to both servers. Then the servers will compute 11th shared keys $g_p^{a}$ and $g_p^{b}$ which they have already sent to us. Now, the final xor of the keys will be different on two servers. However, if our password guess was correct, we can unxor the last shared keys and see that the new shared keys are now equal. Thus we have obtained a way to bruteforce each password separately.

Here is solution script (takes a while due to heavy PoW):

import os
from hashlib import sha512, sha1
from libnum import *
from sock import Sock
def getHashes(p1, p2):
    # bruteforce proof-of-work in C
    data = os.popen("./sha1 '%s' '%s'" % (p1, p2)).read()
    return data.split()
def numhash(n):
    return s2n(sha512(str(n)).digest())
p = 285370232948523998980902649176998223002378361587332218493775786752826166161423082436982297888443231240619463576886971476889906175870272573060319231258784649665194518832695848032181036303102119334432612172767710672560390596241136280678425624046988433310588364872005613290545811367950034187020564546262381876467
pws = [8, 15, 9, 15, 7, 7, 13, None, 10, 15, None]
pws = [None] * 11
for pwi in xrange(11):
    if pws[pwi] is not None:
    for pwc in xrange(1, 17):
        print pwi, pwc, "getting prefixes"
        f1 = Sock(" 20431")
        f2 = Sock(" 20431")
        prefix1 = f1.read_until_re(r"prefix: (\S+)").decode("base64")
        prefix2 = f2.read_until_re(r"prefix: (\S+)").decode("base64")
        sol1 = sol2 = getHashes(prefix1, prefix2)
        recnum1 = None
        recnum2 = None
        for i in xrange(11):
            num1 = int(f1.read_until_re(r"Server send (\d+)"))
            num2 = int(f2.read_until_re(r"Server send (\d+)"))
            if i != pwi:
                gp = pow(numhash(pwc), 2, p)
                recnum1 = numhash(num1)
                recnum2 = numhash(num2)
        f1.read_until("Flag is")
        f2.read_until("Flag is")
        res1 = int(f1.read_until_re(r": (\w+)"))
        res2 = int(f2.read_until_re(r": (\w+)"))
        if res1 ^ recnum1 == res2 ^ recnum2:
            print "MATCH!", "pw[%d] = %d" % (pwi, pwc)
            pws[pwi] = pwc
            print pws

After we have obtained the all passwords, we can implement the legitimate session and get the flag: hitcon{73n_w34k_p455w0rd5_c0mb1n3d_4r3_571ll_wE4k_QQ}

Pake++ (The second challenge)

In the second challenge, the scheme was slightly altered. There are now 8 different prime moduli, each time the prime to be used is chosen at random. Also there is only one password and it has very high entropy. Finally, we have two rounds at each time. Each round a different prime is chosen, but the password is always the same.

  primes = <<-EOS.lines.map(&:to_i)
  fail unless primes.all?{|p| is_safe_prime(p)}
  password = IO.read('password2').strip
  fail unless password =~ /\A[a-zA-Z0-9]{20}\z/
  password = Digest::SHA512.hexdigest(password).to_i(16)
  key = 0
  2.times do |i|
    puts "Round #{i + 1}"
    p = primes[SecureRandom.random_number(primes.size)]
    puts "p = #{p}"
    w = pow(password, 2, p)  # NO to Legendre
    b = 2 + SecureRandom.random_number(p - 2)
    bb = pow(w, b, p)
    puts "Server send #{bb}"
    aa = gets.to_i
    if aa < 514 || aa >= p - 514
      puts 'CHEATER!'
    k = pow(aa, b, p)
    key ^= Digest::SHA512.hexdigest(k.to_s).to_i(16)
  flag ^= key
  puts "Flag is (of course after encryption :D): #{flag}"

Now that we know the MITM idea, it is not much harder. If we manage to get the the same primes in two connections and simply exchange the values sent, we will get same key in both connections. Even if the keys are different, we can’t get the flag from having $flag \oplus stuff1$ and $flag \oplus stuff2$. For example, if we xor these two things together, the flag is cancelled. To avoid this we simply add the third connection! Then triple xor of $flag \oplus stuff$ will still have $flag$ and hopefully we can cancel all the stuff.

Indeed, we can try to make the following key exchanges between connections $a, b, c$:

k_1 = key\_exchange(a, b), \\
k_2 = key\_exchange(a, c), \\
k_3 = key\_exchange(b, c).

Then we will get:

flag \oplus k_1 \oplus k_2 ~\mbox{from}~ a, \\
flag \oplus k_1 \oplus k_3 ~\mbox{from}~ b, \\
flag \oplus k_2 \oplus k_3 ~\mbox{from}~ c.

Xoring everythin results in the flag!

There are some technicalities. We need to distribute these three exchanges between all 2 rounds in all 3 connections. This is easy, since the servers not necessarily need to exchange in the same round.

A slightly harder problem is to wait until the primes match in a right way. We can do the following:

  1. Open several connections until there is a pair of connections with the same prime $p_{ab}$ in the first round.
  2. Perform the exchange between them.
  3. See the second round primes $p_a$ and $p_b$.
  4. Find a client in the pool or make new connections until we get a connection with the first round prime equal to either $p_a$ or $p_b$.
  5. Perform the exchange between the corresponding connections.
  6. Now we have no choice and only one exchange left to do. If the primes do not match, we repeat the full algorithm.
  7. Otherwise, we get the flag.
    • The flag: hitcon{m17m_f0r_pr0f1t_bu7_S71ll_d035n7_kn0w_p455w0rd}

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>