Polictf 2017 – Lucky Consecutive Guessing (Crypto)

chall.py

#!/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()

solve_truncated_lcg.py

#-*- 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"