X-MAS CTF 2018 - Let's Crack the Great(er) lapland monolith

crypto
, ,

These are two very similar challenges: the first one has a bug so that you can solve it in an unintended way, so the organizers realized a second “fixed” challenge. The following method works for both of them.

We’re given a web page that gets a random integer and asks us to guess it, multiple times. After guessing correctly 20 times, it will return a flag.

Solution

From the title we can see that the prng is of lcg type (linear congruential generator), that is, given 3 integers and a seed , the sequence is constructed as . It turns out that the website tells you what value it randomized even if you fail, so observing about 10 values we can break the prng as follows:

  • Construct a sequence
  • Observe that
  • Retrieve
  • Retrieve
  • Retrieve

We did this using the Python script from msm from p4team and then did it on the website by hand (input 20 times is faster than scripting). Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from functools import reduce
from gmpy2 import gcd

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def modinv(b, n):
    g, x, _ = egcd(b, n)
    if g == 1:
        return x % n

def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)

obs = [9933, 16949, 696, 30323, 33563, 25061, 14546, 13243, 12116]

n,k,d = crack_unknown_modulus(obs)
state = obs[-1]

while True:
    state = (state*k+d) % n
    print(state)
    input()