I’ve decided that I’m not going to do a full walkthrough of the Fall 2019 CNY Hackathon CTF challenges, but I did want to take some time to discuss my favorite challenge that we had the students tackle this semester. The challenge in question was titled “An Impossible Task?” and was brought to us by Spencer McClain from the Center for Internet Security.
The premise of the challenge was that there is a network service that pseudo-randomly chooses a number between 1 and 9,223,372,036,854,775,807 and the student must guess the correct number in less than 100 guesses. If they succeed, they are awarded a flag, but if they run out of guesses, the connection is terminated and a new number is chosen when the student re-connects.
Generally, this would be nearly impossible to accomplish, except that the network service returns one key piece of information when an invalid guess is entered:
The inclusion of the “too high/too low” in the response turns this challenge into a classic binary search. Therefore, in order to properly guess the correct number, the student must use the response from the service to narrow down the search space in each subsequent guess. Here’s how this might be accomplished in Python.
First, we define our initial upper and lower bounds, in this case 0 and 9223372036854775807 since we don’t have any information on the initial connection as to where in the space the chosen number is located. For each guess, we can add our lower bound and upper bounds, divide in half, and use that as our guess. Depending on the number chosen, we will get a response stating that our guess is too low or too high.
Based on the response, we have now eliminated half of the search space in one guess! If our guess was too high, we set the upper bound to the value of our guess, otherwise we set the lower bound to the value of the guess. In the next attempt, we perform the same calculation on our new upper and lower bounds. By nesting this in a loop, we can script out a program that will quickly solve this for us:
When we run this, we quickly find the number and receive our flag! Not so bad, right?