09
Jan
2012

GitS teaser 2012 – AL’s revenge

AL’s revenge was basically a crypto/math challenge with some file format puzzling at the start. The given file is an XZ archive which contains a program in LLVM bytecode. Since the unix ‘file’ utility knows about both these fileformats this wasn’t really hard to figure out. After that, the trick is to compile the LLVM bytecode to an ELF binary using the ‘llvmc’ tool, after which you can use your favorite disassembler/decompiler to reverse engineer the binary.

After having reversed the program and converting the important code to python it gets interesting!


# first 8 bytes of the guid
name = 0x6161313836613065 

def checksum(name, serial):
	if name & 0x8000000000000000:
		name ^= 0xA348FCCD93AEA5A7
	if serial & 0x8000000000000000:
		serial ^= 0xA348FCCD93AEA5A7
	check = 0
	while (serial):
		if serial & 1:
			check ^= name
		serial >>= 1
		name <<= 1
		if name & 0x8000000000000000:
			name ^= 0xA348FCCD93AEA5A7
	return check

We need to find a value for serial so that checksum(name, serial) == 1.

One way to look at this is that in the loop we have 64 different values of ‘name’, and the final checksum is a linear combination of these using the xor operation as addition, and the bits from the serial as coefficients.

So first we put these 64 values in a matrix:

n = [checksum(name, 1 << i) for i in range(64)]

Each row is one of the 64 values of name in the checksum loop. Now we have to find which ones to xor together to get the value 1. “Adding values together until you get 1” is pretty much what happens when you run Gaussian Elimination on this matrix, so that seems to be an easy way to solve it.

The problem with the Gaussian Elimination is that it does not keep track of which rows from the input matrix were summed to form each output row. Since this is the information we want we need to keep track of this during the algorithm.

We basically added 64 more columns to the matrix which represent the coefficients of the input rows which produce this output row. This makes the final algorithm quite simple:


# first 8 bytes of the guid
name = 0x6161313836613065 

# return value is 1 for correct serial
def checksum(name, serial):
	if name & 0x8000000000000000:
		name ^= 0xA348FCCD93AEA5A7
	if serial & 0x8000000000000000:
		serial ^= 0xA348FCCD93AEA5A7
	check = 0
	while (serial):
		if serial & 1:
			check ^= name
		serial >>= 1
		name <<= 1
		if name & 0x8000000000000000:
			name ^= 0xA348FCCD93AEA5A7
	return check

n = [((checksum(name, 1 << i) << 64) | (1 << i)) for i in range(64)]

# perform gaussian elimination, while keeping a record for each row which bits of the
# serial must be set to 1 to achieve the value in that row. 
for i in range(64):
	n.sort(reverse=True)
	for j in range(i+1, 64):
		if n[j].bit_length() < n[i].bit_length():
			break
		n[j] ^= n[i]

for i in n:
	if i >> 64 == 1:
		print "solution:", hex(i - (1 << 64))
		print "checksum result (should be 1):", checksum(name, i - (1 << 64))

And indeed this prints the correct answer!

Comments are closed.