XMAS CTF 2018 Let’s Crack the Greater lapland monolith

less than 1 minute read

XMAS CTF 2018 Let’s Crack the Greater lapland monolith

Let’s Crack the Greater lapland monolith by Johannes

The first step is to find the modulus to calculate other values of LCG.

One feature of Linear Congruent Generators is that the modulus in most cases is equal to greatest common divisor of the generated values.

Therefore, I took 10 generated values and did gcd(a1,a2,a3 ...)which gives us the modulus.

The other step is to get the multiplier.

We have two equations a1=a*mult+inc (mod modul) a2=a1*mult+inc (mod modul). From here we obtain that mult = (a2-a1)/(a1-a0);

The last step is to crack the increment and it is pretty easy. a1=a*mult+inc (mod modul) --> inc = a1-a*mult (mod modul)

Yeah we finally cracked the LCG, now we can submit the values into the field and get our flag.