pwnable.kr coin1 write up

pwnable.kr coin1 write up

H3X0R팀 소속 BoB 6기 ch4n3

---

후욱,,, 후욱,,,, 코딩으로 포너블 문제를 처음으로 풀었다는 사실에 감격했다. 

Mommy, I wanna play a game!

(if your network response time is too slow, try nc 0 9007 inside pwnable.kr server)

Running at : nc pwnable.kr 9007

---------------------------------------------------

-              Shall we play a game?              -

---------------------------------------------------

You have given some gold coins in your hand

however, there is one counterfeit coin among them

counterfeit coin looks exactly same as real coin

however, its weight is different from real one

real coin weighs 10, counterfeit coin weighes 9

help me to find the counterfeit coin with a scale

if you find 100 counterfeit coins, you will get reward :)

FYI, you have 30 seconds.

- How to play - 

1. you get a number of coins (N) and number of chances (C)

2. then you specify a set of index numbers of coins to be weighed

3. you get the weight information

4. 2~3 repeats C time, then you give the answer

- Example -

[Server] N=4 C=2 # find counterfeit among 4 coins with 2 trial

[Client] 0 1 # weigh first and second coin

[Server] 20 # scale result : 20

[Client] 3 # weigh fourth coin

[Server] 10 # scale result : 10

[Client] 2 # counterfeit coin is third!

[Server] Correct!

- Ready? starting in 3 sec... -

이건 굳이 해석하지 않겠다.

이 문제는 코딩으로 해결해야 하는 문제이다. 나는 알고리즘에 대해 문외한이기 때문에 무작정 선형 탐색으로 counterfeit coin을 찾으려고 했었다. 하지만, 이런 방법을 사용하게 되면 'time expired' 라는 결과값을 서버로부터 얻게 될 것이다. 그래서 몇 번씩, 몇 번씩 시도했지만, 이 문제를 풀지 못했다. 이 문제를 풀면서 디미고 친구로부터 이진 탐색에 대해서 알게 되었다. 이진 탐색은 선형탐색보다 찾아야 할 대상이 적기 때문에 더 효율적으로 문제를 풀 수 있을 것이라고 생각했다. 

그래서 나는 pwntools를 이용해서 파이썬 스크립트를 작성하기로 하였다.

#! /usr/bin/python
# -*- coding : utf-8 -*-
from pwn import *
import time
import sys

host = "pwnable.kr"
port = 9007

r = remote(host, port)
time.sleep(3)           # wait for 3 sec.

print r.recv()

cnt = 0
for i in range(100):
    r.recvuntil('N=')
    n = int( r.recvuntil(' ') )
    r.recvuntil('C=')
    c = int( r.recv() )
    
    st = 1
    des = n
    t = 0
    while(1):
        
        message = ''
        
        if(st > des):
            break
        
        message = ''
        for i in range(st, (st + des) // 2 + 1):
            message += '{0} '.format(i) 
        
        print "[-] guess : {0}".format(message)
        x = r.sendline(message)
        result = r.recv()
        
        print "[*] result : {0}".format(result)

        if result.find('Correct') > -1:
            t = 1
            break
        elif result[0] == 'N':
            des = n
        elif result.find('error') > -1:
            break
        elif result.find('time') > -1:
            print "\n\n[x] time expired.."
            sys.exit(1)
        elif int(result) % 10 != 0:
            des = (st + des)//2
        else:
            st = (st+des)//2 + 1
    if(t == 0):
        r.sendline(str(st))
        correctmsg = r.recv()
    cnt += 1
    print "[+] count : {0}\n".format(cnt)

flag = r.recv()
print "\n\n[*] FLAG : {0}".format(flag)

플래그를 획득했다