picoCTF - Binary search

W tym poście chciałbym opisać rozwiązania zadania Binary Search z działu General Skills picoCTF. 

Do zadania dołączony skrypt:

1.  
2.             #!/bin/bash
3.  
4.             # Generate a random number between 1 and 1000
5.             target=$(( (RANDOM % 1000) + 1 ))
6.  
7.             echo "Welcome to the Binary Search Game!"
8.             echo "I'm thinking of a number between 1 and 1000."
9.  
10.             # Trap signals to prevent exiting
11.             trap 'echo "Exiting is not allowed."' INT
12.             trap '' SIGQUIT
13.             trap '' SIGTSTP
14.  
15.             # Limit the player to 10 guesses
16.             MAX_GUESSES=10
17.             guess_count=0
18.  
19.             while (( guess_count < MAX_GUESSES )); do
20.                 read -p "Enter your guess: " guess
21.  
22.                 if ! [[ "$guess" =~ ^[0-9]+$ ]]; then
23.                     echo "Please enter a valid number."
24.                     continue
25.                 fi
26.  
27.                 (( guess_count++ ))
28.  
29.                 if (( guess < target )); then
30.                     echo "Higher! Try again."
31.                 elif (( guess > target )); then
32.                     echo "Lower! Try again."
33.                 else
34.                     echo "Congratulations! You guessed the correct number: $target"
35.  
36.                     # Retrieve the flag from the metadata file
37.                     flag=$(cat /challenge/metadata.json | jq -r '.flag')
38.                     echo "Here's your flag: $flag"
39.                     exit 0  # Exit with success code
40.                 fi
41.             done
42.  
43.             # Player has exceeded maximum guesses
44.             echo "Sorry, you've exceeded the maximum number of guesses."
45.             exit 1  # Exit with error code to close the connection
46.  

Zadanie polega na zgadywaniu liczb. Na samym początku losowane jest wartość z zakresu od 1 do 1000, z maksymalną liczbą prób zgadnięcia wynoszącą 10. W odpowiedzi na wartości przekazuje informacje Lower/Higher lub Congratulation. 

Procedurę należy przeprowadzić w oparciu o wyszukiwanie binarne. Tutaj całą tablicę dzielimy na pół, i wiemy czy następne ma być większe czy niższe. 

1. Welcome to the Binary Search Game!
2. I'm thinking of a number between 1 and 1000.
3. Enter your guess: 500
4. Lower! Try again.
5. Enter your guess: 250
6. Lower! Try again.
7. Enter your guess: 125
8. Lower! Try again.
9. Enter your guess: 65
10. Lower! Try again.
11. Enter your guess: 30
12. Lower! Try again.
13. Enter your guess: 15
14. Higher! Try again.
15. Enter your guess: 23
16. Lower! Try again.
17. Enter your guess: 18
18. Higher! Try again.
19. Enter your guess: 20
20. Congratulations! You guessed the correct number: 20
21. Here's your flag: picoCTF{g00d_gu355_bee04a2a}

Należy wykonywać odpowiednio duże skoki najlepiej, zgodnie z zasadą w wyszukiwaniu binarnym. Czyli należy dzielić pozostały zakres na pół i przechodzić do kolejnego zgadywania. Jeśli kroki będą zbyt niskie, może nie udać się odgadnąć flagi w 10 krokach.