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
