【picoCTF】Binary Search - Bashスクリプトを二分探索に書き換えてフラグ取得

問題概要

picoCTFの「Binary Search」という問題の解説記事です。

• カテゴリ: Forensics
• 難易度: Easy

問題文

解説

ステップ1: ZIPファイルの内容確認

$ unzip challenge.zip
Archive:  challenge.zip
   creating: home/ctf-player/drop-in/
  inflating: home/ctf-player/drop-in/guessing_game.sh

ステップ2: シェルスクリプトの確認

$ cat home/ctf-player/drop-in/guessing_game.sh

#!/bin/bash

# Generate a random number between 1 and 1000
target=$(( (RANDOM % 1000) + 1 ))

echo "Welcome to the Binary Search Game!"
echo "I'm thinking of a number between 1 and 1000."

# Trap signals to prevent exiting
trap 'echo "Exiting is not allowed."' INT
trap '' SIGQUIT
trap '' SIGTSTP

# Limit the player to 10 guesses
MAX_GUESSES=10
guess_count=0

while (( guess_count < MAX_GUESSES )); do
    read -p "Enter your guess: " guess

    if ! [[ "$guess" =~ ^[0-9]+$ ]]; then
        echo "Please enter a valid number."
        continue
    fi

    (( guess_count++ ))

    if (( guess < target )); then
        echo "Higher! Try again."
    elif (( guess > target )); then
        echo "Lower! Try again."
    else
        echo "Congratulations! You guessed the correct number: $target"

        # Retrieve the flag from the metadata file
        flag=$(cat /challenge/metadata.json | jq -r '.flag')
        echo "Here's your flag: $flag"
        exit 0  # Exit with success code
    fi
done

# Player has exceeded maximum guesses
echo "Sorry, you've exceeded the maximum number of guesses."
exit 1  # Exit with error code to close the connection

ステップ3: スクリプトの動作の理解

ゲームの正解となる数値の生成

target=$(( (RANDOM % 1000) + 1 ))

この行で、1〜1000 の範囲の乱数が正解（target）として生成されます。 つまり、毎回実行するたびに正解の数値は変わります。

試行回数の制限

MAX_GUESSES=10
guess_count=0

プレイヤーが入力できる回数は 最大 10 回 に制限されています。 これは問題文にある

You'll have 1000 possibilities and only 10 guesses.

という条件そのものです。

入力値に対する判定処理

if (( guess < target )); then
    echo "Higher! Try again."
elif (( guess > target )); then
    echo "Lower! Try again."
else
    echo "Congratulations! You guessed the correct number: $target"

ステップ4: なぜ二分探索が必要か

ここで重要なのは、

• 候補の数は 1000
• 試行回数は 10 回まで という条件です。

この条件下で確実に正解を見つける方法は、二分探索しかありません。 二分探索では、毎回探索範囲を半分に減らします。

10回の試行で 1000 → 1 まで絞り込めるため、必ず正解を見つけられます。

ステップ5: ゲームをクリアしてフラグを取得

このロジックを踏まえて、実際に二分探索を行います。

picoCTFのサーバーにSSHで接続する

問題文に記載されている情報を使って、picoCTFのサーバーにSSHで接続します。

ssh -p xxxxx ctf-player@atlas.picoctf.net

実際の探索例

初期状態では、範囲は 1〜1000 です。 1回目の入力として、中央の 500 を入力します。

Enter your guess: 500

• Higher! Try again. → 正解は 501〜1000 の範囲に絞られます。
• Lower! Try again. → 正解は 1〜499 の範囲に絞られます。
  このように、毎回常に現在の範囲の中央の値を入力し、探索範囲を半分に絞り込みながら、10回以内に正解を見つけます。
  例えば501〜1000の範囲に絞られた場合、次は750を入力します。

フラグの取得

最終的に正解を見つけた場合、以下のようにフラグが表示されます。

Congratulations! You guessed the correct number: 795
Here's your flag: picoCTF{xxxxx}

※フラグはマスクしています。

使用したコマンドの軽い解説

unzip

unzip challenge.zip

ZIPファイルを展開します。展開結果（どのファイルが出てきたか）も出力に表示されます。

cat

cat home/ctf-player/drop-in/guessing_game.sh

ファイルの中身を表示します。CTFでは「まずスクリプト/設定/ログを読む」が定石です。

まとめ

▼ポイントは以下の通りです。

• guessing_game.sh を読んで「試行回数10回」「範囲1〜1000」を確認する
• 二分探索で毎回範囲を半分にし、10回以内に必ず当てる

閲覧ありがとうございました！