ColdwaterQ



Boston Key Party Airport (Crypto 500)

by: ColdwaterQ on March 7 2015

The challenge that I found the most enjoyable, and as such wanted to write about from the Boston Key Party was Airport (Crypto 500). This challenge’s hint made it clear that the goal was to do some kind of timing attack. It said:

The timing in this challenge is clearly not very realistic---but the methods you'll use here can be extended to real-world implementations of modular exponentiation. Server at 52.1.245.61, port 1025. My solution takes a little while. Good luck.

Along with the hint, the code which is being run on the server was also supplied, and so the challenge was to figure out how to get the code to progress down the correct path to return the flag. The full source can bee seen at the bottom of this page if you want to view it(here), and I will include snippets that go with what I am talking about throughout this post.

The three methods that pop out first are exponentiate, handle, and captcha.

def handle(self):
    self.captcha()
    while True:
        self.exponentiate()
    self.request.close()

def captcha(self):
    proof = base64.b64encode(os.urandom(9))
    self.request.sendall(proof)
    test = self.request.recv(20)
    ha = hashlib.sha1()
    ha.update(test)
    if test[0:12]!=proof or not ha.digest().endswith('\xFF\xFF\xFF'):
        self.fail("You're a robot!")

def exponentiate(self):
    base = int(self.request.recv(1024))
    if not group_check(SAFEPRIME, base):
        self.fail("Bad group element.")
    result = slowpower(base, self.SECRET, SAFEPRIME)
    if result != 4:
        self.request.sendall(str(result))
    else:
        self.request.sendall(FLAG)

The exponentiate method returns the flag, so that is what I need to get called, handle calls captcha then exponentiate over and over, so I need captcha to succeed, then I can focus on exponentiate.

Captcha causes the server to send us 12 bytes, which are 9 random bytes base64 encoded. We must take the 12 bytes and determine what we can add to it to cause a sha1 hash of the whole thing to end in ‘\xFF\xFF\xFF’. The whole blob that generates the hash then needs to be sent back to the server. If the blob works, we continue, otherwise the connection is closed. We used the following code to bypass this hurdle, there are probably better ways to do it, but this was good enough and let us move onto the real problem.

sha_beginning = s.recv(12)
def hash(start, depth):
    for i in range(0,256):
        if depth == 0:
            ha = hashlib.sha1()
            ha.update(start+chr(i))
            sha1 = ha.digest()
            if sha1.endswith('\xff\xff\xff'):
                return start+chr(i)
        else:
            ret = hash(start+chr(i), depth - 1)
            if ret != None:
                return ret
    return None

answer = hash(sha_beginning, 6)
ha = hashlib.sha1()
ha.update(answer)
s.send(answer)

Now the real work begins of getting exponentiate to return the flag. The code bellow is all of the code necessary to understand to solve the rest of the problem.

# Trimmed, but trust me it is big and prime
SAFEPRIME = 273273...5727L

def exponentiate(self):
    base = int(self.request.recv(1024))
    if not group_check(SAFEPRIME, base):
        self.fail("Bad group element.")
    result = slowpower(base, self.SECRET, SAFEPRIME)
    print result
    if result != 4:
        self.request.sendall(str(result))
    else:
        self.request.sendall(FLAG)

def slowpower(base, power, mod):
    accum = 1
    for bit in bin(power)[2:]:
        if accum == 4:
            time.sleep(1.0)
        accum = accum*accum % mod
        if bit == '1':
            accum = accum*base % mod
    return accum

self.SECRET = rand_exponent(SAFEPRIME)

while True:
    self.exponentiate()

Exponentiate is called over and over as long as group_check does not fail. I did not include group_check because once I figured out how to solve slowpower all my answers went past group_check as well. So The goal is to provide a number that will cause slowpower to return a 4. The self.Secret is generated for each connection so that is an unknown, but SAFEPRIME is a very large static prime number which was included in the server source.

Looking at slowpower we see that a variable accum starts at one. Then each bit of the secret is enumerated. And for each bit accum is squared, and then if the bit is one accum is also multiplied by base. Also every operation done on accum is modded by SAFEPRIME. Since only multiplication is happening in the loop, all of the mod operations can be pulled outside the loop, and the result will be the same. It is also important to realize that when accum is 4 the function sleeps for a second. After analyzing the function it becomes clear that the goal is to figure out the secret through repeated guesses that take advantage of the sleep so that eventually we have a number that will result in 4 being returned and us winning.

To solve this we considered base to be x, and thought about what various numbers as the secret would mean for x. Bellow is a table that show secrets compared to the value of accum in terms of x. Remember that since mod SAFEPRIME has been pulled outside the loop we don’t have to consider that for now. We are just considering what the multiplication means.

secret bin(secret) accum
1 1 x
2 10 x^2
3 11 x^2*x=x^3
4 100 (x^2*x)^2=x^6
5 101 (x^2*x)^2*x=x^7

What the pattern is, is that for every bit added to bin(secret) the exponent is doubled from the previous exponent. And if the bit is a one the exponent has one added to it on top of being doubled. So in order to take advantage of the sleep(1.0) we start with checking if the first bit is one or zero. If the first bit is one then the x where x%SAFEPRIME=4 will cause the program to wait a second.

Since we know bit one is always 1 we can continue to bit two. If bit two is 0 then x where x^2%SAFEPRIME=4 will cause the program to wait a second, and if that bit was one then the x where x^3%SAFEPRIME=4 will cause the program to wait. Assuming it was one, then if the x where x^6%SAFEPRIME=4 causes the program to wait then the third bit is 0, otherwise it is one. This can be continued to find all the bits of the secret, and more importantly for us, the last value of x will cause the server to return the flag.

Now since there are many bits in the secret we need a programmatic way to solve for x given n such that x^n%SAFEPRIME=4. Keep in mind that SAFEPRIME is a constant so there is one variable we set, and one we solve for.

This is not an easy function to solve though, and we had no idea how to solve this programmaticly but after much googling we found this post on xkcd. http://forums.xkcd.com/viewtopic.php?f=17&t=73708#p3148049. It states the following:

Let y = g^x mod m
Let ux = 1 mod φ(m), where φ() is Euler's totient function.
Then g = y^u mod m

In this case we want to solve for g, and so if we can find u we have our solution. So we just need a programmatic way to solve the second function for u and we have the answer. As it happens the second function is a Modular multiplicative inverse and had to be solved for a different challenge in the CTF so we took the code for that. Then a bit more Google to find that φ(m) when m is prime is m-1. Put this all together and we get the following code.

def find_val(xs):
    return pow(4 ,modinv(xs, p-1), p)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

In this code p is SAFEPRIME, and calling find_val(xs) where xs is the exponent will return the value of what we called x but which was called g in xkcd, which is what we need to send to the server. One problem though, if xs is even the code fails. So we could only check odd numbers. Or in other words, we could only check for bits that are 1. Luckily if the bit isn’t 1 we know it is 0 so that is no big deal.

The whole attack script works as follows. We break captcha with shear strength. Then we start with the exponent of 3, since we already know that bit 1 is a one. So we solve x^3%SAFEPRIME=4 for x. We send that x to the server and if the server waits a second, then we know the second bit is a 1, if the server doesn’t wait a second we know the second bit is a 0. If the bit was a one we multiply the exponent by two and add one, and repeat. If the bit was a 0 we subtract one, multiply the exponent by two, and add one. In this way the exponent never has to be even, and we are able to figure out what the correct exponent should be one bit at a time. The code had to request things that seemed to take one second twice because of the occasional false positive from lag, and we had to increase the size of the stack for the find_num function to work near the end. The code that is solving for the correct exponent is below, and is combined with the cpatcha smasher to make our solution.

xs = 3
first = False
while cont:
    t = time.time()
    s.send(str(find_val(xs)))
    ret = s.recv(9999)
    print ret
    if '\n' in ret:
        cont = False
    a = time.time()-t
    print str(a)+' '+str(xs)
    if a>1:
        if first:
            xs = xs*2+1
            first = False
        else:
            first = True
    else:
        first = False
        xs = (xs - 1)*2+1

After letting this code run for a decent while we had the password which was:

diffie_hellman_im_awfully_fond_of_youuuuuu

The code given to us by the CTF and the code we wrote are both bellow in full.

Provided Source
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#!/usr/bin/python

import time
import random

def slowpower(base, power, mod):
    accum = 1
    for bit in bin(power)[2:]:
        if accum == 4:
            time.sleep(1.0)
        accum = accum*accum % mod
        if bit == '1':
            accum = accum*base % mod
    return accum


SAFEPRIME = 27327395392065156535295708986786204851079528837723780510136102615658941290873291366333982291142196119880072569148310240613294525601423086385684539987530041685746722802143397156977196536022078345249162977312837555444840885304704497622243160036344118163834102383664729922544598824748665205987742128842266020644318535398158529231670365533130718559364239513376190580331938323739895791648429804489417000105677817248741446184689828512402512984453866089594767267742663452532505964888865617589849683809416805726974349474427978691740833753326962760114744967093652541808999389773346317294473742439510326811300031080582618145727L
# generated with gensafeprime.generate(2048)
# https://pypi.python.org/pypi/gensafeprime

GENERATOR = 4

FLAG = ''

def rand_exponent(p):
    return random.randrange(1, (p - 1)/2)

def group_check(p, m):
    if m <= 0:
        return False
    elif m >= p:
        return False
    elif pow(m, (p-1)/2, p) != 1:
        return False
    else:
        return True


import base64, SocketServer, os, sys, hashlib

class ServerHandler(SocketServer.BaseRequestHandler):

    def fail(self, message):
        self.request.sendall(message + "\nGood-bye.\n")
        self.request.close()
        return False

    def captcha(self):
        proof = base64.b64encode(os.urandom(9))
        self.request.sendall(proof)
        test = self.request.recv(20)
        ha = hashlib.sha1()
        ha.update(test)
        if test[0:12]!=proof or not ha.digest().endswith('\xFF\xFF\xFF'):
            self.fail("You're a robot!")

    def exponentiate(self):
        base = int(self.request.recv(1024))
        if not group_check(SAFEPRIME, base):
            self.fail("Bad group element.")
        result = slowpower(base, self.SECRET, SAFEPRIME)
        if result != 4:
            self.request.sendall(str(result))
        else:
            self.request.sendall(FLAG)

    def setup(self):
        self.SECRET = rand_exponent(SAFEPRIME)

    def handle(self):
        self.captcha()
        while True:
            self.exponentiate()
        self.request.close()


class ThreadedServer(SocketServer.ForkingMixIn, SocketServer.TCPServer):
    pass

if __name__ == "__main__":
    HOST = sys.argv[1]
    PORT = int(sys.argv[2])

    FLAG = open('flag.txt', 'r').read()

    server = ThreadedServer((HOST, PORT), ServerHandler)
    server.allow_reuse_address = True
    server.serve_forever()
  
Personal source
import socket
import hashlib
import time
import sys
# p is the SAFEPRIME, but it is so big it gets anoying
from test import p
sys.setrecursionlimit(100000)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def find_val(xs):
    return pow(4 ,modinv(xs, p-1), p)

cont = True
while cont:
    s = socket.create_connection(('52.1.245.61',1025))
#    s = socket.create_connection(('localhost',8000))
    sha_beginning = s.recv(12)
    def hash(start, depth):
        for i in range(0,256):
            if depth == 0:
                ha = hashlib.sha1()
                ha.update(start+chr(i))
                sha1 = ha.digest()
                if sha1.endswith('\xff\xff\xff'):
                    return start+chr(i)
            else:
                ret = hash(start+chr(i), depth - 1)
                if ret != None:
                    return ret
        return None

    answer = hash(sha_beginning, 6)
    print 'sent:'
    print answer.encode('hex')
    s.send(answer)
    xs = 3
    first = False
    while cont:
        t = time.time()
        s.send(str(find_val(xs)))
        ret = s.recv(9999)
        print ret
        if '\n' in ret:
            cont = False
        a = time.time()-t
        print str(a)+' '+str(xs)
        if a>1:
            if first:
                xs = xs*2+1
                first = False
            else:
                first = True
        else:
            first = False
            xs = (xs - 1)*2+1
    s.close()

In order to see write ups for more challenges completed by others on Neg9 check out the neg9 site.