In this level we are presented with a crypto system based on Matrix operations:

#!/usr/bin/python
import random  
from struct import pack

def Str2matrix(s):  
    #convert string to 4x4 matrix
    return [map(lambda x : ord(x), list(s[i:i+4])) for i in xrange(0, len(s), 4)]

def Matrix2str(m):  
    #convert matrix to string
    return ''.join(map(lambda x : ''.join(map(lambda y : pack('!H', y), x)), m))

def Generate(password):  
    #generate key matrix
    random.seed(password)
    return [[random.randint(0,64) for i in xrange(4)] for j in xrange(4)]

def Multiply(A,B):  
    #multiply two 4x4 matrix
    C = [[0 for i in xrange(4)] for j in xrange(4)]
    for i in xrange(4):
        for j in xrange(4):
            for k in xrange(4):
                C[i][j] += A[i][k] * B[k][j]
    return C

def Encrypt(fname):  
    #encrypt file
    key = Generate('')
    data = open(fname, 'rb').read()
    length = pack('!I', len(data))
    while len(data) % 16 != 0:
        data += '\x00'
    out = open(fname + '.out', 'wb')
    out.write(length)
    for i in xrange(0, len(data), 16):
        cipher = Multiply(Str2matrix(data[i:i+16]), key)
        out.write(Matrix2str(cipher))
    out.close()

Encrypt('flag.wmv')  

The Encrypt() function generates a 4x4 matrix based on a seed not providen. This matrix is used to encrypt a byte array. Here is how:

  • File to be encrypted is padded with 0 until its a factor of 16.
  • Then it is split in 16 bytes chunks that are reordened as 4x4 lists
  • Each of this 4x4 matrix is multiplied by the key matrix
  • The encrypted file is generated by appending the length of the encrpyted data and the encrypted bytes

Matrix multiplications are reversible using inverse matrixes so if E = P * K then P.I * E = P.I * P * K so K = P.I * E where:

  • P is a plaintext matrix
  • E is a encrypted matrix of plaintext matrix
  • P.I is the inverse of P

So if we want to extract the key we need to know at least one plaintext 4x4 matrix (P). Fortunately for us the file we need to decrypt is "flag.wmv.out" sounds like it is a WMV file and we know that its magic number is:

3026b2758e66cf11a6d900aa0062ce6c  

Thats exactly 16 bytes :D So to extract the key:

#!/usr/bin/python
import random  
from struct import pack  
from struct import unpack  
from numpy import *

def Str2matrix(s):  
    return [map(lambda x : ord(x), list(s[i:i+4])) for i in xrange(0, len(s), 4)]

def DecStr2matrix(s):  
    matrix = []
    row = []
    rowcount = 0
    for i in xrange(0, len(s), 2):
        item = int(s[i:i+2].encode("hex"),16)
        row.append(item)
        rowcount += 1
        if rowcount==4:
            rowcount=0
            matrix.append(row)
            row=[]
    return matrix

def Matrix2str(m):  
    return ''.join(map(lambda x : ''.join(map(lambda y : pack('!H', y), x)), m))

def DecMatrix2str(m):  
    return ''.join(map(lambda x : ''.join(map(lambda y : pack('!B', y), x)), m))

def Generate(password):  
    random.seed(password)
    return [[random.randint(0,64) for i in xrange(4)] for j in xrange(4)]

def Multiply(A,B):  
    C = [[0 for i in xrange(4)] for j in xrange(4)]
    for i in xrange(4):
        for j in xrange(4):
            for k in xrange(4):
                C[i][j] += A[i][k] * B[k][j]
    return C

def Encrypt(fname,mkey):  
    key = Generate(5)
    data = open(fname, 'rb').read()
    length = pack('!I', len(data))
    while len(data) % 16 != 0:
        data += '\x00'
    out = open(fname + '.out', 'wb')
    out.write(length)
    for i in xrange(0, len(data), 16):
        cipher = Multiply(Str2matrix(data[i:i+16]), key)
        mclear = matrix(Str2matrix(data[i:i+16]))
        mcipher = matrix(cipher)
        mcipher = mclear*mkey
        out.write(Matrix2str(cipher))
    out.close()
    return cipher

def Decrypt(fname,key):  
    data = open(fname, 'rb').read()
    length = int(unpack('!I', data[0:4])[0])
    data = data[4:]
    out = open(fname + '.orig', 'wb')
    for i in xrange(0, len(data), 32):
        mdata = DecStr2matrix(data[i:i+32])
        clear = matrix(mdata)*key.I
        m = clear.round().tolist()
        m = [[int(item) for item in row] for row in m]
        out.write(DecMatrix2str(m))
    out.close()
    return clear

def ExtractKey(fname, clearstring):  
    data = open(fname, 'rb').read()
    cipher = data[4:36]
    clear = clearstring.decode("hex")
    mclear = matrix(Str2matrix(clear))
    mcipher = matrix(DecStr2matrix(cipher))
    mkey = mclear.I*mcipher
    return mkey

#Encrypt('flag.wmv')
ourkey = matrix(Generate(5))  
print"[+] Extract key"  
key = ExtractKey("flag.wmv.out", "3026b2758e66cf11a6d900aa0062ce6c")  
print("[+] Key:\n{0}".format(key))  
print"[+] Decrypt video"  
clear = Decrypt("flag.wmv.out",key)  

So running the script gets the vide decrypted:

alvaro@winterfell ~/D/h/crypto300> python crack2.py  
[+] Extract key
[+] Key:
[[ 31.  51.  20.   0.]
 [ 53.  10.   6.  45.]
 [  3.  13.   3.  49.]
 [ 17.  48.  56.  31.]]
[+] Decrypt video