Tags: lcg crypto
Rating: 2.0
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)
