guessr_solve.py

from pwn import *

M = 2**31
A = 7**6
C = 5

# bisect the possible set of correct numbers
def get_next_guess(low, high):
   return low+(high-low)/2

# binary search to guess the next correct number
def get_next_output(conn, low, high):
   conn.readuntil('go ahead and guess!\n')
   while True:
      current_guess = get_next_guess(low, high)
      conn.sendline(str(current_guess))
      answer = conn.readline()
      if answer.find('Correct') != -1:
         return current_guess
      elif answer.find('too low') != -1:
         low = current_guess
      elif answer.find('too high') != -1:
         high = current_guess
      else:
         exit('Got weird answer: {}'.format(answer))

# calculate all possible internal LCG states     
def get_possible_states(output):
   return range(output-1, M, 100)

# step to next LCG state
def get_next_prng_state(current):
   return (A * current + C) % M

# check to see if a potential internal state matches the external state
def is_state_valid(state, output):
   return (state % 100) + 1 == output
   
r = remote('challenges.hackover.h4q.it', 64500)

# Get an initial output so we can build a list of potential states
print 'Guessing initial number...'
output = get_next_output(r, 1, 101)
print 'Debug: output = {}'.format(output)

# Since we have a reasonable number (2**31)/100 to brute force, let's do this the dumb way
possible_states = get_possible_states(output)
print 'Debug: possible_states...'
print repr(possible_states[:10])

# Keep iterating each potential state and discarding states which don't produce the current output
# until only one state remains, which must be the real internal state
while len(possible_states) > 1:
   output = get_next_output(r, 1, 101)
   print 'Got another output.'
   possible_states = map(get_next_prng_state, possible_states)
   possible_states = filter(lambda x: is_state_valid(x,output), possible_states)
   print 'Number of possible states remaining: {}'.format(len(possible_states))

if len(possible_states) == 0:
   exit('Something went wrong, no correct states found.')

# We now have our real state, let's use it!
state = get_next_prng_state(possible_states[0])

# Using our recovered LCG state, win on the first try every time
# fukkin 360 noscope
while True:
   print r.readline()
   r.sendline(str(state % 100 + 1))
   print r.readline()
   state = get_next_prng_state(state)