[Toddler's Bottle] coin1 writeup

문제

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

---

분석

이번 문제는 해킹문제라기보다는 간단한 게임이다.

게임의 내용

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

이 게임을 해결하는 아이디어는 간단하다.

a번 코인부터 b번 코인까지 중에서 weight가 9인 코인 하나를 찾기 위해서는 우선 a ~ (a+b)/2번 코인들의 무게를 서버에 요구한다.

만약 그 값이 10으로 나누어 떨어진다면 이제 (a+b)/2 + 1 ~ b번 코인 중에서 weight가 9인 코인을 찾으면 되고 반대의 경우 a ~ (a+b)/2번 코인 중에서 찾으면 된다.

이를 1~N번 코인에 대해 재귀적으로 수행하면 분명히 C회 안에 찾을 수 있다. ( C > log(N) )

---

FL4G

exploit :

sol_coin1.py