[HACKYOU 2014] Crypto200 - HashMe

So in this challenge, you are given a python script and the address of a server where the script is being run. Upon inspecting the script you can see that it allows you to register and also to log in. When a user logs in as an administrator, the script will automatically spit out the password. However, in the script given to us, the KEY and SALT have both been removed.

	#!/usr/bin/python
	from math import sin
	from urlparse import parse_qs
	from base64 import b64encode
	from base64 import b64decode
	from re import match
	SALT = ''
	USERS = set()
	KEY = ''.decode('hex')
	def xor(a, b):
	return ''.join(map(lambda x : chr(ord(x[0]) ^ ord(x[1])), zip(a, b * 100)))
	def hashme(s):
	#my secure hash function
	def F(X,Y,Z):
	return (~X & Z) & 0xFFFFFFFF
	def G(X,Y,Z):
	return ((X & Z) | (~Z & Y)) & 0xFFFFFFFF
	def H(X,Y,Z):
	return (X) & 0xFFFFFFFF
	def I(X,Y,Z):
	return (Y ^ (~Z | X)) & 0xFFFFFFFF
	def ROL(X,Y):
	return (X << Y | X >> (32 - Y)) & 0xFFFFFFFF
	A = 0x67452301
	B = 0xEFCDAB89
	C = 0x98BADCFE
	D = 0x10325476
	X = [int(0xFFFFFFFF * sin(i)) & 0xFFFFFFFF for i in xrange(256)]
	for i,ch in enumerate(s):
	k, l = ord(ch), i & 0x1f
	A = (B + ROL(A + F(B,C,D) + X[k], l)) & 0xFFFFFFFF
	B = (C + ROL(B + G(C,D,A) + X[k], l)) & 0xFFFFFFFF
	C = (D + ROL(C + H(D,A,B) + X[k], l)) & 0xFFFFFFFF
	D = (A + ROL(D + I(A,B,C) + X[k], l)) & 0xFFFFFFFF
	print '%x %x %x %x'%(B,A,D,C)
	return ''.join(map(lambda x : hex(x)[2:].strip('L').rjust(8, '0'), [B, A, D, C]))
	def gen_cert(login):
	global SALT, KEY
	s = 'login=%s&role=anonymous' % login
	s += hashme(SALT + s)
	s = b64encode(xor(s, KEY))
	return s
	def register():
	global USERS
	login = raw_input('Your login: ').strip()
	if not match('^[\w]+$', login):
	print '[-] Wrong login'
	return
	if login in USERS:
	print '[-] Username already exists'
	else:
	USERS.add(login)
	print '[+] OK\nYour auth certificate:\n%s' % gen_cert(login)
	def auth():
	global SALT, KEY
	cert = raw_input('Provide your certificate:\n').strip()
	try:
	cert = xor(b64decode(cert), KEY)
	auth_str, hashsum = cert[0:-32], cert[-32:]
	data = parse_qs(auth_str, strict_parsing = True)
	x = hashme(SALT + auth_str)
	s = auth_str+x
	print b64encode(xor(s, KEY))
	if hashme(SALT + auth_str) == hashsum:
	data = parse_qs(auth_str, strict_parsing = True)
	print '[+] Welcome, %s!' % data['login'][0]
	if 'administrator' in data['role']:
	flag = open('flag.txt').readline()
	print flag
	else:
	print '[-] Auth failed'
	except:
	print '[-] Error'
	def start():
	while True:
	print '======================'
	print '[0] Register'
	print '[1] Login'
	print '======================'
	num = raw_input().strip()
	if num == '0':
	register()
	elif num == '1':
	auth()
	start()

view raw crypto200.py hosted with ❤ by GitHub

When a user registers, he is given a certificate that he can use to log in to the system; this certificate consisting of the user's username, role, hash of the username and role, all xor'ed against the KEY and then base64 encoded. Since we have access to the certificate post-xor and we do know what part of the plaintext was ( the username and the role ), we can recover the KEY. We can manipulate the username to be as long as necessary in order to recover the entire key.

	import base64
	login = 'a'*500
	s = 'login=%s&role=anonymous' % login
	cert = 'RK5yZMJaZTlcDXBExkxd5kV/HjX2iNltGZWvSmm9ykpsk2qByr9qdjBL8jqmBAEdlIRJoHRszQZlOVwNcETGTF3mRX8eNfaI2W0Zla9Kab3KSmyTaoHKv2p2MEvyOqYEAR2UhEmgdGzNBmU5XA1wRMZMXeZFfx419ojZbRmVr0ppvcpKbJNqgcq/anYwS/I6pgQBHZSESaB0bM0GZTlcDXBExkxd5kV/HjX2iNltGZWvSmm9ykpsk2qByr9qdjBL8jqmBAEdlIRJoHRszQZlOVwNcETGTF3mRX8eNfaI2W0Zla9Kab3KSmyTaoHKv2p2MEvyOqYEAR2UhEmgdGzNBmU5XA1wRMZMXeZFfx419ojZbRmVr0ppvcpKbJNqgcq/anYwS/I6pgQBHZSESaB0bM0GZTlcDXBExkxd5kV/HjX2iNltGZWvSmm9ykpsk2qByr9qdjBL8jqmBAEdlIRJoHRszQZlOVwNcETGTF3mRX8eNfaI2W0Zla9Kab3KSmyTaoHKv2p2MEvyOqYEAR2UhEmgdGzNBmU5XA1wRMZMXeZFfx419ojZbRmVr0ppvcpKbJNqgcq/anYwS/I6pgQBHZSESaB0bM0GZTlcDXBExkxd5kV/HjX2iNltGZWvSmm9ykpsk2qByr9qdjBL8jqmBAEdlIRJoHRszQYiKlIAdBjGQ1PpXXMQIeTQ22lMla8eau7JTTrFO9TP7D4uZUvxa/8EAknAhx2lLQ=='
	cert_bytes = base64.b64decode(cert)
	auth_str_bytes = cert_bytes[:len(s)]
	key = map(lambda (x,y): (ord(x)^ord(y)), zip(auth_str_bytes,s) )
	key = key[:50]
	key = ''.join(map(lambda x: str(hex(x))[2:].rjust(2,'0'),key))
	print key

view raw key_calc.py hosted with ❤ by GitHub

Using this method, I found the key to be 28c1150dac6704583d6c1125a72d3c87241e7f5497e9b80c78f4ce2b08dcab2b0df20be0abde0b17512a935bc765607cf5e5 when hex encoded.

Now that we have the key, we're free to obtain the auth string and the hash from any certificate issued by that particular script on that server. Looking closely at the code, it doesn't seem likely that obtaining the SALT is possible but we do see that the code searches for "administrator" in the data['role'] list. What this tells us is that it is possible for us to successfully pass the admin check even if we have more than one role present in our auth string.

It turns out that we can simply add "&role=administrator" to the end of the auth string and that works out fine. However, we still have to deal with the md5 hash of that auth string. Luckily for us, the hashing algorithm used in the script is vulnerable to a length extension attack. We can use the hash given to us in the certificate ( using the key we recovered earlier ), to discover the internal state ( A,B,C,D ) of the hashing function at the end of its operation. We can then use that state in place of the IV we usually start with and continue to hash our newly added role.

However, the hashing algorithm state, depends not only on A,B,C and D but also on the number of bytes processed up to that point (modulo 32). At this point, this value is purely dependent on the length of the SALT which is still unknown to us but we know that there are only 32 possible values for this aspect of the state and therefore it can be bruteforced.

	import socket
	import base64
	import itertools
	from struct import pack,unpack
	from math import sin
	def get_cert(login_name):
	#GET CERT
	sock = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
	sock.connect((address,port))
	sock.recv(256)
	sock.recv(256)
	sock.send('0\n')
	sock.recv(256)
	sock.send(login_name+'\n')
	sock.recv(256)
	data = sock.recv(512).split(':')[1]
	data = data.split('\r')[1]
	sock.close()
	cert = data
	return cert
	def cert_login( cert ):
	#LOGIN WITH CERT
	ret = ()
	sock = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
	sock.connect((address,port))
	sock.recv(256)
	sock.recv(256)
	sock.send('1\n')
	sock.recv(256)
	sock.send(cert+'\n')
	sock.recv(256)
	data = sock.recv(512)
	if 'Welcome' in data:
	flag_pos = data.find('CTF')
	flag = data[ flag_pos: flag_pos+37 ]
	ret = (True,flag)
	else:
	ret = (False,'')
	sock.close()
	return ret
	def gen_certs():
	global KEY, s
	certs = []
	for i in range(0,32):
	auth_str = s
	salt_len = i
	prev_len = len(auth_str) + salt_len
	auth_str += '&role=administrator'
	auth_str += hashme(mhash,'&role=administrator',prev_len)
	auth_str = base64.b64encode(xor(auth_str, KEY))
	certs.append(auth_str)
	return certs
	def xor(a, b):
	return ''.join(map(lambda x : chr(ord(x[0]) ^ ord(x[1])), zip(a, b * 100)))
	def hashme(mhash,s,prev_len):
	#my secure hash function
	def F(X,Y,Z):
	return ((~X & Z) | (~X & Z)) & 0xFFFFFFFF
	def G(X,Y,Z):
	return ((X & Z) | (~Z & Y)) & 0xFFFFFFFF
	def H(X,Y,Z):
	return (X ^ Y ^ Y) & 0xFFFFFFFF
	def I(X,Y,Z):
	return (Y ^ (~Z | X)) & 0xFFFFFFFF
	def ROL(X,Y):
	return (X << Y | X >> (32 - Y)) & 0xFFFFFFFF
	B = int(mhash[0:8],16)
	A = int(mhash[8:16],16)
	D = int(mhash[16:24],16)
	C = int(mhash[24:32],16)
	X = [int(0xFFFFFFFF * sin(i)) & 0xFFFFFFFF for i in xrange(256)]
	for i,ch in enumerate(s):
	k, l = ord(ch), (i+prev_len) & 0x1f
	A = (B + ROL(A + F(B,C,D) + X[k], l)) & 0xFFFFFFFF
	B = (C + ROL(B + G(C,D,A) + X[k], l)) & 0xFFFFFFFF
	C = (D + ROL(C + H(D,A,B) + X[k], l)) & 0xFFFFFFFF
	D = (A + ROL(D + I(A,B,C) + X[k], l)) & 0xFFFFFFFF
	return ''.join(map(lambda x : hex(x)[2:].strip('L').rjust(8, '0'), [B, A, D, C]))
	KEY = '28c1150dac6704583d6c1125a72d3c87241e7f5497e9b80c78f4ce2b08dcab2b0df20be0abde0b17512a935bc765607cf5e5'.decode('hex')
	login_name = 'rik'
	address = 'hackyou2014tasks.ctf.su'
	port = 7777
	#GET CERT
	cert = get_cert(login_name)
	cert = base64.b64decode(cert)
	cert = ''.join(map( lambda (x,y): chr(ord(x)^ord(y)), zip(cert,itertools.cycle(KEY))))
	mhash = cert[-32:]
	s = cert[0:-32]
	certs = gen_certs()
	for i,cert in enumerate(certs):
	print "Attempt %d: %s"%(i,cert)
	result = cert_login(cert)
	if result[0] == True:
	print '\n\nSuccess: %s'%result[1]
	break
	else:
	print 'Cert failed!'

view raw 200pwn.py hosted with ❤ by GitHub

Using the script above, I was able to generate the 32 candidate certificates for a particular user that comply with the SALT and KEY present in the script on the server. The 21st certificate was accepted, meaning that the length of the SALT was 20 bytes and then the flag was spit out.

[HACKYOU 2014] crypto300 - Matrix

So for this crypto challenge, you're given a file, encrypter.py, and another file, flag.wmv.out. Looking at the encrypter file, you can tell that the original file is broken up into blocks of 16 bytes each which are then transformed into 4x4 matrices. Each of these matrices is then multiplied by a key that was generated earlier and the resulting matrix is turned back into a string of bytes and written to the output file.

	#!/usr/bin/python
	import random
	from struct import pack
	from struct import unpack
	from scipy import linalg
	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 mMatrix2str(m):
	return ''.join(map(lambda x : ''.join(map(lambda y : pack('!B', 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):
	print Str2matrix(data[i:i+16])
	cipher = Multiply(Str2matrix(data[i:i+16]), key)
	out.write(Matrix2str(cipher))
	out.close()
	Encrypt('sample.wmv')

view raw encrypter.py hosted with ❤ by GitHub

The key to this challenge was to take a look at the specification for the file format.

A WMV file is in most circumstances encapsulated in the Advanced Systems Format (ASF) container format.

Looking at the ASF specification, these types of file usually start with a 16 byte GUID that identifies the file type. This hints at a known-plaintext attack. Using some basic linear algebra, given the plaintext and the ciphertext for the first 16 bytes of the file, it is possible to recover the key matrix. Once this key matrix is recovered, the rest of the file can be decrypted and the original wmv file can be recovered. The details of the steps involving the calculations are explained in comments in the code below.

	from scipy import linalg
	import numpy as np
	from struct import pack,unpack
	import sys
	filename = 'flag.wmv' if len(sys.argv)==1 else sys.argv[1]
	m_transform = np.frompyfunc(lambda x: int(round(x)),1,1)
	header_byte_seq = [0x30,0x26,0xB2,0x75,0x8E,0x66,0xCF,0x11,0xA6,0xD9,0x00,0xAA,0x00,0x62,0xCE,0x6C]
	#turn header_byte_seq into a 4x4 matrix
	hbs_matrix = np.array( header_byte_seq ).reshape(4,4)
	#get ciphertext
	ciphertext_file = open(filename+'.out','rb')
	ciphertext = ciphertext_file.read()
	ciphertext_file.close()
	#ciphertext was packed as a series of shorts
	#get length
	length = unpack('!I',ciphertext[0:4])[0]
	ciphertext = ciphertext[4:]
	#convert into list integers
	ciphertext = [ unpack('!H',ciphertext[i*2:i*2+2])[0] for i in range(0,length) ]
	#first 16 bytes hold the header guid
	hbs_ciphertext = ciphertext[0:16]
	#RECOVER KEY USED FOR ENCRYPTION
	# Let hbs_matrix = B
	# Let key = K
	# Let hbs_ciphertext = C
	# BK = C
	# (B^(-1)B)K = B^(-1)C
	# K = B^(-1)C
	B = hbs_matrix
	C = np.array(hbs_ciphertext).reshape(4,4)
	B_inverse = linalg.inv(B)
	K = m_transform(B_inverse.dot(C))
	#RECOVER ORIGINAL DATA GIVEN KEY AND CIPHERTEXT
	# BK = C
	# BK.K^(1) = C.K^(-1)
	# B = C.K^(-1)
	K_inverse = linalg.inv(K)
	plaintext = []
	for i in range(0,length/16):
	C = ciphertext[i*16:i*16+16]
	C = np.array(C).reshape(4,4)
	B = m_transform(C.dot(K_inverse))
	plaintext += [x for x in B.reshape(1,16)[0]]
	#WRITE DECRYPTED DATA TO FILE
	decrypted_file = open(filename,'wb')
	data = ''.join( pack('!B',x) for x in plaintext )
	decrypted_file.write(data)
	decrypted_file.close()

view raw hackyou_crypto300.py hosted with ❤ by GitHub

Once the file has been decrypted, the wmv file is playable and it reveals the flag.