# [Crypto] VolgaCtf2019 - LG

LG 100

Description:
WazzUP! My homie bought a new UltraSmartTV, but he forgot a secret key from an admin panel.

After a few attempts to crack this “smart” IoT device it started to generate new passwords on its own, and now we are stuck.

### Identifying the problem

The first time I read the description of this task didn’t helped me at all I mean a LG television ? After doing connection with the server I saw the server was giving us some random numbers and asked us to predict the next. Well after this I remembered last year I was looking at an attack against Linear Congruential Generators (LCG) and I thought to myself this is probably a LCG because the title is similar LG.

### What is a LCG ?

LCG can be defined as: Where:

• X(n) is a sequence of pseudo random values.
• p is modulo defined as 0 < p
• a is the multiplier defined as 0 < a < p
• c is the increment 0 <= c < p ( if c = 0 the LCG is called Multiplicative Congruential Generator)

An example implementation of LCG in python:

We have no knowledge of a,c and p and initial seed for x was chosen randomly, this attack is based in George Marsaglia analyzed Pseudo Random Number Generators in which he found a flaw in LCG.

This can be done with 2x2 matrix or a 3x3 matrix, I used 2x2 matrix like this guy from here .

For example if the out of the generated sequence is:

From 7 numbers we can generate 4 2x2 matrices like this: If you wanted to do with 3x3 matrices they could be formed like this: The determinant of the matrix is an integer multiple of the modulus p used in LCG. The gcd of two random multiples of p will be p with probability 6/π^2 = 0.61 and if you take the gcd of all of this integers it should provide us the real modulus p with a higher probability. To calculate each determinant of the matrices above you need remember something from linear algebra classes, calculating a determinant from a 2x2 matrix is pretty trivial this can be done with this formula: Note that if you choose to go with the 3x3 matrices the calculation is in a different way.

Now the GCD of these matrices should provide us with the real modulus p:

Knowing p we can find a and c by solving simple equations:

Finding a: Finding c: The next number is given by: The equivalent code to solve this is:

Running it:

The flag was VolgaCTF{pR3d1ct1ng_1s_n0t_oNlY_f0r_0O0rAculs}