# pwnable.kr - coin1

## Prompt

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

## Analysis

``````noble@heart:~\$ 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... -

N=338 C=9
``````

We need to, with a restricted number of guesses, find a counterfeit coin in an array of coins. I’m optimistic about using binary search to cut out half of the possible coins each guess. The main issue is finding 100 coins in 60 seconds. We obviously have to do this programmatically. Python and its `pwntools` library will be very useful for sending, receiving, and processing.

At first I was making the connections remotely, i.e. with `conn = remote('pwnable.kr', 9007)`, but it was not fast enough. We need to solve 100 challenges, and my initial script only reached the mid-80s in solves. I was considering using recursive binary search, but then remembered I could `ssh` into the server to run my scripts locally to improve response time. Note: you can make SSH connections with `pwntools` but you’ll need to programmatically upload, `chmod +x`, and run your solution script if you want to bypass the delay.

## Solution

SSH into on of the other pwnable.kr challenge accounts, e.g. `ssh fd@pwnable.kr -p2222 #password: guest`.

``````fd@pwnable:~\$ mkdir /tmp/binary
fd@pwnable:~\$ cd \$_
fd@pwnable:/tmp/binary\$ vim solve.py # paste file into vim
fd@pwnable:/tmp/binary\$ chmod +x solve.py
fd@pwnable:/tmp/binary\$ python solve.py
[+] Opening connection to localhost on port 9007: Done
Correct! (0)

Correct! (1)
...
Correct! (99)

{censored flag}

[*] Closed connection to localhost port 9007
fd@pwnable:/tmp/binary\$
``````

solve.py:

``````#!/usr/bin/env python2

from pwn import *

# For SSHing in, and then running locally
# s = ssh(host="pwnable.kr", user="fd", port=2222, password="guest")
# conn = s.remote('localhost', 9007)

# For running remotely
# conn = remote('pwnable.kr', 9007)

# For running locally on pwnable.kr
conn = remote('localhost', 9007)

conn.recvline()
conn.recvline()

for _ in range(100):

line = conn.recvline().decode('utf-8').strip().split(' ') # [u'N=317', u'C=9']
# print line
n = int(line.split('='))  # 317
c = int(line.split('='))  # 9

start = 0
end = n - 1

for _ in range(c):

mid = int((start + end)/2) # cast to ensure only whole numbers

# print('start: '+str(start))
# print('mid: '+str(mid))
# print('end: '+str(end))

guess = ' '.join(str(i) for i in range(start, mid + 1))
# print guess
conn.sendline(guess)
weight = int(conn.recvline())
# print weight

if weight % 10 == 0: # if divisible by 10, then no counterfeit in list
start = mid + 1
else: # counterfeit in list
end = mid

conn.sendline(str(start)) # send final guess

print(conn.recvline())  # Correct! (n)

print(conn.recvline()) # Congrats! get your flag
print(conn.recvline()) # {actual flag}

conn.close()

``````