Skip to content

Instantly share code, notes, and snippets.

@hellman
Last active July 9, 2017 09:08
Show Gist options
  • Save hellman/28aa45b7645a8f71c68c6429c64090c4 to your computer and use it in GitHub Desktop.
Save hellman/28aa45b7645a8f71c68c6429c64090c4 to your computer and use it in GitHub Desktop.
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