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:

1 | class LCGPrng(object): |

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:

1 | X(0) = 64302589647963933737451564 |

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**:

1 | p0 = GCD(DeterminantOfMatrix0, DeterminantOfMatrix1) |

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:

1 | import sys |

Running it:

1 | $ python lol.py |

The flag was **VolgaCTF{pR3d1ct1ng_1s_n0t_oNlY_f0r_0O0rAculs}**