Instantly share code, notes, and snippets.

# hellman/chall.py

Last active July 9, 2017 09:08
Show Gist options
• Save hellman/28aa45b7645a8f71c68c6429c64090c4 to your computer and use it in GitHub Desktop.
Polictf 2017 – Lucky Consecutive Guessing (Crypto)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/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()
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #-*- 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<>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"