Pwnable.kr - coin1

3 minute read

Challenge description:

Mommy, I wanna play a game! (if your network response time is too slow, try nc 0 9007 inside pwnable.kr server)

In this challenge we are not given any binary or source code, it’s just a netcat connection:

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

As described above, we are given a range of numbers (N) and we have to find the bad number in a limited number of tries (C).

Because the tries are limited, we need an efficient way to send the minimum number of queries. Whats better than Binary Search.

If you don’t know binary search, here is a little explanation:

given N=10 and Bad=6:

[1,2,3,4,5,6,7,8,9,10]	==> current search space
search at the first half:
[1,2,3,4,5]	==> weight is 50, divisible by 10, bad not here so we through the first half away

[6,7,8,9,10]	==> current search space
search at the first half:
[6,7]	==> weight is 19, not divisible by 10, bad is definitely here so we through the second half away

[6,7]	==> current search space
search at the first half:
[6]	==> weight is 9, not divisible by 10, range length is 1 so this is the bad number

Num of queries: 3

You can ssh using any of the previous challenges credentials and run the script locally (much faster than the remote connection).

Solution:

# solve.py

from pwn import *
import re

p = remote('localhost', 9007)
print(p.recv())

for i in range(100):
	N, C = re.findall("N=(\d+) C=(\d+)", p.recv())[0]
	N = int(N)
	C = int(C)
	print(N, C)

	start, end = 0, N-1

	while start <= end and C > 0:
		mid = (start + end) // 2
		x = " ".join([str(j) for j in range(start, mid+1)])	# build range list
		p.sendline(x)
		
		res = int(p.recvline()[:-1])
		if res % 10 == 0:
			start = mid+1	# through first half
		else:
			end = mid-1		# through second half
		C -= 1

	while C > 0:	# use all the tries
		p.sendline("0")
		p.recv(1024)
		C -= 1

	p.sendline(str(start))	# final answer
	print(p.recv())

print(p.recv())

$ python solve.py
.....
(736, 10)
Correct! (0)
.....
(359, 9)
Correct! (98)

(137, 8)
Correct! (99)

Congrats! get your flag
b1NaRy_S34rch1nG_1s_3asy_p3asy

Flag: b1NaRy_S34rch1nG_1s_3asy_p3asy

Abdallah Elshinbary

Solution: