from pwn import *
M = 2**31A = 7**6C = 5
# bisect the possible set of correct numbersdef get_next_guess(low, high):   return low+(high-low)/2
# binary search to guess the next correct numberdef 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 statedef get_next_prng_state(current):   return (A * current + C) % M
# check to see if a potential internal state matches the external statedef 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 statesprint '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 waypossible_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 statewhile 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 noscopewhile True:   print r.readline()   r.sendline(str(state % 100 + 1))   print r.readline()   state = get_next_prng_state(state)