Let’s start with another challenge from pwnable.kr called 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

Solution

Firstly let’s connect to this service using nc.

main:~ > 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... -

N=34 C=6
time expired! bye!

So we get a set of coins, with only one counterfeit one that weights 9, rest of them weight 10 each. As we have limited tries and limited time to find 100 counterfeit coins, we have to find a quick algorithm that will do it for us.

What helped me find out the solution was illustrating the problem on a piece of paper.

[10,10,10,10,9,10,10,10,10,10]

Let’s sum up the weight of first half of these 10 coins.

10+10+10+10+9 = 49

Here we see that the sum is not divisable by 10, so that means that 9 in somewhere in this half. Let’s repeat this operation once more, but after dividing this half.

[10,10,10] # here we're not able to divide it, so let's take 3 and 2

This set’s weight is equal to 30, so the counterfeit must be in the other part.

[10, 9]

This time weight is equal to 19, so one of these 2 coins is counterfeit. If we choose to weight the first one, we’ll know that it’s real, and the counterfeit is the other coin.

Easy, right? That’s binary searching and now we’re ready to implement it in Python. I’ll be using pwntools library which makes communication with servers much easier.

import time
from pwn import *

conn = remote('0', 9007)
conn.recv(10024)
for _ in range(100):
    line = conn.recv(1024).decode('UTF-8').strip().split(' ')
	  print(line)
    n = int(line[0].split('=')[1])
    c = int(line[1].split('=')[1])
    left = 0
    right = n

    for _ in range(c):
        guess = ' '.join(str(left) for left in range(left, int((left+right)/2)))
        conn.sendline(guess)
        output = int(conn.recv(1024).decode('UTF-8').strip())
        if (output % 10 == 0):
            left = int((left+right)/2)
        else:
            right = int((left+right)/ 2)
    conn.sendline(str(left))
    print(conn.recv(1024).decode('UTF-8'))
print(conn.recv(1024).decode('UTF-8'))
conn.close()                 

If you don’t understand this code, follow my lead. Firstly we will set the connection variable, to the address 0, as we’ll run this code inside one of the pwnable.kr servers - response time will be much faster.

After that we’re ready to get the bytes from the introduction with conn.recv(10024). We will not need it on our challenge. After that, the loop will will iterate for each of the coin sets that we’re assigned to check.

Next lines will decode the line, get the values of n and c, with left and right variables that will be helpful for the binary search.

After that there’s a loop that will iterate for the number of tries we have. In each iteration we’re doing our binary search procedure - weight the first half of coins, if the weight is divisable by 10, then try the other half. If not, then cut in half the part that we’ve been using. Easy, right?

[u'N=433', u'C=9']
Correct! (95)

[u'N=588', u'C=10']
Correct! (96)

[u'N=628', u'C=10']
Correct! (97)

[u'N=323', u'C=9']
Correct! (98)

[u'N=310', u'C=9']
Correct! (99)

Congrats! get your flag
b1NaRy_S34rch1nG_1s_3asy_p3asy

[*] Closed connection to 0 port 9007

And we have the flag!

Tools used

Python

Pwntools

Reference/notes

https://en.wikipedia.org/wiki/Binary_search_algorithm

https://docs.pwntools.com/en/stable/