Coin1 문제풀이

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

Toddler's Bottle 11번 문제

이 문제는 보안 문제라기 보다는

코딩 문제에 가깝습니다.

알고리즘을 배우고 한동안 쓸일이 없었는데

활용할 기회가 생겨 즐겁더군요.

fd@ubuntu:/tmp/Posix/coin1$ nc localhost 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 60 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... -

N=664 C=10

주어진 포트로 Netcat을 사용해 접속하면

게임에 대한 설명이 나옵니다.

간단히 요약하면

주어지는 N개 동전 중에 섞여있는

무게가 9인 가짜 동전 하나를

C번 만에 찾아내면 되는 게임입니다.

다만 60초 안에 100번을 찾아내야 하니

인간의 손으로는 불가능 할 것 같군요.

format error

참고로 문제 설명에 제시되지는 않았지만

동전을 찾아내는 것은 마지막 찬스여야만 합니다.

그 이전에 동전을 찾아서 번호를 입력해도

무게만 출력될 뿐이지요.

또한 가짜 동전을 마지막 기회에서

무게를 조회하겠다고

다수의 코인 번호를 입력하면

위와 같이 형식 오류가 뜹니다.

#! /usr/bin/python

from pwn import *
import re
import sys

p = re.compile('N=(\d+) C=(\d+)')

def range_sum(begin, end):
		query = ' '.join(str(i) for i in range(begin, end))
		
		conn.writeline(query)
		res = conn.readline()
		
		if res.find('Correct!') != -1 or int(res) == 9:
			while res.find('Correct!') == -1:
				conn.writeline(query)
				res = conn.readline()
			
			sys.stdout.write(res)
			return -1
		
		return int(res)

def find_counterfeit(begin, end):
	
	if begin + 1 == end:
		range_sum(begin, end)
		return -1
		
	mid = (begin + end) >> 1
	
	left_sum = range_sum(begin, mid)
	
	if left_sum == -1: return
	
	if left_sum != (mid - begin) * 10:
		find_counterfeit(begin, mid)
	else:
		find_counterfeit(mid, end)


if __name__ == '__main__':
	conn = remote('localhost', 9007)
	conn.read()

	sleep(4)
		
	while True:
		info = conn.readline()		
		m = p.search(info)
		
		if info == 'Congrats! get your flag\n':			
			sys.stdout.write(info + conn.read())
			break
		
		N = int(m.group(1))
		
		find_counterfeit(0, N)

이 문제는 이진탐색을 사용해 푸는 문제로서

C는 이진탐색을 사용해 반드시

답을 찾아낼 수 있는 값으로 지정됩니다.

만약 이진탐색 알고리즘을 사용해

스크립트를 작성했는데도

타임아웃 오류가 난다면

인터넷 지연에 의한 것일 확률이 높으므로

이전에 사용했던 pwnable.kr의 ssh 계정을

아무거나 이용하여 서버 내부에서 스크립트를 실행하도록 합시다.

fd@ubuntu:/tmp/Posix/coin1$ ./solve.py
[+] Opening connection to localhost on port 9007: Done
Correct! (0)
...
Correct! (98)
Correct! (99)
Congrats! get your flag
b1NaRy_S34rch1nG_1s_3asy_p3asy
[*] Closed connection to localhost port 9007

서버 내부에서 스크립트를 실행해

플래그를 휙득했습니다.