Binary Search - General Skills

Description

Walkthrough

When I read the challenge's description above, two keywords stood out: the shell and Binary Search. From that information, I assumed this challenge was meant to introduce players to the idea of the Shell and the Binary Search algorithm. So, I downloaded the challenge files directly from the terminal:

wget https://artifacts.picoctf.net/c_atlas/19/challenge.zip -O challenge.zip

I extracted the zip file, and there was only one shell script guessing_game.sh inside the folder /home/ctf-player/drop-in/:

I took a look at the script, read them, and realized it’s a simple 'Binary Search' guessing game:

This game asks the users to guess a number between 1 and 1000, and only get 10 tries to get it right. If the guess is too high, it tells to go lower. If it’s too low, it tells to go higher. Once I guess the correct number, it congratulates me and gives me the flag.

To solve this challenge, I needed to play the game by guessing the correct number using the Binary Search formula: mid_idx = (low_idx + high_idx) / 2.

Since Binary Search works by cutting the range in half each time, I started by guessing the middle number between 1 and 1000, which is 500. Depending on whether the game told me to guess higher or lower, I adjusted my next guess and kept narrowing it down.

If you want to understand how the Binary Search algorithm works, you can watch this or read this. Now let's check the program's source code, and see how they actually work.

#!/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

This shell script generates a random number between 1 and 1000 and gives the players chance to guess the correct number up to 10 guesses. If the players guess the number that is higher than the correct number, it will respond with a message: Lower! Try Again, otherwise, it will respond: Higher! Try Again, until the players guess the correct number and then it will give them the flag.

So, this is basically a simple challenge. I just need to play the game by guessing the correct numbers and get the flag. Here's one of my attempt to get the flag by playing the game:

Bu(t|g)

Here’s the interesting part, though: while playing around with the script, I noticed a bug. Let’s break it down, and check the code again.

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

In the code above, we can see that it checks if the user’s input is a number (0 to 9). If it’s not, the script just asks for a valid number and moves on to the next try.

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

Next, the script compares the user's guess to the target number. If the guess is too low, it says, "Higher! Try again" If it’s too high, it says, "Lower! Try again." And if it's right, it prints the flag.

The logic works fine overall, but there’s a catch. If you enter a number with a leading zero followed by something greater than 7 (like 099), the program crashes—and it still prints the flag to the console:

The issue arises from how the script handles input with leading zeros, such as 099. In Bash, numbers starting with 0 are interpreted as octal (base 8) instead of decimal (base 10). Octal numbers only allow digits 0 through 7, so entering something like 099 confuses Bash since 9 isn’t valid in octal. This causes the program to crash, but instead of handling the error properly, the script continues running and inadvertently prints the flag to the console.

This bug can be exploited to bypass the game entirely and retrieve the flag without playing. By simply entering an invalid octal number, the error is triggered, causing the program to behave unexpectedly.

Fixing this bug requires ensuring that user input is always treated as decimal and properly validated to prevent such edge cases. Simple changes, such as stripping leading zeros or enforcing base-10 interpretation, can safeguard against this issue. For example, using the following code:

guess=$((10#$guess))

If you want to know more about the bug, you can simply Google it using the keyword 'leading zeros in bash,' or just read this simple article.

Solver

You can see the solver (by playing the game) here.