Description
Want to play a game? As you use more of the shell, you might be interested in how they work! Binary search is a classic algorithm used to quickly find an item in a sorted list. Can you find the flag? You'll have 1000 possibilities and only 10 guesses.
Cyber security often has a huge amount of data to look through - from logs, vulnerability reports, and forensics. Practicing the fundamentals manually might help you in the future when you have to write your own tools!
- Download the provided challenge.zip artifact and inspect its README for context.
- Launch the picoCTF instance to obtain the unique SSH port and password for your session.
ssh -p <PORT_FROM_INSTANCE> ctf-player@atlas.picoctf.net
password: <PASSWORD_FROM_INSTANCE>
Solution
After connecting you will see:
Welcome to the Binary Search Game!
I'm thinking of a number between 1 and 1000.
From the shell script (sh) file provided you can see that you have 10 gueesses and each time it will compare your guess to the target and will let you know if the target it "Higher" or "Lower".
To find the optimal guesses you can use the Binary Search Tree (BST) tool and halve the search space on each attempt. You can do this by starting at the half point of 500 and based on the response chaning your bounds.
Forumula:(Low + High) / 2| Always round 0.5 downward.
Explore the search tree
Want the exact guesses, ranges, and calculations generated for you? Launch the Binary Search Tree tool and walk through each midpoint with copyable inputs and a live tree view.
Open Binary Search Tree ToolWorked example
If you'd like to see it worked out manually you can see the sequence below.
- Step 1too high
Guess: 500
(1 + 1000) / 2 = 500.5 → 500 (round down)
Next range: 1 – 499
- Step 2too high
Guess: 250
(1 + 499) / 2 = 250
Next range: 1 – 249
- Step 3too high
Guess: 125
(1 + 249) / 2 = 125
Next range: 1 – 124
- Step 4too high
Guess: 62
(1 + 124) / 2 = 62.5 → 62 (round down)
Next range: 1 – 61
- Step 5too low
Guess: 31
(1 + 61) / 2 = 31
Next range: 32 – 61
- Step 6too high
Guess: 46
(32 + 61) / 2 = 46.5 → 46 (round down)
Next range: 32 – 45
- Step 7flag found
Guess: 38
(32 + 45) / 2 = 38.5 → 38 (round down)
The service reveals the flag once the exact value is submitted.
Flag
picoCTF{g00d_gu355_de95...}
The service prints the flag immediately after the correct guess (38 in this run) once the binary search converges.