We implemented a random number generator. We’ve heard that rand()’s 32 bit seeds can be easily cracked, so we stayed on the safe side.

It is required to guess the output of a rand(). The rand() source file is given. An example of a play is the following:

$ nc lucky.chall.polictf.it 31337
Do you feel lucky? Try to guess the numbers I'm thinking of.
You have one minute to reach 100 points. Good Luck!
You have 10 points.
Guess the next number:
0Wrong, the correct number was 1527358467.
You have 9 points.
Guess the next number:

Wrong, the correct number was 4237098583.
You have 8 points.
Guess the next number:
Wrong, the correct number was 3143302912.
You have 7 points.
Guess the next number:
Wrong, the correct number was 61247370.
You have 6 points.
Guess the next number:

Part of the source is the following:

   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)

    multiplier = 0x66e158441b6995
    addend = 0xB
    nbits = 85    # should be enough to prevent bruteforcing
    generator = LinearCongruentialGenerator(multiplier, addend, nbits)

It is a classic linear congruential generator, where the current random number is not the full state, but just the 32 most significant bits.

At the first comment here https://crypto.stackexchange.com/questions/10608/how-to-attack-a-fixed-lcg-with-partial-output is explained how to solve this challenge.

An here is the implementation:

mod = (1<<85)

def getstate(r0,r1,r2):
  t=((1<<53)*r1 - a*(1<<53)*r0 - b + (1<<53) - 1) % mod
  for k in range(1,((1<<53)*a-1-t)/mod):
    if ((t+mod*k)%a) < (1<<53):
        state = (t+(1<<85)*k)/a + (1<<53)*r0
        if (((state *a +b)%mod)*a+b)%mod >> 53 == r2:
            return state
  return 0

def next():
  global state
  state = (state*a+b)%mod
  return state >> 53

r1 = input()
r2 = input()
r3 = input()

state = getstate(r1,r2,r3)
for i in range(1,3):
for i in range(1,200):
  print next()