Polictf 2017 – Lucky Consecutive Guessing

This is a short snippet to solve the LCG on Polictf’17. The basic idea is to reduce the problem aX_i + b = X_{i+1} \bmod M to aX_i = X_{i+1} \bmod M. This problem is quite easy to solve.

The basic idea is to view the problem as the latter and correct the discrepancies (\delta = (b, ab, a^2b,\dots)). So, for instance, if we sample

V = \texttt{1310585136, 1634517111, 2548394614, 745784911},

then these values contain the implicit discrepancies. By performing correction of the values (subtracting \sum_k^i \delta_k from the corresponding V_i we obtain a corrected value).

So, now we can use LLL to solve the simpler problem. Once a solution is found, we use the discrepancies to correct it to the case aX_i + b = X_{i+1} \bmod M.

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 break_lcg(a,b,p,i,j,outputs):
	deltas = [b % p, (a*b + b) % p, (a^2*b + a*b + b) % p, (a^3*b + a^2*b + a*b + b) % p]
	Y = [((val << (i - j)) )  for val, delta in zip(outputs, deltas)]
	L = matrix([
	    [  p,  0,  0,  0 ],
	    [a^1, -1,  0,  0 ],
	    [a^2,  0, -1,  0 ],
	    [a^3,  0,  0, -1]
	])
	B = L.LLL()
	Y = vector([x - y for x, y in zip(Y, deltas)])
	target = vector([ round(RR(w) / p) * p - w for w in B * vector(Y) ])
	states = list(B.solve_right(target))
	return [x + y + z for x, y, z in zip(Y, states, deltas)]

# parameters
p = 2^85
a = 0x66e158441b6995
b = 0xb
n = 85
r = 32
sequence = [1310585136, 1634517111, 2548394614, 745784911]

# break the LCG
start_seed = break_lcg(a,b,p,n,r,sequence)

# run it to sample required values
lcg = LinearCongruentialGenerator(a, b, n)
lcg.state = start_seed[0]
for i in range(0, 104):
	print lcg.nextint()
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s