Polictf 2017 – Lucky Consecutive Guessing (Crypto)
#!/usr/bin/env python | |
import signal, random | |
import sys | |
class LinearCongruentialGenerator: | |
def __init__(self, a, b, nbits): | |
self.a = a | |
self.b = b | |
self.nbits = nbits | |
self.state = random.randint(0, 1 << nbits) | |
def nextint(self): | |
self.state = ((self.a * self.state) + self.b) % (1 << self.nbits) | |
return self.state >> (self.nbits - 32) | |
if __name__ == "__main__": | |
with open("flag", "r") as f: | |
flag = f.read() | |
multiplier = 0x66e158441b6995 | |
addend = 0xB | |
nbits = 85 # should be enough to prevent bruteforcing | |
generator = LinearCongruentialGenerator(multiplier, addend, nbits) | |
points = 10 | |
print "Welcome!" | |
print "Do you feel lucky? Try to guess the numbers I'm thinking of." | |
print "You have one minute to reach 20 points. Good Luck!" | |
sys.stdout.flush() | |
signal.alarm(60) | |
while points > 0 and points < 100: | |
print "You have {} points.".format(points) | |
sys.stdout.flush() | |
current_num = generator.nextint() | |
guess_num = None | |
while guess_num is None: | |
try: | |
print "Guess the next number:" | |
sys.stdout.flush() | |
guess_num = int(raw_input()) | |
except ValueError: | |
print "That's not a valid number!" | |
sys.stdout.flush() | |
if (guess_num == current_num): | |
print "That's correct!" | |
sys.stdout.flush() | |
points = points + 1; | |
else: | |
print "Wrong, the correct number was {}.".format(current_num) | |
sys.stdout.flush() | |
points = points -1; | |
if points <= 0: | |
print "You lost!" | |
sys.stdout.flush() | |
elif points >= 20: | |
print "Congratulations, you won!!" | |
print "Here is your flag: {}".format(flag) | |
sys.stdout.flush() | |
else: | |
print "Something went wrong..." | |
sys.stdout.flush() |
#-*- coding:utf-8 -*- | |
import random | |
class LinearCongruentialGenerator: | |
def __init__(self, a, b, nbits): | |
self.a = a | |
self.b = b | |
self.nbits = nbits | |
self.state = random.randint(0, 1 << nbits) | |
def nextint(self): | |
self.state = ((self.a * self.state) + self.b) % (1 << self.nbits) | |
return self.state >> (self.nbits - 32) | |
def split(x): | |
return ((x >> 53) % 2**32, x % 2**53 ) | |
MASK32 = 2**32-1 | |
MASK53 = 2**53-1 | |
MASK85 = 2**85-1 | |
a = 0x66e158441b6995 | |
b = 0xB | |
a1, a0 = split(a) | |
generator = LinearCongruentialGenerator(a, b, 85) | |
n1 = generator.nextint() | |
SECRET_STATE1 = generator.state | |
n2 = generator.nextint() | |
n3 = generator.nextint() | |
def recurse(h, t): | |
if t == 0: | |
# Final check of the candidate | |
s = (s1 << 53) | h | |
s = (a*s + b) & MASK85 | |
if s >> 53 != n2: | |
return | |
s = (a*s + b) & MASK85 | |
if s >> 53 != n3: | |
return | |
print "CORRECT!", h | |
return h | |
t -= 1 | |
h <<= 1 | |
for bit in xrange(2): | |
h |= bit | |
# delta = val - ( 2**t*h*a1 + 2**t*h*a0/2**53 ) % 2**32 | |
delta = val - ( (h+h+h<<t) + ((h*a0<<t)>>53) ) | |
delta &= MASK32 | |
if delta < 4*2**t: | |
res = recurse(h, t) | |
if res: | |
return res | |
# s1, s0 = split(SECRET_STATE1) | |
s1 = n1 | |
out = n2 | |
val = (out - s1*a0) % 2**32 | |
for top in xrange(2**24): | |
if top & 0xffff == 0: | |
print hex(top) | |
# top = s0 >> 29 | |
s0 = recurse(top, 29) | |
if s0: | |
print "Found solution!", s0 | |
break | |
mygen = LinearCongruentialGenerator(a, b, 85) | |
mygen.state = (s1 << 53) | s0 | |
assert mygen.nextint() == n2 | |
assert mygen.nextint() == n3 | |
for i in xrange(1000): | |
assert mygen.nextint() == generator.nextint() | |
print "Outputs predicted correctly" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment