[pwnable.kr] coin1

1. 문제 확인

nc pwnable.kr 9007

게임 내용을 요약하면 다음과 같다.

 

위조 동전 1개와 진짜 동전 N-1개가 존재한다. 여기서 위조 동전을 찾아야 한다.

찾을 수 있는 방법은 서버에게 동전의 인덱스 번호를 주면 동전의 무게를 반환하는데 위조 동전의 무게는 9이고 진짜 동전은 10이다.

 

규칙은 다음 예시를 통해 확인하자

 

[Server] N=10 C=2  # 전체 동전 개수 N개, 기회 4번

[Client ] 0 1 2 3 4 5  # 동전 인덱스 번호(0, 1, 2, 3, 4, 5), 기회 1번 차감(1번 남음)

[Server] 60                # 0 ~ 5 인덱스의 동전의 합한 무게, 다 진짜 동전이므로 60

[Client ] 6 7 8           # 동전 인덱스 번호(6, 7, 8), 기회 1번 차감(0번 남음)

[Server] 30               # 6 ~ 8 인덱스의 동전의 합한 무게, 다 진짜 동전이므로 60

[Client ] 9                  # 기회를 전부 다 쓰고 마지막에 가짜 동전의 인덱스 ㄱㄱ

[Server] Correct!    # 나머지 9번 인덱스가 가짜 동전인 것을 알 수 있음

 

---

2. 접근 방법

 

이진 탐색을 이용해서 찾는 방법으로 ㄱㄱ

• 이진 탐색의 빅오 = O(lgn)

예를 들어, N=422, C=9일 때 lg422 = 8.72109 이므로 9번의 기회로 충분하다.

그리고 몇 번 하다보면 빅오 값을 넘지 않는 기회를 주므로 쌉 충분하다.

 

이진 탐색 참고 자료)

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

 

---

3. 문제 풀이

 

익스 코드)

from pwn import *

context.log_level = "debug"

def init_data():
    p.recvuntil("N=")
    N = int(p.recvuntil(" "))
    p.recvuntil("C=")
    C = int(p.recvuntil("\n"))

    return N, C


def BinarySearch(N_list, C):
    lower = 0
    upper = len(N_list) - 1
    count = C
    
    while lower < upper:
        middle = (lower+upper)/2
        payload = "".join([str(_)+str(" ") for _ in N_list[lower:middle+1]])
        p.sendline(payload)
        count = count - 1 
        
        log.info("send data : "+payload)
        log.info("chance    : "+str(count))

        if int(p.recvuntil("\n")) == (len(N_list[lower:middle+1]) * 10) :
            lower = middle + 1
        else:
            upper = middle

        if lower == upper:
            find_data = lower
            
    for c in range(count+1):
        p.sendline(str(find_data))

    

p = remote("pwnable.kr", 9007)
p.recvuntil("sec... -\n\t\n")

coin = 0

while coin < 100:
    N, C = init_data()
    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()

 

→ 하다 보면 자꾸 "time expired" 뜨면서 안됨

 

이럴 때 걍 서버에 접속해서 코드 실행하면 해결할 수 있음

(서버 접속해서 /tmp에다가 파이썬 코드 올리고 실행하면 됨)

fd@pwnable:/tmp/cmc$ ls 
ex.py

 

실행결과)

---

4. 몰랐던 개념