coin1

nc로 접속해보면

	---------------------------------------------------
	-              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=425 C=9

이런 게임이 나온다 해석해보면 코인 갯수와 시도횟수를 출력해주는데

코인중에 가짜 코인이 숨어있다고 한다 그리고 가짜 코인은 진짜와 무게가 다르다고한다.

원하는 동전의 무게 정보도 알려준다고 한다. 우리는 무게를 비교하면서 가짜 코인을 100번 찾아내야한다. 그런데 시간제한이 60초다.

이진 탐색으로 답을 빠르게 맞춰야한다.

그냥 프로그래밍 문제다;;

아직 알고리즘에 취약하기 때문에 검색의 힘을 빌렸다.

---

from pwn import *

context.log_level = 'debug'

p = remote('pwnable.kr', 9007)
p.recvuntil('- Ready? starting in 3 sec... -')

for i in range(100):
    p.recvuntil('N=')
    coin = int(p.recvuntil('C=').split(b' ')[0])
    chance = int(p.recvline())

    start = 0
    end = coin -1

    for j in range(0, chance):
        mid = (start + end) // 2
        msg = ''
        for k in range(start, mid+1): msg += (str(k) + ' ')
        p.sendline(msg)
        res = int(p.recvline())
        if res%10 == 9:
            print([str(k) for k in range(start, mid+1)])
            end = mid
        else:
            print([str(k) for k in range(mid+1, end+1)])
            start = mid + 1
    
    p.sendline(str(start))
    p.recvline()

p.interactive()

처음에는 이 코드로 원격에서 시도하니 응답속도가 느려서 절반도 못가서 60초가 지나버린다.

문제 설명을 보면 응답이 느리면 폰케알 서버 내에서 시도해보라고 하니

ssh로 접속하는 아무 문제나 접속해서 

/tmp에 파이썬 코드를 작성하고 실행하면 된다.

fd@pwnable:/tmp/kimg00n$ cat ex.py
from pwn import *

context.log_level = 'debug'

p = remote('0', 9007)
p.recvuntil('- Ready? starting in 3 sec... -')

for i in range(100):
    p.recvuntil('N=')
    coin = int(p.recvuntil('C=').split(b' ')[0])
    chance = int(p.recvline())

    start = 0
    end = coin -1

    for j in range(0, chance):
        mid = (start + end) // 2
        msg = ''
        for k in range(start, mid+1): msg += (str(k) + ' ')
        p.sendline(msg)
        res = int(p.recvline())
        if res%10 == 9:
            print([str(k) for k in range(start, mid+1)])
            end = mid
        else:
            print([str(k) for k in range(mid+1, end+1)])
            start = mid + 1

    p.sendline(str(start))
    p.recvline()

p.interactive()

난 fd에 접속해 tmp안에 폴더를 만들어 0 9007로 접속하게 코드를 바꾸고 실행했다.

[DEBUG] Received 0xe bytes:
    'Correct! (99)\n'
[*] Switching to interactive mode
[DEBUG] Received 0x37 bytes:
    'Congrats! get your flag\n'
    'b1NaRy_S34rch1nG_1s_3asy_p3asy\n'
Congrats! get your flag
b1NaRy_S34rch1nG_1s_3asy_p3asy
[DEBUG] Received 0x13 bytes:
    'time expired! bye!\n'
time expired! bye!
[*] Got EOF while reading in interactive
$

 

실행해보면 플래그가 잘 출력되는것을 볼 수 있다.

 

flag: b1NaRy_S34rch1nG_1s_3asy_p3asy

 

---

알고리즘과 자료구조를 좀 공부해야겠다고 마음먹게 되는 문제였다.

파이썬 문법도 좀 날잡고 공부해야될거 같다.