Pwnable.kr 「coin1 (Toddler's Bottle)」Writeup

pwnable_kr-coin1

Summary

本問は，二分探索を用いて，制限時間内に重さの異なる偽のコインを探す問題です．

• Category: Misc
• Description: Mommy, I wanna play a game!
• Tools & TechStack:
  • Python
  • Binary Search
• Release: N/A

階層構造

.
└── readme

1 directory, 1 file

---

ゲームルールを読む

この問題では，readme しか含まれていませんでした．
とりあえず，接続先にアクセスしてみるとゲームルールの説明が表示されました．

readme

# coin1

Mommy, I wanna play a game!

## Remote

Direct connection: `nc pwnable.kr 10009`

The challenge is executed under coin1_pwn privilege.

$ nc pwnable.kr 10009

        ---------------------------------------------------
        -              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 500 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=144 C=8

日本語版

    ---------------------------------------------------
    -              ゲームをしようか？                  -
    ---------------------------------------------------

    君の手には何枚かの金貨がある
    しかし，その中に1枚だけ偽物の金貨が混ざっている
    偽物の金貨は本物とまったく同じ見た目をしている
    しかし，重さだけが本物と異なる
    本物の金貨の重さは10，偽物の金貨の重さは9だ
    天秤 (はかり) を使って偽物の金貨を見つけてほしい
    偽物の金貨を100枚見つけたら，報酬がもらえるよ :)
    ちなみに，制限時間は500秒だ。

    - 遊び方 -
    1. 金貨の枚数 (N) と計量できる回数 (C) が与えられる
    2. 量りたい金貨のインデックス番号の組を指定する
    3. その重さの情報が返ってくる
    4. 2〜3をC回繰り返したら，答えを提出する

    - 例 -
    [Server] N=4 C=2        # 4枚の金貨から2回の試行で偽物を見つける
    [Client] 0 1            # 1枚目と2枚目の金貨を量る
    [Server] 20             # 計量結果: 20
    [Client] 3              # 4枚目の金貨を量る
    [Server] 10             # 計量結果: 10
    [Client] 2              # 偽物は3枚目だ！
    [Server] Correct!

制限時間500秒以内に，重さが10のN枚の金貨の中から，C回の秤を使用して重さが9の偽の金貨を連続で100枚当てることができれば，Flagが入手できるようです．

自動化スクリプトを書く

二分探索で解くため，秤で計るごとに探索範囲が半分になります．
そのため，必要な回数は $\log_2 x$ になります．

時間制限については，1問あたり C+1 往復なので，100問でも数百~千往復程度に収まるはずです．
よって，500秒なら十分間に合うはずです．

from pwn import *
import re

NC_PAT = re.compile(rb'^N=(\d+) C=(\d+)')

p = remote("pwnable.kr", 10009)

# n, c が来るまで読み飛ばす関数
def recv_nc(p):
    while True:
        line = p.recvline().strip()
        m = NC_PAT.match(line)
        if m:
            return int(m.group(1)), int(m.group(2))
        # N, C 以外の行
        log.info(line.decode(errors='ignore'))

# コイン100枚分のループ
for i in range(100):
    n, c = recv_nc(p)
    log.success(f"{i}: <Coin: {n}, Libra: {c}>")

    low, high = 0, n
    sum_w = 0

    # 秤の使用回数
    for _ in range(c):
        # 1つに絞れたとき，使い果たすまで正解であるかをチェック
        if low + 1 == high:
            p.sendline(str(low).encode())
            result = p.recvline().strip()
            assert(int(result) == 9)
            continue

        center = (low + high) // 2

        # 計測した重さが9が10かで，左か右を選択する
        range_str = " ".join(map(str, range(low, center))).encode()
        p.sendline(range_str)
        sum_w = int(p.recvline().strip())

        # 偽のコインが無い場合
        if sum_w % 2 == 0:
            # low, hi の区間を更新
            low = center
        else:
            high = center

    # 答えを送る
    p.sendline(str(low).encode())
    if p.recvline().strip().startswith(b"Correct"):
        log.success(f"No.{i}: Correct!")

log.success(p.recvall(timeout=5).decode(errors='ignore'))

$ python3 solver.py
#...
[*] - Ready? starting in 3 sec... -
[*]
[+] 0: <Coin: 611, Libra: 10>
[+] No.0: Correct!
#...
[+] 99: <Coin: 784, Libra: 10>
[+] No.99: Correct!
[+] Receiving all data: Done (55B)
[*] Closed connection to pwnable.kr port 10009
[+] Congrats! get your flag
    <REDACTED>

---

Post-Mortem & Dead ends

N/A

References

N/A