Cyber Apocalypse 2023 - The Cursed Mission (HTB CTF)
The Calibration challenge required the player to find the center of a circle on a coordinate plane with a range of -1 billion to +1 billion (x and y). The player was given 300 chances to find the center of the circle, and each guess the player received a detected or undetected response indicating whether their guess fell within the radius of the circle. The challenge consisted of 47 calibration iterations, with each iteration requiring the player to find a single point in the map that would be used as a reference. The calibrator could point at any location in the map and detect if its pointing at the reference point, or if the reference point is within its radius or not. The calibrator could only run up to 300 times in each iteration, and if the reference point was not found within 300 attempts, the calibrator stopped and the process had to be restarted. The coordinates (X, Y) of the reference point, as well as the radius R of the calibrator were unknown in each iteration. The calibrator had error correcting capabilities so it could point up to 2 galactic units away from the reference point and still return a REFERENCE response.
My strategy to solve this had two main parts.
-
Seed the field: I used about half of my guesses to get a rough estimate of the center of the circle by identifying each point that was detected as a hit. Then, I found the four points with the minimum and maximum x and y values among the hits, and took the midpoint of these points as the initial guess for the center of the circle.
-
Expand the circle: Starting with the x-max direction, I used a binary search algorithm to iteratively expand the circle in each direction. For each iteration, I found the midpoint between the hit with the greatest x value and the miss with the smallest x value that is still greater than the maximum hit x value. Then repeated for each direction. This strategy is similar to the "guess a number from 1-100" problem, where guessing midpoints allows one to guarantee the correct answer after six guesses.
Step 2 iterates for each direction ~20 times.
Each hit at this stage will move the boundaries, thus generating a new guess of center of the circle.
