PicoCTF: Binary Search

Challenge Name: Binary Search

Category: General Skills

Difficulty: Easy

Description: Walkthrough and Learning

Challenge: guess the correct number between 1 and 1000 to win the flag.

After downloading the challenge.zip file, I found a game. "The Binary Search Game!" This game comes complete with some rules to play by such as maximum attempts

When I SSH into the challenge machine, we are immediately presented with this game.

After ten attempts, the connection is closed. So you restart the connection.

On this attempt, I captured the flag.

There is a real strategy to this. For example, if you could never attempt this game again, you must ensure that you guess correctly in the first 10 attempts. We know that the flag is an integer between 1 and 1000. We need to cut down the distance as quickly as possible. We might start at 500 to eliminate half the numbers.

If I cut the number in half each time, can I achieve the answer in 10 attempts? Lets find out based on the answer from the challenge. This strategy is simply cutting the number that is left, roughly in half based on the response of "higher" or "lower". The numbers I list to the right are the remaining possible answers after the attempt.

Begin: 1-1000

Attempt 1: 500 (lower) 1-499

Attempt 2: 250 (higher) 251-499

Attempt 3: 375 (higher) 376-499

Attempt 4: 437 (higher) 438-499

Attempt 5: 468 (lower) 438-467

Attempt 6: 452 (lower) 438-451

Attempt 7: 444 (higher) 445-451

Attempt 8: 447 (lower) 445-447

Attempt 9: 446 (lower) 445

Attempt 10: 445 You win!

We now know it is possible to complete this challenge in the 10 attempts they provide.

Thanks for reading!