생초보 pwnable.kr - coin1 write-up

필요 지식

---

 1. Binary Search

이진 탐색은 정렬된 배열에서 특정 값을 찾을 때 사용되는 알고리즘입니다.

위 그림처럼 배열이 정렬된 있을 때 가장 큰 값에 high 작은 값에 low를 두고 중간값에 middle을 둡니다. 그리고 middle값과 탐색하는 값과 비교해서 탐색값이 작을 경우 middle값을 high로 바꾸어주고 middle값을 다시 그 중간값으로 세팅해 주면서 탐색해 나갑니다. 탐색값이 middle값보다 클 경우 반대로 middle이 low가 되겠죠.

이진 탐색은 한번 비교할때마다 남아있는 탐색 해야 될 공간이 1/2씩 줄어듭니다. 따라서 시간복잡도는 O(log n)을 가지게됩니다. 정렬된 배열에 대해 탐색할 때 상당히 빠른 알고리즘입니다.

 

Write-Up

---

안녕하세요! 오늘은 6점짜리 coin 1문제입니다.

이번에는 게임 형식의 문제 같습니다. nc로 들어가 보겠습니다.

음 게임 내용은 N개의 코인 중에 위조 코인이 하나 들어있고 C번의 기회 중에 찾아내야 하는 게임입니다. 각 인덱스에 해당하는 코인을 물어보면 코인의 무게를 주는데 무게가 위조코인만 9이고 나머지는 10이네요. 그리고 이거을 100번을 풀면 flag를 주는 모양이네요. 게다가 60초 시간제한까지 있습니다. 

몇 번 시도해 보면 아시겠지만 손으로 입력해서는 도저히 풀 수 없는 문제가 대부분입니다. 그래서 여러 가지 생각해 보다가 처음에는 마이너스 값이 입력되길래 이쪽에 뭔가 코드가 잘못 짜여 있나 생각해서 시도해 보고 고민했는데 도저히 안 나오더군요.

그러던 중 N과 C가 나오는 값의 패턴을 보니 N은 1000을 안 넘기고 C는 10까지만 나오더군요. 아 그래서 이진 탐색으로 찾으면 답을 찾을 수 있겠구나 생각했습니다. 그래서 pwntool을 이용해 파이썬 코드를 짜보았습니다.

from pwn import *

p = remote("0",9007)

p.recv()

for i in range(100):
    p.recvuntil("N=")
    N = int(p.recvuntil(" "))
    p.recvuntil("C=")
    C = int(p.recvuntil("\n"))
    
    t = 0
    low = 0
    high = N-1
    while t < C:
    	middle = (low + high)/2
        inject = ' '
        for j in range(low, middle + 1):
        	inject += str(j)
        	inject += ' '
        p.sendline(inject)
        ans = int(p.recv())
        if ans%10 == 9:
        	high = middle
        else:
        	low = middle + 1
	t +=1
    middle = (low + high)/2
    p.sendline(str(middle))
    print(p.recv())

print(p.recv())

코드 설명을 간단히 하면 N, C를 받고 그에 따라 low, high, middle을 정한 후 middle 보다 작거나 같은 수로 입력해 줄 스트링을 만들고 그 안에 위조 코인이 있는지 없는지를 %10 해서 9가 나오면 위조 코인이 있는 것이고 0이면 없는 것으로 판단합니다. 그 후 이진 탐색으로 이 과정을 반복해서 구해줍니다. 

After Review

---

이진 탐색 알고리즘을 알면 풀 수 있는 문제였습니다. 그런데 저는 '아 그래도 뭔가 취약점이나 코드 상 오류가 있지 않을까'라고 생각해서 주야장천 여러 가지 방법을 시도해 보았네요. 이건 좀 시간 아까운 삽질이었습니다. 원래 처음에는 C로 코딩해서 입력값을 주는 프로그램을 만들라 했는데 파싱 하는 거랑 입력해 줄 스트링을 만드는 게 너무 귀찮고 힘들어서 그냥 python으로 풀었습니다. 혹시 나중에 시간 되거나 하면 c로 다시 만들어 보겠습니다.

감사합니다.