[포너블] pwnable.kr - coin1

pwnable.kr - coin1

 

문제

nc pwnable.kr 9007 로 접속해서 문제를 확인해보자.

문제를 읽어보면 위조코인을 찾는 문제이다. 진짜 코인은 무게가 10이 나가고 위조코인의 무게는 9이다.

이것을 활용해서 위조코인의 인덱스를 찾아야한다.

 

예시를 살펴보자

4개의 코인 0,1,2,3 번 코인이 존재하고 이 중 하나는 위조코인이다.

이때 원하는 만큼 코인을 집어 무게를 측정할 수 있는 기회가 2번 주어진다면 위조코인을 찾을 수 있을까?

첫번째 시도에서는 0,1번 코인의 무게를 측정한다. 무게가 20이므로 둘다 진짜코인이다

두번째 시도에서는 3번 코인의 무게를 측정한다. 무게가 10이므로 진짜 코인이다.

따라서 2번코인이 위조코인으로 밝혀졌다.

 

여기까지만 읽어봐도 이진탐색 알고리즘을 활용하는 문제라는 것을 알 수 있다.

 

https://man-25-1.tistory.com/172?category=938895 

[강의노트] 사전ADT를 이용한 선형탐색과 이진탐색 - 1

 

입력순서리스트를 배열로 구현했을경우 이진탐색을 수행하면 최악의 시간복잡도는 O(log n) 이다.

따라서 문제에서 주어진 N= 277 에 기회를 9번 주는데 로그를 취하면 8.xx 기때문에 이진탐색 알고리즘으로 문제를 해결할 수 있다.

 

따라서 이진탐색 알고리즘을 100번 돌리면 문제가 해결된다.

 

익스플로잇 코드

from pwn import *   def BinarySearch(N_list, C):     left = 0     right = len(N_list) - 1     count = C          while left < right:         mid = (left+right)//2         payload = "".join([str(_)+str(" ") for _ in N_list[left:mid+1]])         p.sendline(payload)         count = count - 1                   if int(p.recvuntil("\n")) == (len(N_list[left:mid+1]) * 10) :             left = mid + 1         else:             right = mid           if left == right:             print("find@",left)             counterfeit = left     #남은 count가 있을경우를 대비해서             for i in range(count+1):         p.sendline(str(find_data))          p = remote("localhost", 9007) p.recvuntil("sec... -\n\t\n")   coin = 0 while coin < 100:     p.recvuntil("N=")     N = int(p.recvuntil(" "))     p.recvuntil("C=")     C = int(p.recvuntil("\n"))     N_list = [data for data in range(N)]     log.info("N="+str(N)+", C="+str(C))     BinarySearch(N_list, C)     coin = coin + 1     p.interactive()

 

익스플로잇 결과

 

알게된 것

join 함수 문법에 대해서 알게되었다. '구분자'.join(리스트) 의 형태로 사용하면 

리스트의 값 사이에 구분자를 넣어서 하나의 문자열로 합쳐준다.

0부터 9까지의 숫자 사이에 공백을 넣고 싶을때 위와 같이 작성해주면

이렇게 출력된다.