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
2
3
4
5
6
7
8
9
10class LCGPrng(object):
def __init__(self, p, a, c):
self.p = p
self.a = a
self.c = c
self.x = random.randint(0, p)
def next(self):
self.x = (self.a*self.x + self.c) % self.p
return self.x
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18$ python lol.py
[+] Opening connection to lg.q.2019.volgactf.ru on port 8801: Done
64708864023319939604022646
51838154021189816354186379
22661473037375677492051015
67787858287294194078929082
65543613026965543757917756
68747435477887801975414929
52410286788865373905332250
--------------
83765940583638585693638595
9751638931180187
3802
Found: 83765940583638585693638595 as P, 9751638931180187 as a and 3802 as c
[+] Receiving all data: Done (64B)
[*] Closed connection to lg.q.2019.volgactf.ru port 8801
CONGRATULATIONS!
VolgaCTF{pR3d1ct1ng_1s_n0t_oNlY_f0r_0O0rAculs}
The flag was VolgaCTF{pR3d1ct1ng_1s_n0t_oNlY_f0r_0O0rAculs}