[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.

[EBCTF Teaser] Crypto100

	#!/usr/bin/python
	import hashlib, string, sys
	ROUNDS = 20000
	def xor(a, b):
	l = min(len(a), len(b))
	return ''.join([chr(ord(x) ^ ord(y)) for x,y in zip(a[:l], b[:l])])
	def h(x):
	x = hashlib.sha256(x).digest()
	x = xor(x[:16], x[16:])
	return x
	def verify(x):
	return all([ord(c) < 127 for c in x])
	def crypt(msg, passwd):
	k = h(passwd)
	for i in xrange(ROUNDS):
	k = h(k)
	out = ''
	for i in xrange(0, len(msg), 16):
	out += xor(msg[i:i+16], k)
	k = h(k + str(len(msg)))
	return out
	def encrypt(msg, passwd):
	msg = crypt(msg, passwd)
	return msg.encode('base64')
	def decrypt(msg, passwd):
	msg = crypt(msg.decode('base64'), passwd)
	if verify(msg):
	return msg
	else:
	sys.stderr.write('Looks like a bad decrypt\n')
	sys.exit(1)
	if len(sys.argv) < 5 or sys.argv[1] not in ('encrypt', 'decrypt'):
	print 'Usage:\tcrypto.py encrypt <password> <infile> <outfile>'
	print '\tcrypto.py decrypt <password> <infile> <outfile>'
	sys.exit(1)
	op, passwd, infile, outfile = sys.argv[1:]
	inp = open(infile).read()
	if op == 'encrypt':
	ct = encrypt(inp, passwd)
	open(outfile, 'w').write(ct)
	elif op == 'decrypt':
	pt = decrypt(inp, passwd)
	open(outfile, 'w').write(pt)

view raw crypto.py hosted with ❤ by GitHub

	import hashlib, string, sys
	def h(x):
	x = hashlib.sha256(x).digest()
	x = xor(x[:16], x[16:])
	return x
	def xor(a, b):
	l = min(len(a), len(b))
	return ''.join([chr(ord(x) ^ ord(y)) for x, y in zip(a[:l], b[:l])])
	def crypt(msg, k):
	out = ''
	for i in xrange(0, len(msg), 16):
	out += xor(msg[i:i+16], k)
	k = h(k + str(len(msg)))
	return out
	def verify(x):
	return all([ord(c) < 127 for c in x])
	#plaintext = 'From: Baron van '
	plaintext = 'From: Vlugge Jap'
	print len(plaintext)
	#get first 16 bytes from msg002.enc
	file_contents = open('msg002.enc','r').read().decode('base64')
	ciphertext = file_contents[0:16]
	key = xor(plaintext,ciphertext)
	out = crypt(file_contents,key)
	if verify(out):
	print out
	else:
	print 'Bad decrypt!'

view raw dec.py hosted with ❤ by GitHub

[SIGINT CTF] RSA

	#!/usr/bin/env python
	from time import time
	from os import system
	from Crypto.PublicKey import RSA
	SEED = int(time())
	def randfunc(n):
	def rand():
	global SEED
	ret = SEED*0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35 + 1
	SEED = ret
	return (ret >> 0x10) & 0x7fff
	ret = ""
	while len(ret) < n:
	ret += chr(rand() & 0xff)
	return ret
	keypair = RSA.generate(1024, randfunc)
	with open("pub", "w") as pubfile, open("id_rsa", "w") as privfile:
	privfile.write(keypair.exportKey())
	pubfile.write(keypair.publickey().exportKey())
	system("ssh-keygen -m PKCS8 -i -f pub > id_rsa.pub && rm pub")

view raw genrsa.py hosted with ❤ by GitHub

	#!/usr/bin/python
	import sys
	import base64
	import struct
	filename = sys.argv[1]
	file_contents = open(filename,'rb').read()
	base64_encoded_info = file_contents.split(' ')[1]
	raw_bytes = base64.b64decode(base64_encoded_info)
	length = struct.unpack('>I',raw_bytes[0:4])[0]
	raw_bytes = raw_bytes[4:]
	data = raw_bytes[0:length]
	print 'Obtained string: %s'%(data)
	raw_bytes = raw_bytes[length:]
	exponent_size = struct.unpack('>I',raw_bytes[0:4])[0]
	print 'Exponent size: %d'%(exponent_size)
	raw_bytes = raw_bytes[4:]
	exponent = 0
	for i in range(0,exponent_size):
	exponent<<=8
	exponent += ord(raw_bytes[i])
	print 'Exponent: '+str(exponent)
	raw_bytes = raw_bytes[exponent_size:]
	modulus_size = struct.unpack('>I',raw_bytes[0:4])[0]
	raw_bytes = raw_bytes[4:]
	print 'Modulus size: %d'%(modulus_size)
	modulus = 0
	for i in range(0,modulus_size):
	modulus<<=8
	modulus += ord(raw_bytes[i])
	print 'Modulus: '+str(modulus)

view raw rsa_extract.py hosted with ❤ by GitHub

	from Crypto.PublicKey import pubkey
	from Crypto.Util import number
	import fractions
	import sys
	MIN_SEED = int(sys.argv[1])
	MAX_SEED = int(sys.argv[2])
	SEED = MAX_SEED
	def randfunc(n):
	def rand():
	global SEED
	ret = SEED*0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35 + 1
	SEED = ret
	return (ret >> 0x10) & 0x7fff
	ret = ""
	while len(ret) < n:
	ret += chr(rand() & 0xff)
	return ret
	correct_modulus = 133542334266816908873627788991135098836872531174929294246169531210661376429243860064170039541966242804413057715139822380296022355504905790916703933165069728724833411797448828615450127927989084469577103148831167203596018572102137170380105783557008648639360019823792278259940952368577709045086814405497576841683
	e = long(65537)
	bits = 1024
	debug = 1
	while MAX_SEED > MIN_SEED:
	SEED = MAX_SEED
	p = q = 1L
	while number.size(p*q) < bits:
	p = pubkey.getStrongPrime(bits>>1, e, 1e-12, randfunc)
	q = pubkey.getStrongPrime(bits - (bits>>1), e, 1e-12, randfunc)
	modulus = p*q
	gcd = fractions.gcd( modulus, correct_modulus )
	if gcd > 1:
	print 'GCD: %d\np: %d\nq: %d\n'%(gcd,p,q)
	break
	MAX_SEED-=1

view raw pwn_rsa.py hosted with ❤ by GitHub

	from Crypto.PublicKey import pubkey
	from Crypto.Util import number
	from Crypto.PublicKey import RSA
	from Crypto.PublicKey import _slowmath
	import fractions
	import sys
	import os
	e = long(65537)
	p = long(13097286606179453667665592444299109782484218865253457545521978739889248320232481682880143106432871469494586765663594908396375009598486558938138835723794021)
	q = long(10196183246368760603869192593971202143897281417220455881063414616103901438182656326076501376638806928762094749150020638960102206987607293047096627515275223)
	n = long(p*q)
	d = long(pubkey.inverse(e, (p-1)*(q-1)))
	key = _slowmath._RSAKey()
	key.e = e
	key.p = p
	key.q = q
	key.n = n
	key.d = d
	keypair = RSA._RSAobj(RSA.RSAImplementation(),key)
	with open("pub", "w") as pubfile, open("id_rsa", "w") as privfile:
	privfile.write(keypair.exportKey())
	pubfile.write(keypair.publickey().exportKey())
	os.system("ssh-keygen -m PKCS8 -i -f pub > id_rsa.pub && rm pub")

view raw key_gen.py hosted with ❤ by GitHub

What's in that wchar_t*?!

So I came across a situation yesterday where I wanted the contents of a wide character string while in GDB. Now for regular strings, GDB has the command 'x' which allows you to examine memory and it also takes a format specifier, so x/s usually does the job. Unfortunately, GDB doesn't have builtin support for printing wide character strings ( or maybe I missed it while going through the docs ). A quick search led me to results like this. Seemed a bit like overkill to me.

	(gdb) disas main
	Dump of assembler code for function main:
	0x08048596 <main+0>: push ebp
	0x08048597 <main+1>: mov ebp,esp
	0x08048599 <main+3>: sub esp,0x18
	0x0804859c <main+6>: and esp,0xfffffff0
	0x0804859f <main+9>: mov eax,0x0
	0x080485a4 <main+14>: sub esp,eax
	0x080485a6 <main+16>: cmp DWORD PTR [ebp+0x8],0x2
	0x080485aa <main+20>: je 0x80485ca <main+52>
	0x080485ac <main+22>: mov eax,DWORD PTR [ebp+0xc]
	0x080485af <main+25>: mov eax,DWORD PTR [eax]
	0x080485b1 <main+27>: mov DWORD PTR [esp+0x4],eax
	0x080485b5 <main+31>: mov DWORD PTR [esp],0x8048760
	0x080485bc <main+38>: call 0x80483b8 <printf@plt>
	0x080485c1 <main+43>: mov DWORD PTR [ebp-0x4],0x0
	0x080485c8 <main+50>: jmp 0x8048618 <main+130>
	0x080485ca <main+52>: call 0x804852d <pass>
	0x080485cf <main+57>: mov DWORD PTR [esp+0x8],0x64
	0x080485d7 <main+65>: mov eax,DWORD PTR [ebp+0xc]
	0x080485da <main+68>: add eax,0x4
	0x080485dd <main+71>: mov eax,DWORD PTR [eax]
	0x080485df <main+73>: mov DWORD PTR [esp+0x4],eax
	0x080485e3 <main+77>: mov DWORD PTR [esp],0x80491a0
	0x080485ea <main+84>: call 0x80483a8 <mbstowcs@plt>
	0x080485ef <main+89>: mov DWORD PTR [esp+0x4],0x8049140
	0x080485f7 <main+97>: mov DWORD PTR [esp],0x80491a0
	0x080485fe <main+104>: call 0x80483d8 <wcscmp@plt>
	0x08048603 <main+109>: test eax,eax
	0x08048605 <main+111>: jne 0x804860c <main+118>
	0x08048607 <main+113>: call 0x80484b4 <win>
	0x0804860c <main+118>: mov DWORD PTR [esp],0x8048795
	0x08048613 <main+125>: call 0x80483e8 <puts@plt>
	0x08048618 <main+130>: mov eax,DWORD PTR [ebp-0x4]
	0x0804861b <main+133>: leave
	0x0804861c <main+134>: ret

view raw wchars.asm hosted with ❤ by GitHub

So looking at the disassembly of main, we can see that one of the command line arguments passed to the program is converted to a wide character string and stored in a global ( I guess it could be static as well.. but meh ) buffer @ 0x80491a0. The contents of that string is already known so it isn't too interesting. Looking a little further down..

	0x080485ef <main+89>: mov DWORD PTR [esp+0x4],0x8049140
	0x080485f7 <main+97>: mov DWORD PTR [esp],0x80491a0
	0x080485fe <main+104>: call 0x80483d8 <wcscmp@plt>

view raw wchars_e1.asm hosted with ❤ by GitHub

Now we see a comparison taking place between our string and another string. What is it comparing it against? We can see that the string in question is stored in a global as well. In a small program, not containing many wide character strings, there's a very simple but imprecise way of finding out.
There is the linux strings command. Now by default strings will only print regular character strings that are at least 4 characters long and followed by an unprintable character. Luckily for us strings takes a switch which allows us to specify the type of encoding of the strings that we're looking for.

 -e --encoding={s,S,b,l,B,L} Select character size and endianness: s = 7-bit, S = 8-bit, {b,l} = 16-bit, {B,L} = 32-bit

So a strings -el <binary> will get us our answer, somewhere inside a mess of other things. In a small program, this shouldn't be too troublesome but in larger programs this could become annoying.

The better, more precise way to get this done is from within gdb itself. If they're using those wide char functions then libc is probably loaded and available and so the respective functions for printing wide character strings should also be available; wprintf in particular.

So all that is really necessary is to call wprintf and pass the address of the string as the argument.

	(gdb) call wprintf(0x8049140)
	$1 = 8
	(gdb) call fflush(stdout)
	SecretPW$2 = 0

view raw gdb_output.c hosted with ❤ by GitHub

Now since the output stream is buffered and is flushed when things like newlines are printed, to see our output we either have to print a newline or we can just flush stdout. A call to fflush() does the trick and we can see the contents of the string.

PlaidCTF - Crypto200 - Compression

  It's been a long time since I've blogged. I've been really busy with school and well... life in general.. as well a shift in focus. It sucks because before this weekend I can't remember the last time I actually made time for doing/learning anything sec-related. I feel like if I need a large chunks of uninterrupted free time to be able to get anything done and I just haven't had many of those chunks lately. I can't say I've been wasting time though. I've been investing a lot of time into developing my programming/problem solving skills in general ( mostly via competitive programming ) and that's always a good thing. I've been so out of the loop that I didn't even know that the Plaid CTF was starting until about an hour before it did ( so much for any kind of preparation! ). However, I can successfully say that I dedicated the vast majority of my time this weekend ( while ignoring assignments and the fact that finals are a little less than 2 weeks away) to participating in the CTF. I don't regret it at all. I can't remember the last time I've learned so much in such a short space of time and enjoyed it this much.

  I've been meaning to write something here for a while and now and I figured with me completing a few challenges in the CTF that I could do a writeup or two and see how it turns out. I mostly focused on the crypto challenges this time around. It's always been an area that I've been interested in but I've never really devoted a lot of time to so this was the perfect time; I was participating just for the fun of it and to learn, not competitively. Out of the few that I did solve, the one I enjoyed the most was the crypto200 - compression challenge. So here is my writeup :)


  The script above was provided to us for the challenge. The script in question was actually being run on one of their servers but with the PROBLEM_KEY and ENCRYPT_KEY set to their real values. From reading the comment on line 11, it becomes obvious what the goal is.

GOAL: Determine the PROBLEM_KEY

  At this point in time, the only information that we have about the problem key is that it's 20 characters long and it consists only of lowercase letters and underscores. The fact that they provided us witha charset hints towards the solution requiring some enumeration/bruteforcing.

  The next step, after determining what the goal was, was to take a closer look at the script and determine what it was doing.
Moving further down the script, the next thing we see is the encrypt function.

	def encrypt(data, ctr):
	aes = AES.new(ENCRYPT_KEY, AES.MODE_CTR, counter=ctr)
	return aes.encrypt(zlib.compress(data))

view raw compression-encrypt.py hosted with ❤ by GitHub

  Looking at the encrypt function we can see that it uses AES. A little background on that:
AES ( Advanced Encryption Standard ) is a symmetric block cipher. That just means that it operates on a fixed amount of data at a time and that it uses the same key for both encryption and decryption as opposed to asymmetric key encryption like RSA which uses different keys for encrypting and decrypting.

  Now with block ciphers, by design, they are only supposed to operate on one block of a fixed size. So what happens if there is more than one block?

Let's call our encryption function E, our key, K and we have two messages M₁ and M₂ and two ciphertexts C₁ and C₂
E_k(M₁) = C₁
E_k(M₂) = C₂

  The AES algorithm on its own is completely deterministic; for a given input ( k,M_x ) it will always produce the same output C_x. This is undesirable because it allows us to deduce something about the plaintext given the ciphertext. Just as an example( I'm not going to bother being technically accurate here ), consider that I had to encrypt the string "abccdeabcdef" and that a block size of 3 bytes was being used.

String: "abccdeabcdef"

Separated into 3 byte blocks: ["abc"]["cde"]["abc"]["def"]

  Now given that the block ["abc"] occurs twice, and the algorithm being completely deterministic, when looking at the ciphertexts for the different blocks, it will be quite noticeable that the same ciphertext occurs twice. Seeing that, we might not be able to deduce what exactly the plaintext was but we are able to deduce that whatever the plaintext was, it occurred at least twice within the string. Therefore we can deduce something about the plaintext by looking at the ciphertext and this is semantically insecure.

To combat this, when a block cipher with a particular key needs to be applied to more than one block, a mode of operation is necessary.

Taken from Wikipedia:

 A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than one block.^[

  Looking at the second parameter passed to AES.new(), we see AES.MODE_CTR otherwise known as Counter. This mode of operation essentially turns the block cipher into a stream cipher. The Counter is just required to produce a sequence which is guaranteed not to repeat for a long time ( usually an increment by 1 scheme is used ). In addition to the Counter, a Cryptographic Nonce is used. The nonce is usually generated from some random generator suitable for crypto purposes. The nonce is combined with the value from the counter because of the value from the counter being predictable.

  Now instead of encrypting the actual plaintext, the combination of the nonce and the counter value is encrypted instead to form the keystream. This keystream is then combined, in this case XOR'd, with the plaintext to form the ciphertext. The two diagrams below, taken from Wikipedia, illustrate the encryption and decryption processes.

However, one thing to keep in mind is that the plaintext passed to the encrypt function is compressed before it is actually encrypted. Keeping in mind that the name of the challenge was compression, it would probably be a good thing to keep in mind.

So far we know:

• The program uses AES encryption with a 256 bit key
• It uses CTR as it's mode of operation so it can be used on multiple blocks.
• The nonce used comes from Python's os.urandom().The Python doc's state that this function is suitable for generating random bytes of data suitable for cryptographic use. 
• The PROBLEM_KEY is 20 bytes long with a charset consisting of lowercase letters and underscores.
• The plaintext is compressed before it is encrypted.

It isn't feasible to bruteforce the key. 2^256 different permutations isn't something we want to bruteforce.
It isn't feasible to bruteforce the PROBLEM_KEY. 27^20 permutations also isn't something we want to bruteforce. This naive approach is not going to work.

Moving further down the script we see:

	def handle(self):
	nonce = os.urandom(8)
	self.wfile.write(nonce)

view raw compression-nonce.py hosted with ❤ by GitHub

As we connect to the server, the nonce is sent to us.

Does this help us at all?

We have the nonce and we can predict the counter values and therefore we know what's being encrypted to form the keystream. If we could figure out what the keystream was, it would be trivial to recover the plaintext. However, we don't have the AES encryption key so that isn't possible. I'm not sure why the nonce was sent but I think it was only really meant as a red herring but I could be very wrong.


Looking at the rest of the script we see mostly trivial details. The first four bytes we send to the server is interpreted as the length of the message about the follow. The server appends the PROBLEM_KEY to the data we send then first sends its length back to us followed by the encrypted version of the compressed data. The detail that really stands out here is that the PROBLEM_KEY is appended to the data.


Looking at what we have so far, it's probably not feasible to perform any sort of AES related attack. What do we have left? We know that the plaintext has the PROBLEM_KEY appended to it  before it is compressed and then encrypted.


We've already looked at the encryption so now let's take a look at the compression. The program uses the zlib library for compression. How does zlib work? A quick google search and some looking around will get you to this page which contains a sufficient explanation of the DEFLATE algorithm which zib uses. Essentially the DEFLATE algorithm uses Huffman Trees and LZ77 compression. The LZ77 compression algorithm looks for repeated substrings foward in the sequence up to a certain point and takes advantage of this redundancy. Instead of storing the same substring multiple times, at every repeated occurrence, it simply stores how far back the identical substring occurred and its length.

zlib.compress(our_data+PROBLEM_KEY) is what is taking place.

From the description of the DEFLATE algorithm, and with the knowledge of what is being compressed, it becomes clear what needs to be done. We can use the fact that the data is being compressed before it is encrypted to gather information about the plaintext and ultimately, the PROBLEM_KEY.

The length of the returned ciphertext should differ depending on how much of PROBLEM_KEY occurs in our string. Assuming that I had the first x-1 characters of the PROBLEM_KEY correct, appending the xth character would cause the length of the ciphertext take one of two values depending on whether the xth character was correct or not. The character that produced the shorter ciphertext would be the correct one.

	#!/usr/bin/python
	import zlib
	import sys
	PROBLEM_KEY = 'crime_sometimes_pays'
	print len(zlib.compress(sys.argv[1]+PROBLEM_KEY))

view raw ctest.py hosted with ❤ by GitHub

I wrote that small script solely for the purpose of experimenting to see how the length of the compressed data varied with my input. The first thing I tried to do was to determine the first character of the PROBLEM_KEY. I realized that the compression really only started kicking in when the string I chose had all four of its characters matching the first character of the PROBEM_KEY.

	rik@sec:~/ctf/plaid2013/compression$ python ctest.py aaaa
	30
	rik@sec:~/ctf/plaid2013/compression$ python ctest.py bbbb
	30
	rik@sec:~/ctf/plaid2013/compression$ python ctest.py cccc
	29
	rik@sec:~/ctf/plaid2013/compression$ python ctest.py dddd
	30

view raw ctest_tests hosted with ❤ by GitHub

After a little more experimentation, I realized that until I had at least the first four characters right I had to follow a certain pattern and from then on I could just append single characters and work with the respective lengths of the ciphertexts.

For example, if I knew c matched the first character. I would try cacacaca , cbcbcbcb, ... , c_c_c_c_ and pick the one that produced the smallest ciphertext. I did this until I had the first four characters and from there I took a much more straightforward route.

Below is the script I used to automate the process:

	import socket
	import itertools
	import struct
	import string
	import sys
	def send_data( rsocket, data ):
	length = struct.pack('I',len(data))
	rsocket.send(length)
	return rsocket.send(data)
	def recv_data( rsocket, data ):
	length = struct.unpack('I',rsocket.recv(4))[0]
	data = rsocket.recv(length)
	return length
	def purge_candidate_strings( candidate_strings, min_len ):
	return filter( lambda x: len(x)>=min_len, candidate_strings)
	candidate_strings = ['']
	if len(sys.argv) >= 2:
	candidate_strings = [sys.argv[1]]
	charset = 'abcdefghijklmnopqrstuvwxyz_'
	multiplier = 4
	perm_len = 1
	max_len = 0
	rsocket = socket.create_connection(("127.0.0.1",4433))
	nonce = rsocket.recv(8)
	while max_len < 20:
	num_candidates = len(candidate_strings)
	for i in range(0,num_candidates):
	min_ret_bytes = -1
	possible_candidates = []
	data = ''
	for possible_candidate in map( lambda x : candidate_strings[i]+x ,charset):
	send_data(rsocket, possible_candidate * (1 if max_len >= 4 else 4) )
	possible_candidates.append((possible_candidate, recv_data(rsocket, data) ))
	min_len = min( map( lambda x: x[1], possible_candidates) )
	possible_candidates,_ = zip(*filter( lambda x: x[1] == min_len , possible_candidates ))
	candidate_strings += possible_candidates
	max_len = max(map(len,candidate_strings))
	candidate_strings = purge_candidate_strings( candidate_strings, max_len )
	print candidate_strings

view raw compression_solution.py hosted with ❤ by GitHub

Now the explanation above about zlib was just a general idea of how it works. The script mostly works but it does get stuck at a few points. For instance, it successfully deduced crime_somet but another candidate string crime_some_ received the same length ciphertext and as the script continued the latter candidate moved forward while the first did not. That's the reason for me having the option to pass the first candidate as a command line argument. I had to coach the script along a bit but it did do most of the work and after about 2 pushes in the direction at the points where it started failing, it successfully produced the PROBLEM_KEY.

All that work just for "crime_sometimes_pays" :)

It was definitely an awesome challenge and I learned a lot from it. It was also a nice opportunity to brush up on my python.

Sale Problem

Problem Description:

In a shop each kind of product has a price. For example, the price of a flower is $2 and the price of a vase is $5. In order to attract more customers, the shop runs a promotion in which special offers are made. A special offer consists of one or more product items for a reduced price. Examples: Three flowers for $5 instead of $6, or two vases and one flower for $10 instead of $12.

Write a program that calculates the price a customer has to pay for a certain set of items, making optimal use of the special offers. That is, the price should be as low as possible. You are not allowed to add items, even if that would lower the price.

For the prices and offers given above, the lowest price for 3 flowers and 2 vases is $14: 2 vases and 1 flower for the reduced price of $10 and 2 flowers for the regular price of $4.

Input:

The first line of input.txt contains the number b of different kinds of products in the basket ( 0 <= b <= 5 ). Each of the next b lines contains three values c,k and p. The value c is the (unique) product code ( 1 <= c <= 999 ). The value k indicates how many items of this product are in the basket ( 1 <= k <= 5 ). The value p is the regular price of the item ( 1 < = p <= 999 ).

The next line contains the number s of special offers ( 0 <= s <= 99 ). Each of the next s lines describes one offer by giving its structure and its reduced price. The first number n on such a line is the number of different kinds of products that are part of the offer ( 1 <= n <= 5 ). The next n pairs of numbers (c,k) indicate that k items ( 1 <= k <= 5 ) with product code c ( 1 <= c <= 999 ) are involved in the offer. The last number p on the line stands for the reduced price ( 1 <= p <= 9999 ). The reduced price of an offer is less than the sum of the regular prices.


Output:

Write to the output file output.txt one line with the lowest possible price to be paid for the items in the basket.


Solution:

	//Rikaard Hosein
	//811004653
	#include <cstdlib>
	#include <cstdio>
	#include <climits>
	#include <memory.h>
	using namespace std;
	#define _DEBUG_
	#define MAX_ITEMS 5
	#define MAX_OFFERS 99+5
	unsigned int num_items; // 0 <= num_items <= 5
	unsigned int num_special_offers;
	unsigned int num_offers;
	unsigned int desired_items[MAX_ITEMS];
	unsigned int desired_quantities[MAX_ITEMS];
	struct Offer
	{
	unsigned int items[MAX_ITEMS];
	unsigned int quantity[MAX_ITEMS];
	unsigned int num_items;
	unsigned int price;
	};
	Offer offers[MAX_OFFERS];
	unsigned int memoize_array[6][6][6][6][6];
	//quantities is modified
	bool offer_appropriate( unsigned int *items, unsigned int num_items,
	unsigned int *quantities, Offer offer )
	{
	//For an offer to be considered appropriate, it must contain a subset
	//of the items in the list of desired items and the quantities must be
	//less than or equal to the quantities in the list of desired items.
	unsigned int i,j;
	for( i = 0; i < offer.num_items; ++i )
	{
	bool found = false;
	//is item found in the desired list of items
	for( j = 0; j < num_items; ++j )
	{
	if( offer.items[i] == items[j] )
	{
	found = true;
	break;
	}
	}
	if( !found ) return false;
	//Item was found, check quantity
	if( offer.quantity[i] > quantities[j] ) return false;
	else
	{
	quantities[j] -= offer.quantity[i];
	}
	}
	//If all items were found in the desired list of items
	//and their quantities were less than or equal to the quantities
	//requred, then return true.
	return true;
	}
	unsigned int minimum_price( unsigned int *items, unsigned int num_items, unsigned int *quantities )
	{
	bool finished = true;
	for( unsigned int i = 0; i < num_items; ++i )
	{
	if(quantities[i])
	{
	finished = false;
	break;
	}
	}
	if( finished ) return 0;
	//ADD MEMOIZATION
	unsigned int x;
	if( x = memoize_array[quantities[0]][quantities[1]][quantities[2]][quantities[3]][quantities[4]] )
	return x;
	unsigned int min_price = UINT_MAX;
	for( unsigned int i = 0; i < num_offers; ++i )
	{
	//need to duplicate original quantity array since it might be modified
	unsigned int temp_quantities[MAX_ITEMS];
	memset( &temp_quantities, 0, MAX_ITEMS*sizeof(unsigned int) );
	for( unsigned int j = 0; j < num_items; ++j )
	temp_quantities[j] = quantities[j];
	//Can this offer be used?
	bool appropriate = offer_appropriate( items, num_items, temp_quantities, offers[i] );
	if( !appropriate ) continue;
	unsigned int temp_price = offers[i].price + minimum_price( items,num_items,temp_quantities );
	if( temp_price < min_price ) min_price = temp_price;
	}
	memoize_array[quantities[0]][quantities[1]][quantities[2]][quantities[3]][quantities[4]] = min_price;
	return min_price;
	}
	int main()
	{
	FILE *input = fopen("input.txt","r");
	//These is the list of desired items
	fscanf(input,"%u",&num_items);
	for( unsigned int i = 0; i < num_items; ++i )
	{
	offers[i].num_items = 1;
	offers[i].quantity[0] = 1;
	unsigned int quantity;
	fscanf( input, "%u %u %u", &offers[i].items[0], &quantity, &offers[i].price );
	++num_offers;
	desired_items[i] = offers[i].items[0];
	desired_quantities[i] = quantity;
	}
	fscanf(input,"%u",&num_special_offers);
	for( unsigned int i = 0; i < num_special_offers; ++i )
	{
	unsigned int temp_num_items;
	fscanf(input,"%u",&temp_num_items);
	offers[num_offers].num_items = temp_num_items;
	for( unsigned int j = 0; j < temp_num_items; ++j )
	fscanf( input, "%u %u", &offers[num_offers].items[j], &offers[num_offers].quantity[j] );
	fscanf( input, "%u", &offers[num_offers].price );
	++num_offers;
	}
	fclose(input);
	unsigned int min_price = minimum_price( desired_items, num_items, desired_quantities );
	FILE *output = fopen("output.txt","w");
	fprintf(output,"%u",min_price);
	fclose(output);
	}

view raw sale.cpp hosted with ❤ by GitHub

libavformat_p1: A first look at libavutil's memory allocator

   libavformat is one of the libraries that make up the FFmpeg project. FFmpeg is one of the leading mutimedia frameworks out right now and is used  in lot of different projects . It's used in VLC, MPlayer, HandBrake, Blender, Google Chrome and many others. libavformat, in particular, is a muxing/demuxing library which means it's responsible for reading and separating streams of data from within a/v containers. My interest is isn't in creating some of kind a/v related application using FFmpeg or libavformat, but instead I'm just auditing libavformat's code base. Why? Because it's fun. :)


   Now within FFmpeg, there's a library called libavutil. libavutil contains a number of general utilities which are used by various libraries within the project itself, including libavformat. Memory allocation undoubtedly plays a big part in these kinds of libraries and the memory allocator used in libavformat is actually included from libavutil. So I'm tackling this part of the library first.

	void *av_malloc(size_t size)
	{
	void *ptr = NULL;
	#if CONFIG_MEMALIGN_HACK
	long diff;
	#endif
	/* let's disallow possible ambiguous cases */
	if (size > (max_alloc_size-32))
	return NULL;
	#if CONFIG_MEMALIGN_HACK
	ptr = malloc(size+ALIGN);
	if(!ptr)
	return ptr;
	diff= ((-(long)ptr - 1)&(ALIGN-1)) + 1;
	ptr = (char*)ptr + diff;
	((char*)ptr)[-1]= diff;
	#elif HAVE_POSIX_MEMALIGN
	if (size) //OS X on SDK 10.6 has a broken posix_memalign implementation
	if (posix_memalign(&ptr,ALIGN,size))
	ptr = NULL;
	#elif HAVE_MEMALIGN
	ptr = memalign(ALIGN,size);
	#else
	ptr = malloc(size);
	#endif
	if(!ptr && !size)
	ptr= av_malloc(1);
	return ptr;
	}

view raw gistfile1.c hosted with ❤ by GitHub

   So here is the the bread and butter of the memory allocator. Immediately, you can notice that there's some conditional compilation going on.

• CONFIG_MEMALIGN_HACK
• HAVE_POSIX_MEMALIGN
• HAVE_MEMALIGN

 CONFIG_MEMALIGN_HACK is only used when the OS doesn't have one of the two supported memalign functions. So in this scenario, the memory alignment is done manually. HAVE_MEMALIGN and HAVE_POSIX_MEMALIGN are similar. HAVE_POSIX_MEMALIGN takes precedence over HAVE_MEMALIGN since posix_memalign() is more compliant on systems that have certain alignment restrictions. For all intents and purposes, posix_memalign() and memalign() can just be thought of as two functions that return pointers to blocks of memory which are aligned on the boundaries specified.

Now with that aside, we can take a closer look at the code.

	/* let's disallow possible ambiguous cases */
	if (size > (max_alloc_size-32))
	return NULL;

view raw gistfile1.c hosted with ❤ by GitHub

Here we see that it's doing a check to make sure that the size is at least 32 bytes less than the maximum size of data allowed to be allocated. The first question one should ask when seeing this is, why 32 bytes? The answer is memory alignment. ALIGN is defined as either 16 or 32 depending on whether or not the processor supports AVX instructions. Here, it seems, they got lazy and instead of just checking to see whether it was 16 or 32, they just assumed the larger. So if the size requested was too large, it just returns NULL and that's the end of it. However, if the size wasn't too large, things become more interesting. Now the memory is allocated and aligned. If HAVE_MEMALIGN or HAVE_POSIX_MEMALIGN is defined then the corresponding function is called. However, when CONFIG_MEMALIGN_HACK is defined, some interesting code is run.

	#if CONFIG_MEMALIGN_HACK
	ptr = malloc(size+ALIGN);
	if(!ptr)
	return ptr;
	diff= ((-(long)ptr - 1)&(ALIGN-1)) + 1;
	ptr = (char*)ptr + diff;
	((char*)ptr)[-1]= diff;

view raw gistfile1.c hosted with ❤ by GitHub

  The first thing this section of code does is that it makes a call to malloc() and allocates size+ALIGN bytes of memory. From our previous observations it should be obvious that the extra bytes allocated is so that alignment can take place. Now if the allocation fails, ptr is set to NULL and the value of ptr is returned. 
  
  Now let's look at what happens if the allocation was successful. It sets diff to the result of an expression containing ptr and ALIGN that involves some bitwise operations. The first part of the expression is ((-(long)ptr - 1). Now the '-' operator at the front tells us that it's computing the negative equivalent of ptr. Now, thinking about that in terms of bits and integer representation, it finds the two's complement of the original value. In other words, it flips all of the bits and then adds one. This is immediately followed by the subtraction of one which effectively cancels out the addition at the end of the two's complement, making it the one's complement of the original value. i.e All the bits were flipped. 


   After all of that occurs, it performs a bitwise AND against ALIGN-1. Keeping in mind that ALIGN is a power of 2, this means that all the bits { b_0, b_1, ... , b_n } before b_x where b^x = ALIGN are being considered during the bitwise AND. Now since the bits being considered against the bitwise AND are the ones before b_x in ptr that are 0 ( since the bits were flipped ), we get the  sum needed to be added to ptr to cause the bits before b_x to add up to ALIGN-1. Now to that sum, 1 is added. We now have the sum necessary to increase the pointer to a multiple of ALIGN. The result of the expression is stored in diff, and then diff is added to ptr.  Now this alignment is guaranteed to increase ptr by at least 1 byte, so it's perfectly safe in the next line when they store the value of diff at an offset of -1 from ptr. In case you're wondering why this is done, it's so that when freeing the memory later on, and the original value returned from malloc() is needed, you can compute it by subtracting diff from the value of ptr.

Fiddling with ASN.1/DER and X.509 Certificates

   So it turns out that one of the most popular formats, if not THE most popular format, for storing X.509 certificates is base64 encoded DER; DER being an acronym for Distinguished Encoding Rules which is a concrete derivative of ASN.1 ( Abstract Syntax Notation One ). Well after a few days of reading about these two things and how they are related, I'm surprised at how little I'm actually able to understand. There is a fair amount of documentation about ASN.1 and a fair amount about X.509 certificates but there seems to be very little about how they relate. It also doesn't help that what little does exist is extremely vague...

  Luckily for me, I seemed to have stumbled upon ( literally stumbled, not the service ), two articles which seem to discuss both and how they intertwine. It is unfortunate that both articles are extremely long but maybe their density will prove to be a time saver in the long run.

• A Layman's Guide to a Subset of ASN.1, BER, and DER
• X.509 Style Guide

  Now I can truly appreciate the value of .NET. They've simplified the entire process down to a single function call. I don't like the fact that I don't understand exactly what's going on but I have deadlines so it'll have to do for now. I hope to start my own   decoder implementation soon and hopefully finish it within the month.

Recursion

What is Recursion?

   Recursion is an algorithmic method for solving problems where the problem itself consists of a number of sub-problems that are near identical, but smaller to itself. These sub-problems, however, must eventually reach a base case.( Else we just end up trying to solve an infinite number of sub-problems which will probably just end up in the process's stack space being exhausted ) Since the method involves solving similar, smaller sub-problems, it shouldn't be surprising that recursion involves a function calling itself with modified arguments.

1. Recursion involves solving a problem by solving similar but smaller sub-problems.
2. There must be a base case, so at some point, the decomposition of problems into sub-problems will stop.
3. Recursive solutions to problems involve functions calling themselves with modified arguments.

Note: This isn't the only situation in which recursion is applicable and this isn't the only way to think about recursion. In my opinion, this is just the best way to introduce the concept.

   Finding the nth number of the Fibonacci sequence is an easy way to demonstrate how recursion works. Since recursion involves solving a problem by solving similar sub-problems, then it would seem logical that the function would call itself.


 In the Fibonacci sequence, each term is the result of the sum of the previous two terms. The exception to this would be the first two terms where they are both 1.


 Let's say we wanted to find the nth number of the Fibonacci sequence. If n was 1 or 2, then we would just return the number, 1. However, if n > 2, then we would return the sum of the two previous fibonacci numbers, Fib(n-1) and Fib(n-2).


Fib(n) is the original problem. We find it's solution by solving similar, smaller sub-problems, Fib(n-1) and Fib(n-2).

	unsigned int Fib( unsigned int n )
	{
	if( n == 0 ) return 0;
	if( (n==1) || (n==2) ) return 1;
	else return Fib(n-1)+Fib(n-2);
	}

view raw Fib.c hosted with ❤ by GitHub

In this code snippet, we can clearly see all the characteristics of a recursive solution.

1. The problem of finding the nth Fibonacci number is computed using the solutions to similar sub-problems;  Fib(n-1), Fib(n-2)
2. The base case exists when n=1,2 for Fib(n)
3. The Fib function indeed does call itself with modified arguments.

Blag!