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

1
2
3
4
5
6
7
8
9
10
class 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
2
3
4
5
6
7
X(0) = 64302589647963933737451564
X(1) = 23099347408308738343740115
X(2) = 60779187967701597680605077
X(3) = 41531243105709646792416331
X(4) = 71461317334046189800115379
X(5) = 50094315434186546595562390
X(6) = 27719142972686291997765807

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
2
3
p0 = GCD(DeterminantOfMatrix0, DeterminantOfMatrix1)
p1 = GCD(p0, DeterminantOfMatrix2)
P = GCD(p1, DeterminantOfMatrix3)

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
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import sys
import math
import random
from pwn import *

def calc_det(i,j,X):
""" Calculate the values for the matrix[lattice] """
a1 = X[i] - X[0]
b1 = X[i+1] - X[1]
a2 = X[j] - X[0]
b2 = X[j+1] - X[1]

""" Calculate the determinant """
det = a1*b2 - a2*b1
return abs(det)

def GCD(a,b):
""" Euclidean Algo"""
a = abs(a)
b = abs(b)
while a:
a,b = long(b%a),a
return b

def modInverse(a, m):

if GCD(a, m) != 1:
return None # no mod inverse if a & m aren't relatively prime

u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3 # // is the integer division operator
v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
return u1 % m

def main():
while True:
try:
X = []
r = remote('lg.q.2019.volgactf.ru', 8801)
r.recvuntil("Try this:\n")
for i in xrange(7):
n =int(r.recvline().strip())
print n
X.append(n)
r.recvuntil(">>>")
print '--------------'

Det_X = []
Det_X.append(calc_det(1,2,X))
#print Det_X
Det_X.append(calc_det(2,3,X))
#print Det_X
Det_X.append(calc_det(3,4,X))
#print Det_X
Det_X.append(calc_det(4,5,X))
#print Det_X

found_p = reduce(GCD, Det_X)

# To find 'a' and 'c' we need to solve the simple equation:
# a = ((x3 - x4)*INVERSE_MODULE((x2-x3),p))%p
# And:
# c = (x4 - a*x3)%p
# Where x2, x3, x4 are all numbers generated by the LCG that we got already!

mod_inv_a = modInverse((X[2]-X[3]), found_p) # Here we find the modular inverse of x2-x3 with modulo p
found_a = ((X[3] - X[4])*mod_inv_a)%found_p
print found_a #found_a will be the correct a with high probability.

found_c = (X[4] - found_a*X[3])%found_p
print found_c #found_c will be the correct a with high probability, clearly depending on the correctness of a

print "Found: %d as P, %d as a and %d as c" % (found_p, found_a, found_c)
r.sendline(str((found_a * X[-1] + found_c) % found_p))
print r.recvall()
r.close()
break
except TypeError:
r.close()

if __name__ == "__main__":
sys.exit(main())

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}