programming/sillygoose

267 points

Writeup by Aryan

We have to find a number between 1 and 10^500, and we have 500 guesses. After each guess, we are told if our number is higher or lower than the target number.

It is a trivial binary search problem because the server tells if our guess is higher or lower than the target number. We can solve in ceil(log_2(10^100)) = 333 queries at most, well under the limit of 500.

import socket

def binary_search(low, high):
    while low <= high:
        mid = (low + high) // 2
        guess = str(mid)
        print(f"Trying {guess}")
        s.send((guess + '\n').encode())
        response = s.recv(1024).decode().strip()

        if "congratulations" in response:
            return "Flag below!\n" + response
        elif "too large" in response:
            high = mid - 1
        elif "too small" in response:
            low = mid + 1
        elif "time" in response or "skill issue" in response:
            return response

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('24.199.110.35', 41199))
print(binary_search(0, 10**100))
s.close()

Flag: n00bz{y0u_4r3_4_sm4rt_51l1y_g0053}