Pwnable.kr [coin1]

	---------------------------------------------------
	-              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... -

 

코드 자체는 아니고 문제에서 요구하는 대로, nc로 포트에 붙으면 이와같은 창과 함께

 

N=123 C=7 같은 숫자만 덜렁 준다.

 

설명을 읽어보면, 0~122 (N-1)까지의 숫자 중에 하나만 무게값이 9이고, 해당 넘버를 찾는 것이 문제이다.

몇 번 보다보면 C는 2의 파워로, 2^C >= N의 조건을 만족하는 것을 알 수 있고

결국 이분 검색을 통해서 찾을 수 있다고 예상 가능하다.

 

사실 그냥 알고리즘 코딩 문제라고 봐도 되고, 파이썬을 이용해서 작성했는데,

문법이 아직도 생소하고, 프로그램이 입력받는 포맷에 맞게 해줘야 되서 시행착오를 겪으면서 꽤 오래 풀었다 ㅠ

 

우선 무조건 코딩해야 되는게, 간혹 작은 숫자(10대도 나옴)도 나오길래, 수기로 풀 수 있나? 했는데

100회 연속 풀어야 한다 ㅎ.

한 게임당 제한시간은 1분, 100만 넘어가도 사실상 힘들다. 

 

아래는 내 exploit 코드

trunc_N 함수만 봐도 상당히 조잡한 것을 알 수 있다. 흑

from pwn import *

#get N
def trunc_N(p):
	tmp = p.split(' ')	
	N = tmp[0].split('=')
	N[1] = int(N[1])
	print(N[1])
	return N[1]

#binary search
def search_coin(start, end):
	payload=""
	mid = (start+end)/2
	if start == end:
		return start
	for i in range(start,mid+1):
		payload += str(i)+" " 
	r.send(payload[:-1]+"\n")
	print("start: "+str(start)+"\nmid: "+str(mid)+"\nend: "+str(end))
	p=r.recvline()
	print(p)
	if 'Cor' in p:
		print("?")
		return -1
	if int(p)%10==0:
		start = mid+1
		result = search_coin(start, end)
		return result
	else:
		end = mid
		result = search_coin(start, end)
		return result

#This game must be played more than one time.
def do_onetime(r, N):
	start = 0
	end = N
	found = search_coin(start, end)
	print(found)
	if found!=-1:
		r.send(str(found)+"\n")
		p=r.recvline()
		print(p)
		while True:
			if not 'Cor' in p:
				r.send(str(found)+"\n")
				p=r.recvline()
				print(p)
			else:
				break
		
		

r=remote('127.0.0.1', 9007)
r.send("")	

for i in range(31):	#Read everything before start.
	r.recvline()

#1st
p=r.recvline()		#N, C
do_onetime(r, trunc_N(p))
for i in range(100):
	p=r.recvline()
	print(p)
	try:
		do_onetime(r, trunc_N(p))
	except:
		p=r.recvline()
		print(p)