Pwnablekr_Toddlers Bottle_coin1

따로 소스코드를 제공하지는 않는다.

정상 코인의 무게는 10, 가짜 동전의 무게는 9이다. 주어진 N개의 동전 중 가짜 동전의 인덱스를 찾는다. C번 질문할 수 있다.

알고리즘 문제로 보인다. 이분탐색으로 절반씩 무게를 합쳐서 작은 쪽을 택하면 logN만에 찾을 수 있다.

N과 C는 실행시마다 바뀌지만 관찰해본 결과 N은 1001000, C는 910정도의 수를 반복한다. logN으로 찾기 충분해 보인다. 100문제를 풀라고 한다.

from pwn import *
 
def binarysearch(left, right):
 
    global p
    global c
 
    if(left < right):
        mid = int((left + right)/2)
 
        req = ""
        for i in range(left, mid+1):
            req += str(i) + " "
 
        p.sendline(req)
 
        res = p.recvline()
 
        if int(res)%10 ==0:
            left = mid+1
        else:
            right = mid
 
        c -= 1
        return binarysearch(left, right)
 
    elif left == right:
        return left
 
p = remote("localhost", 9007)
 
print(p.recvuntil("- Ready? starting in 3 sec... -"))
 
sleep(4)
 
for t in range(100):
    p.recvuntil("N=")
    num = p.recvline()
    num = num.split(' ')
 
    n = int(num[0])
    c = int(num[1].split("=")[1].split("\\")[0]
 
    result = binarysearch(0, n-1)
 
    for i in range(c):
        p.sendline(str(result))
    p.sendline(str(result))
 
p.interactive()

리모트에서 하면 네트워크가 너무 느려 시간 내로 풀 수 없다. pwnable.kr의 다른 SSH 계정으로 접속하여 로컬에서 실행했다.

flag는 b1NaRy_S34rch1nG_1s_3asy_p3asy 이다.

---

tags: writeup, pwnable, algorithm, binary search