Hack You CTF 2014 - Crypto 300 - Matrix - [Team SegFault]

We were given source code of encryptor and an encrypted file flag.wmv.out. The encryption algorithm performs the following operation

[*] Generates a 4x4 matrix as key using randint() function. An secret password is used as seed, which we dont know
[*] File is padded with NUL such that size(file) % 16 == 0
[*] Each 16 bytes of file is converted to 4x4 matrix and multiplied with key
[*] Each element of resultant 4x4 matrix is packed into 2 bytes of data and written to file

First we should find the key to perform decryption. The file extension leaves a clue wmv. Using wmv header as known plain text and encrypted header as cipher text, the key could be found as wmv_header.inverse() * enc_header. Once the key found, we have to write decryption routine such that encrypted file is processed in blocks for 32 bytes in a 4x4 matrix. Below is the code to solve this

#!/usr/bin/env python

from sage.all import *
import struct

wmv_header = [[0x30, 0x26, 0xB2, 0x75], [0x8E, 0x66, 0xCF, 0x11], [0xA6, 0xD9, 0x00, 0xAA], [0x00, 0x62, 0xCE, 0x6C]]

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 : struct.pack('!B', y), x)), m))
def PackedStr2matrix(s):
    matrix = [0] * 16 
    for i in range(0, len(s), 2):
        matrix[i/2] = struct.unpack('!H', s[i:i+2])[0]
    matrix = [matrix[i:i+4] for i in range(0,len(matrix), 4)]
    return matrix
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
        
header =  matrix(wmv_header)
encrypted_wmv = open('flag.wmv.out','rb').read()
size = struct.unpack('!I', encrypted_wmv[:4])
enc_header = encrypted_wmv[4:36]
enc_header = matrix(PackedStr2matrix(enc_header))

# sage: header = matrix([[48, 38, 178, 117], [142, 102, 207, 17], [166, 217, 0, 170], [0, 98, 206, 108]])
# sage: enc_header = matrix([[6025, 10758, 8274, 14059], [10718, 11769, 5025, 15260], [19537, 18796, 14142, 15035], [7648, 8842, 7254, 17852]])
# sage: header.inverse() * enc_header
# [31 51 20  0]
# [53 10  6 45]
# [ 3 13  3 49]
# [17 48 56 31]
# sage: key.inverse()
# [  5732/2519421  96221/5038842 -41017/2519421 -10009/5038842]
# [ 65399/2519421 -67381/5038842  44957/2519421 -44311/5038842]
# [-49681/2519421  22679/5038842 -51064/2519421 128507/5038842]
# [-14660/2519421  10597/5038842  45127/2519421   4501/5038842]

key = header.inverse() * enc_header
key_inverse = key.inverse()

out = open('flag.wmv','wb')
encrypted_wmv = encrypted_wmv[4:]

for i in xrange(0, len(encrypted_wmv), 32):
    unpacked_data = matrix(PackedStr2matrix(encrypted_wmv[i:i+32]))
    decrypted = unpacked_data * key_inverse
    out.write(Matrix2str(decrypted))
out.close()

# CTF{b699a72e2692d16f65ec9626055aa740}

We get a decrypted wmv file which has the flag.

root@sagepc:~ $file flag.wmv
flag.wmv: Microsoft ASF

Flag for the challenege is CTF{b699a72e2692d16f65ec9626055aa740}