HackYou 2014 - Crypto 300 - Do you like math? Write-up

Do you like math?

We have an encrypted flag.wmv.out file and this python script:

#!/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')

To solve this challenge, analyzing the WMV file type is important.

The header of a WMV (ASF container actually) starts with a well-know 16 bytes sequence: the header GUID

So we know 16 bytes of plaintext and 16 bytes of corresponding ciphertext : that’s enough to calculate the key

C = K * X
K = X-1 * C
P = K-1 * C

Here is a script automating this:

#!/usr/bin/python
from struct import pack,unpack
from numpy.linalg import inv

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 Words2matrix(s):
#convert words to 4x4 matrix
return [map(lambda x: 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('!B', (y+0.05) % 256), x)), m))

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 to_words(string):
i=0
data = []
while i<len(string):
h = string[i:i+2]
data.append(unpack('!H', h)[0])
i+=2
return data

def Decrypt(fname):
data = open(fname, 'rb').read()

# WMV GUID header
plain = Str2matrix("30 26 b2 75 8e 66 cf 11 a6 d9 00 aa 00 62 ce 6c".replace(" ", "").decode("hex"))
cipher = Words2matrix(to_words(data[4:4 + 32]))

inv_plain = inv(plain)
print "inv plain=", repr(inv_plain)

key = Multiply(inv_plain, cipher)
print "key=", repr(key)

inv_key = inv(key)
print "inv_key=", repr(inv_key)

out = open('flag.wmv', 'wb')
for i in xrange(4, len(data) - 4, 32):
cipher = Words2matrix(to_words(data[i:i + 32]))
print "cipher=", repr(cipher)
plain = Multiply(cipher, inv_key)
print "plain=", repr(plain)
out.write(Matrix2str(plain))
out.close()

Decrypt('flag.wmv.out')