[pwnable.kr] coin1

[pwnable.kr] coin1

Problem

게임을 하고 싶다는 말이 써져있고 nc로 접속할 수 있는 프로그램 하나가 주어져있었다.

앞 문제들과는 달리 소스 코드나 ssh로 접속할 수 있는 상황은 아니었다.

nc를 통해 접속해보니 게임 하나가 주어져있엇다.

접속을 한 후, 일정 시간이 지나면 N과 C를 주게 되어있었다.

0 ~ N 범위의 동전에서 무게가 9인 가짜 동전을 찾는 문제였다. 정상적인 동전은 10의 무게를 가지고 있고 0~N 범위에서 무게가 9인 동전을 찾으면 문제를 해결하는 방식으로 되어있었다.

총 C번까지 시도 이후에 답을 입력하면 문제가 해결되었고 총 100개의 문제를 해결하게 되면 reward를 준다고 되어있었다.

Solution

C번의 기회밖에 주어지지 않아서 모든 동전을 일일이 확인하기는 어려워보였다.

하나의 동전을 제외한 모든 동전의 무게가 10이기 때문에 범위를 설정하여 보내 나머지가 9인 값이 들어있다면 범위를 계속해 좁혀나갈 수 있고 해당 동전을 찾을 수 있을 것 같았다.

문제를 해결하기 위해 Binary Search를 이용했다. 특정 값을 찾는 Binary Search에서 조금 수정해 범위를 변경해가며 9가 나올 때까지 찾는 방식을 사용했다.

Binary Search의 비교 횟수가 logN 정도 되기 때문에 사용 가능한지 확인하기 위해 접속을 계속해서 진행해보았더니 모든 문제가 해당 범위 내에서 찾을 수 있게 되어있었다.

ref) Binary Search : http://dongdd.tistory.com/50?category=768515

이 문제는 예제로 설명하는 것이 좋을 것 같아 예제를 만들어보았다.

Example) N=13, C=4, Answer=9

Step-1

먼저 가장 작은 값 0을 low로 설정하고, 가장 큰 값 13(N)을 high로 설정한다.

이 후에 mid = (low+high)/2로 계산해 mid에 6을 넣어준다.

low~mid 값을 보낸 후 돌아오는 값에 모듈러 연산을 하여 1의 자리가 9인지 0인지 확인한다. 예제에서는 0~6을 보냈을 때 나머지가 0이 나오게 된다.

0이 나올 경우 해당 범위에 정답이 없는 것이기 때문에 low값을 mid+1로 설정해 다시 진행한다.

Step-2

첫번째 과정을 거치고 low=7, high=13이 된다. mid = (low+high)/2를 계산해 mid에 10을 넣어준다.

low~mid 값을 보낸 후 돌아오는 값에 모듈러 연산을 하면 7~10에 답인 9가 포함되어 있으므로 9를 얻게 되고 이 범위 내에 답이 있다는 것을 알 수 있다. 이러한 경우에는 high값을 mid로 설정해 다시 진행한다.

Step-3

두번째 과정을 거치고 low=7, high=10이 된다. mid = (low+high)/2를 계산해 mid에 8을 넣어준다.

low~mid 값을 보낸 후 돌아오는 값에 모듈러 연산을 하면 7~8에는 답인 9가 포함되어 있지 않기 때문에 0을 얻게 되고 범위 내에 답이 없다는 것을 알 수 있다. low = mid+1로 설정해 다시 진행한다.

Step-4

세번째 과정을 거치고 low=9, high=10이 된다. mid = (low+high)/2를 계산해 mid에 9를 넣어준다.

low~mid(9) 값을 보낸 후 돌아오는 값에 모듈러 연산을 하면 9를 얻게 되고 이게 답이라는 것을 알 수 있다.

이것이 답이 아닐 경우는 low가 mid+1이 되어 답이 10이더라도 찾을 수 있게 된다.

이 과정을 코딩을 통해 작성하고 총 100번을 돌리게 되면 flag를 획득할 수 있다.

python으로 코딩은 별로 해보지 않아서 for문 범위 설정에서 어려움이 많았다.

pwntool을 사용해 nc로 접속하고 해당 프로그램을 100번 수행해 flag를 획득할 수 있었다.

**************     Answer & Flag     **************

Python Code(pwntool)

from pwn import *
 
p = remote("pwnable.kr",9007)
 
print p.recv()
for j in range(100):
    print p.recvuntil("N=")
    a = int(p.recvuntil(" "))                           
    print p.recvuntil("C=")
    b = int(p.recvuntil("\n"))
    print b
 
    low = 0
    high = a
    cnt = 0
    while cnt != b :
        cnt = cnt + 1
        snd = ""
        mid = (low+high)/2
        for i in range(low,mid):
            snd += str(i)
            snd += " "
        snd += str(mid)
        print snd
        p.sendline(snd)
        a = int(p.recv())
        print a
        if a % 10 == 9 :
            high = mid
        else:
            low = mid + 1
 
    mid = (low+high)/2
    p.sendline(str(mid))
    print str(mid)
    print p.recv()
print p.recv()
 

위의 예제에서 설명한대로 그대로 코딩을 했다. 프로그램을 실행하여 flag를 획득할 수 있었다.

Flag : b1NaRy_S34rch1nG_1s_3asy_p3asy