[Pwnable.kr] coin1 풀이 (6pt)

풀이

주어진 서버로 접속해보자.

이번 문제는 N개의 코인 속 안에 있는 1개의 위조 코인을 C번의 저울질을 이용해 찾아내는 문제다.

널리 알려져있는 저울 문제는 양팔 저울을 이용하지만 이 문제에서는 한팔 저울을 이용한다.

총 100개의 위조 코인을 발견하면 보상을 얻을 것이라고 한다.

코인 N개에 대해 주어지는 기회 C번은 $C\,=\, log_{2}{n} $다.

 

---

이번 문제는 이진 탐색을 이용해 문제를 해결할 수 있다.

다음을 예시로 들어보도록 하자. (코인은 0번부터 시작함)

 

코인: 100개, 기회: 7번 위조 코인: 87번

first = 코인 시작 넘버, last = 코인 마지막 넘버

 

1번째

first = 0, last = 50

0 - 50 사이에는 위조 코인이 없음.

 

2번째

first = 51, last = 75

51 - 75 사이에는 위조 코인이 없음.

 

3번째

first = 76, last = 88

76 - 88 사이에 위조 코인이 있음!

 

4번째

first = 76, last = 82

76 - 82 사이에는 위조 코인이 없음.

 

5번째

first = 83, last = 85

83 - 85 사이에는 위조 코인이 없음.

 

6번째

first = 86, last = 87

86 - 87 사이에 위조 코인이 있음!

 

7번째

first = 86, last = 86

86번은 위조 코인이 아님.

 

결국, 87번은 위조 코인임

---

이진 탐색을 기반으로한 페이로드는 다음과 같다.

참고로, 원격으로 프로그램을 실행하면 속도가 엄청 느리다.

pwnable.kr 서버에 ssh로 접속해서 local에서 실행하면 빠른 속도로 값을 얻을 수 있다.

import time
from pwn import *

p = remote('localhost', 9007) #in pwnable.kr server
for i in range(0,31):
    arr = p.recvline()
time.sleep(3)

for qwer in range(0,100):
    arr = p.recvline().split(' ')
    coins = int(arr[0][2:])
    chances = int(arr[1][2:-1])

    first = 0
    mid = int((coins - first)/2) 
    last = first + mid #51
    pandan = (last - first + 1) * 10 

    payload = list(range(0, mid + 1))
    payload = " ".join(map(str, payload))
    p.sendline(payload)

    for i in range(0, chances):
        p_value = int(p.recvline())

        mid = int((last - first)/2) 

        if pandan == p_value:
            first = last + 1 

        last = first + mid

        pandan = (last - first + 1) * 10
        payload = list(range(first, last + 1))
        payload = " ".join(map(str, payload))
        p.sendline(payload)

    print p.recvline()

print p.recvline() #get flag
print p.recvline() #get flag