Blind SQL Injection optimization techniques

우리는 눈으로 볼 수 없는 사물은 X-Ray로 투시하면 사물에 담긴 그 내용물을 볼 수 있다. 병원에서는 의료용으로 많은 도움이 되고 공항이나 보안이 철저한 곳에서는 위험물을 소지 했는지 확인하는 용도로 많이 쓰인다.

경험으로는 국내 S그룹 본관에서 3주가량 프로젝트로 상주게하 되었을 때, 가방이 없으면 허전하기에 매일 출/퇴근 길에 들고 다녔다. 그러나 퇴근할 때는 X-Ray를 이용하여 반출금지 물품을 소지하였는지 매번 확인하며 물리적 보안을 하고 있었다.

이 글의 주제에 해당하는 Blind SQL Injection이 또한 이런거 같다. 그냥 보면 SQL Injection 처럼 DB의 에러 구문이나, 데이터는 볼 수 없지만 우리가 조작한 SQL 구문은 분명 DB에서 실행이 되는 경우이다. 이럴 경우 우리는 머리속으로 화가가 그림을 그리듯 하나하나 유추해 가면서 DB를 획득하게 된다. Blind 방식의 특성상 수작업으로 다량의 데이터를 획득하기에는 매우 어려우며 대부분 자동화 툴을 많이 사용한다.

Blind SQL Injection은 SQL Injection(MSSQL with Error와 Union을 통한 데이터 획득)과 다르게 공격 구문이 DB에서 실행 유무를 이용하여 참/거짓만 판단만이 가능한 환경이다.

이러한 환경에서는 데이터 획득을 위한 비용 적인 측면의 고려가 매우 중요하다. SQL Injection에서는 몇변의 질의(공격)로 DB의 데이터 획득이 가능하지만 Blind 방식에서는 한글자 또는 한 단어 획득을 위해서 수차례의 질의(공격)가 필요하다.

일반적으로 Blind SQL Injection에서는 DB의 데이터를 획득하기 위해 SUBSTRING을 사용하여 단어의 한 글자를 택한 후 해당 단어를 유추하는 방식을 많이 사용한다. 가장 많이 쓰이는 방식이 ASCII 값으로 변환 후 이진탐색(Binary Search)알고리즘을 이용하는 방법이다.

질의어 : select ascii(substring('corea',1,1)) 결과값 : 99

원리를 보면 corea라는 데이터가 있다. 공격자는 이 데이터를 알지 못하는 상황이며 위에서 설명한 바와 같은 방식으로 첫번째 글자의 ASCII 값이 99가 나오도록 질의어를 조작한 후 99라는 값을 찾기위해 다양한 방법을 시도한다. ASCII는 0~127까지의 영역을 사용하며 Binary Search로 검색할 경우 7번정도 질의하면 99라는 값을 획득하게 된다. 여기서 7번의 질의 횟수가 비용이 된다.

Blind SQL Injection에서는 이 비용을 줄이기는 방법이 자동화 툴의 성능을 좌우하는 핵심 기술이 된다. 최적의 비용을 위한 데이터 획득 알고리즘에 대하여 알아보자.



1. DB 데이터 획득 Algorithm

Blind SQL Injection을 통해 데이터 획득을 위한 일반적인 방법으로 순차탐색과 이진탐색 방법이 있다. 물론 여기에서는 DB의 내장 함수 등을 사용하는 방법은 배제하고 서술한다.


1.1 순차탐색(sequential search)

가장 단순한 비교 방법이며 순차적으로 데이터를 입력하여 존재 유무를 확인하는 것으로 비효율 적인 방법이다. 순차탐색은 MySQL 5.0 미만의 버전 등등 메타데이터를 이용하여 DB의 구조 데이터를 제공하지 않거나 질의가 불가한 일부 환경에서 사용되는 방법으로 순차적으로 하나씩 비교하여 해당 데이터가 존재하는지 확인하는 방법이다. 이 방법은 사전을 이용하는 방법과 SUBSTRING을 이용하여 한글자씩 비교하는 방법 등이 있다.


- 사전(Dictionary)을 이용한 방법

사전에 나열된 문자을 순서대로 하나씩 비교하는 방법으로 TABLE 또는 COLUMN 명을 검색할때 유용한 방법이다.

질의어 : (select count(*) from Dictionary_Word)>0 결과값 : 참일 경우 테이블명 존재

위의 방법에서 테이블이 존재할 경우 참인 결과 페이지가 리턴 됩니다. 또한, Count 가 0일 때는 거짓인 결과가 나오나 Data가 없는 테이블 명으로 무의미하다고 할 수 있다.


- SUBSTRING을 이용한 방법

일반적으로 DB의 데이터는 SBCS(Single Byte Character Set)일 경우 ASCII 값의 범위 0~127을 갖습니다. 해당 값을 순서대로 비교하는 방법으로 순차검색만 사용 가능한 환경에서 유효한 방법이다.

질의어 : (select top 1 substring(name,Position,1) from sysobjects)='char' 결과값 : 참일 경우 해당 글자 존재

순차탐색은 리스트의 모든 값을 순차적으로 비교한다는 점에서 매우 비효율 적인 방법임은 분명하다. 그렇다고 불필요한 방법이라고는 할 수 없습니다. 순차 탐색이 아니면 DB 획득이 불가한 환경도 있기 때문에 어느 방법이 유효한지 먼저 따져봐야 할 것이다.


1.2 이진탐색(Binary Search)

이제 Blind SQL Injection에서 최적의 알고리즘인 이진탐색 알고리즘에 대해서 알아 보겠다. 여기서 알고리즘은 동일하지만 환경에 따라서 다양한 방법이 필요할 경우가 많다. 예를 들어 사용자 입력값 필터링이 있을 경우 차단될 확률이 높고 이러한 경우 한가지 방법으로는 원하는 데이터를 모두 획득하기 어렵다.
 
대표적으로 XSS 차단을 위해 ">", "<" 를 필터링 하는 경우 우리는 "=" 연산자만 사용이 가능하며 또는 "=" 연산자만 사용이 불가능한 환경도 있으며 모두 다 사용 가능한 환경도 있다. 이러한 ">","<","=" 중 하나의 연사자만 사용이 가능하다 할지라도 모두 동일하게 이진탐색이 가능하다. 물론 제약 사항이 있어 알고리즘 별로 약간의 속도 차이는 발생하나 대부분 1% 미만의 차이가 나므로 무시해도 무방할 정도이다.

이진탐색의 비용은 2ⁿ의 비용이 발생한다. 즉 ASCII의 0~127의 범위로 2⁸, 즉 최대 8번 질의로 하나의 문자 획득이 가능하다.

비용	1	2	3	4	5	6	7
검색값	64	32	16	8	4	2	1

이진탐색 비용 계산표

여기서 비용은 질의 횟수이며 검색값은 검색을 위한 기준 값으로 비용만큼 증가감을 하면 된다. 그러면 이제 검색 방법에 따른 알고리즘을 알아 본다.

( 여기에서 설명하는 알고리즘은 분활정복(Divide and conquer) 방식으로도 불리나 본 문서에서는 이진탐색으로 통일하여 사용한다. )


- 비교 연산자를 사용하는 방법(Compare)

DB에서의 비교 연사자는 ">","<","="를 사용할 수 있습니다. Compare 방식에서는  ">"와 "<" 연산자 만을 이용하여 DB 획득 알고리즘을 설명한다. "=" 연산자는 여기에서는 사용하지 않는다. 만약 "=" 연사자가 필터링 되어 있는 경우에는 SQL Query 문에서도 "=" 연사자를 사용할 수 없으며, 연산자 모두 사용이 가능할 경우 SQL Query 문은 자유롭게 기술이 가능하다.

예를 들어 단어 "corea"를 이진탐색을 하면 다음과 같은 결과가 나온다. 여기서 "c"의 ASCII 십진수 값은 99이다. 총 5글자 * 7회로 35회의 질의 비용이 발생한다.

1. T : (select ascii(substring('corea',1,1))) > 64 2. T : (select ascii(substring('corea',1,1))) > 96 3. F : (select ascii(substring('corea',1,1))) > 112 4. F : (select ascii(substring('corea',1,1))) > 104 5. F : (select ascii(substring('corea',1,1))) > 100 6. T : (select ascii(substring('corea',1,1))) > 98 7. F : (select ascii(substring('corea',1,1))) > 99 T = True, F = False

일반적으로 이진 탐색을 위해서는 하나의 노드에 도달하였을 경우 분기를 위해 ">","<","=" 등의 비교연산을 수행한다. 하지만 Blind SQL Injection 에서는 최소한의 연산을 해야 비용을 줄일 수 있다. 일반 이진탐색처럼 한번의 분기를 위해서 2번에서 최대 3번까지 비교연산을 수행을 해야 한다면 그 만큼의 질의를 해야 하므로 비용이 2~3배 가량 증가하게 된다. 하지만 특정 값 보다 ">" 또는 "<" 인지 비교하면 True, False 상태를 이용하여 한번에 분기가 가능합니다. 물론, "="인 경우도 있으나 7번의 질의 후에는 결과 획득이 된다.

이러한 비교연사자를 이용한 이진탐색 알고리즘을 조금 수정하여 쉽게 구현이 가능하며 아래는 C#으로 구현한 예시이다.

public long BinarySearch(long left, long right, string sQuery) {         long mid;         // 검색을 위한 중간 값 값 저장         bool bResult;   // 질의 결과(참/거짓) 저장         mid = (left + right) / 2;         bResult = BooleanOperation(sQuery + ">" + (mid - 1))         // ">" 연산자를 이용하여 연산을 수행 mid -1은 ">=" 연산자와         // 동일한 결과 유도를 위해 사용         if ((right - left) <= 1)         {               if (bReuslt) { return right; } else { return left;}         }         // 연산의 차이가 1 보다 같거나 작으면 결과 Return         if (bResult)         {               if (bResult)                { return BinarySearch(mid,right,sQuery);}               else               { return BinarySearch(left,mid,sQuery);}         }         // 재귀 호출 } // long 형 선언은 ASCII 값 외에 데이터의 Count 등등 int형 범위를 벗어난 // 데이터를 찾을 경우 int 형 범위를 벗어 남 BooleanOperation 함수는 질의 결과 참/거짓 판별 함수

- 사칙연산을 사용하는 방법(Divide)

사칙연산을 사용하는 경우는 ">","<" 연사자를 필터링하여 사용 할 수 없을 경우 사용하는 방법이다. 여기에서는 "=" 연산자만 사용이 가능하므로 일반적으로 이진 탐색이 불가해 보이나 사칙연산의 "/"을 이용 이진탐색이 가능하다.

나눗셈 연산의 결과는 몫과 나머지로 나뉘며 여기에서는 몫만을 사용하여야 한다. 예를 들어 피제수(被除數 )보다 큰 제수(除數)로 나눗셈 연산을 하면 0.xx 로 1보다 작은 값이 나오며 1보다 값이 크면 검색하고자 하는 값보다 비교한 값이 크다는 뜻이 된다. Divide를 이용한 이진탐색은 수학의 이러한 특성을 이용한 방법이다.

예를 들어 50 이라는 값을 찾기 위해서는 50/64를 계산하면 0.78으로 몫은 0으로 64보다 찾고자 하는 값이 작음을 알수 있고, 50/32를 계산하면 1.56으로 몫은 1로 32보다 찾고자 하는 값이 크다는 것을 알 수 있다. 여기서는 이진탐색의 중간값(MID)을 제수(除數)에 넣고 계산을 하면 몫이 0인지 확인하면 검색하고자 하는 값이 ">" 또는 "<"를 판별이 가능하며, True / False 를 통한 분기가 가능하다.

기본적인 방법은 위에서 설명한 Compare 방식과 원리는 동일하며 비용또한 거의 유사하게 소요된다.
 
Divide 연산자를 이용한 이진탐색을 위해서는 SQL Query를 대폭 수정이 필요하며 ">","<" 필터링이 있을 경우 SQL Query에서는 "=" 외에는 사용이 불가하다. 그러면 이번에도 단어 "corea" 를 이용하여 이진탐색을 수행하면 다음과 같다.

1. T : (select (case when ascii(substring('corea',1,1))/ 64=0 then 1 else 0 end))=1 2. T : (select (case when ascii(substring('corea',1,1))/ 96=0 then 1 else 0 end))=1 3. F : (select (case when ascii(substring('corea',1,1))/112=0 then 1 else 0 end))=1 4. F : (select (case when ascii(substring('corea',1,1))/104=0 then 1 else 0 end))=1 5. F : (select (case when ascii(substring('corea',1,1))/100=0 then 1 else 0 end))=1 6. T : (select (case when ascii(substring('corea',1,1))/ 98=0 then 1 else 0 end))=1 7. F : (select (case when ascii(substring('corea',1,1))/ 99=0 then 1 else 0 end))=1 T = True, F = False

지금까지 Blind SQL Injection에서 필터링 등의 제약 조건이 있을 경우 우회 방법 알고리즘에 대한 내용과 최소 비용을 구하기 위한 알고리즘에 대해서 알아 보았다.

주제는 optimization techniques에 대한 내용으로 보통 위의 내용을 많이 기술하는거 같다. 아무리 봐도 탐색 알고리즘이 가장 기본적인 최적화 기술이기 때문이다. 하지만 여기에는 탐색 알고리즘 외에 SQL Query 최적화가 추가 이뤄져야 하며 또한 찾고자하는 Data의 특성을 분석해야 한다. 즉 문자열 인코딩 방식별 특성을 연구하면 더 많은 비용을 줄일 수 있다. 즉, DB에서의 처리 비용도 중요하다는 것이다. 그리고 끝은로 네트워크 전송 비용도 고려되어야 한다.

최적화에는 이외에도 다양한 기술이 필요합니다만 여기에서는 알고리즘에 대해서만 기술하였다.

p.s
본 문서에서는 SQL Query에 대해서 자세하게 다루지는 않았습니다. 차후에 SQL Query 편에서 위에서 언급된 환경에서의 Query 문을 다루도록 하겠습니다.