[pwnable.kr] Toddler's Bottle - coin1

[pwnable.kr] Toddler’s Bottle – coin1

 

 

 

  

 

N개의 동전 중 1개의 위조 동전이 껴 있는데, C번의 기회 안에 위조 동전을 알아내야합니다.

 

처음에는 한 번만 맞추면 되는 줄 알았습니다.

 

 

그래서 수작업을 시도했다가 교육 한 번 당했으니, 코드를 짜도록 하겠습니다.

 

일단 2000명의 관람객 중 도둑이 보석을 도둑질하고 다른 색깔의 보석을 끼워 넣었다. 적어도 몇 번 “보석은 무슨 색이었습니까?”를 물어봐야 찾을 수 있나? 라는 문제와 비슷한 것 같습니다.

 

이진 탐색은 정렬되어 있어야 하고, 시간 복잡도가 log N입니다.

 

 

from pwn import *
import time
 
host = "pwnable.kr"
port = 9007
 
con = remote(host, port)
 
print con.recv()
time.sleep(3)        #starting in 3 sec...
 
 
for i in range(100):    #find 100 counterfeit coins
    con.recvuntil("N=")
    n = int(con.recvuntil(" "))
    con.recv()
 
    print n
    high = n
    low = 1
    coin = -1
    
    while 1:
 
        mid = (low + high) / 2
        num = ""
        #Omission of termination condition
        
        if coin > 0:
            con.sendline(coin)
            print "send : " + coin
        else:
            for j in range(low, mid+1):
                num += "{0} ".format(j)
            print "send : " + num
            con.sendline(num)
        
        recv = con.recvuntil("\n")
        print "recv : " + recv
 
        if recv.find("Correct") != -1:
            break
        elif int(recv) == 9:
            if coin > -1:
                continue
            else:
                coin = num
                continue
        elif int(recv) % 10 != 0:
            high = mid
        else:
            low = mid + 1

 

 

이렇게 이진 탐색을 파이썬으로 구현했습니다. 보통 이진 탐색의 경우, 종료 조건이 low > high or find key입니다. 하지만, coin1은 정렬된 배열의 크기를 key와 비교하는 것이 아닙니다. 그렇기 때문에 종료 조건은 Correct!가 출력될 때입니다.

 

 

하지만, 99까지 밖에 출력되고 멈춥니다.

저는 100번 째 계산이 실행되지 않는 건가? 하고 보니 괄호 안의 숫자는 0~99입니다.

즉, 100번 계산을 마쳤는데 제가 flag를 읽지 않았다는 것입니다.

 

 

    if i == 99:
        print con.recv()

 

그래서 이러한 코드를 추가해줬습니다.

 

 

 

그러면 flag가 출력됩니다!