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

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:

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:

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:

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:

$ 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}