pwnable.kr 11. coin1

 글 쓰다가 날아가서 화가 난다. 이번 글은 짧게 써야겠다. 별로 어렵지도 않다.

 

nc pwnable.kr 9007로 접속하면 가짜 동전 찾기 게임이 나온다. 문제를 읽어보니 딱 봐도 이분 탐색(Parametric Search) 문제이다. 그런나 이 게임을 100번을 통과해야 하는데 제한 시간은 60초이다. 딱봐도 뭔가 Exploitation Code를 작성해서 해결해야 겠다는 생각이 들지 않는가? 사람 손으로 1분 안에 깬다는 것은 불가능하다.

 

 

 

---

1. Parametric Search

 이분 탐색 코드이다. while문의 제한은 C번이다. left는 0, right는 N으로 시작하며 계속해서 범위를 절반으로 줄여 나간다.

    left = 0  
    right = N
    cnt = C
    mid = -1  
  
    while cnt != 0:  
        cnt -= 1  
        s = ""  
        # left부터 mid까지의 sequence를 만듦
        mid = (left + right) / 2  
        for j in range(left, mid):  
            s += str(j)  
            s += " "  
        s += str(mid)  
        print(s)  
        
        # sequence를 보내서 돌아오는 답은 해당 코인들의 무게 합
        p.sendline(s)  
        weight = int(p.recv())  
        print(weight)  
        
        # 무게 합의 일의 자리가 9이면 가짜 코인이 left ~ mid 중에 있다는 것임
        if weight % 10 == 9: 
            right = mid 
            
        # 아니면 mid + 1 ~ right 중에 가짜 코인이 있음
        else: 
            left = mid + 1
	
    # 답은 mid에 있음
    mid = (left + right) / 2
    p.sendline(str(mid))

---

2. Exploitation Code

 지난 7강에서 input 문제를 해결할 때 pwntool을 활용하여 해결했던 기억이 있을 것이다. 이번 문제는 훨씬 쉬우니 코드만 보고도 각 문장이 무슨 일을 하는지 이해할 수 있을 것이다.

from pwn import *  
  
p = remote('pwnable.kr', 9007)  
  
print(p.recv())  
  
for j in range(100):  
    print(p.recvuntil("N="))  
   N = int(p.recvuntil(" "))  
    print(p.recvuntil("C="))  
   C = int(p.recvuntil(" "))  
  
    left = 0  
    right = N
    cnt = C 
    mid = -1  
  
    while cnt != 0:  
        cnt -= 1  
        s = ""  
        mid = (left + right) / 2  
        for j in range(left, mid):  
            s += str(j)  
            s += " "  
        s += str(mid)  
        print(s)  
        p.sendline(s)  
        weight = int(p.recv())  
        print(weight)  
        if weight % 10 == 9: 
            right = mid 
        else: 
            left = mid + 1
 
    mid = (left + right) / 2
 
    p.sendline(str(mid))
    print("Stage " + str(j) + " clear!!") 
    print(str(mid)) 
    print(p.recv()) 
 
print(p.recv()) 

해결