FLARE-ON 2018 — Challenge 6 Solution

This year, as always, I participated in the FireEye FLARE-ON challenge, which is a capture the flag (CTF) competition for reverse engineers/malware analysts. If you aren’t familiar with the competition you can get more info here: http://www.flare-on.com/

The official write-ups for this years challenge have also been published here: https://www.fireeye.com/blog/threat-research/2018/10/2018-flare-on-challenge-solutions.html

As with past years there are some challenges that are real tough nuts to crack and for me this year, challenge 6 was the one I expended most time on and ultimately finished with (having been AWOL for 3/6 weeks of the challenge. Note to self — book out calendar for FLARE-ON 2019!).

I’ll take you on a rambling journey of my thought process and approach at various stages in reaching the final solution (SPOILER — I did it all in a single Python script using Unicorn engine and pexpect. You can judge my horrible hacky code here)

Init

For challenge 6 we were provided with a single file called “magic”. Running the file command show us we were dealing with a 64-bit ELF binary. Cool.

$ file magic
magic: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=0d9c0c6c6a7f6b7189ce4758d112c25e48effe87, stripped

If we execute the file (I used Xubuntu 17.10) we are prompted for key 1 of 666 and entering a test key gives the error message shown and exits the program.

$ ./magic
Welcome to the ever changing magic mushroom!
666 trials lie ahead of you!
Challenge 1/666. Enter key: icanhazflag?
No soup for you!

At this point, I ran strings over the binary, just on the off chance there was a nice easy win, or an obvious jump into a useful code section. The output below shows some promising entries, which we can follow up.

No soup for you!
Failed to read file
Could not write file!
Run, Forrest, run!!
Generated first permutation!
Welcome to the ever changing magic mushroom!
%d trials lie ahead of you!
Challenge %d/%d. Enter key:
Congrats! Here is your price:

At this point we are ready to take a deeper look at the code itself, my first weapon of choice is IDA Pro, mainly because I use it for $dayJob and secondly because for standard binary formats like PE and ELF, it is still one of the best tools for the job.

Initial code review doesn’t show any form of code trickery or obfuscation, the program flow looks quite natural and by pivoting off of the strings we found previously, we are led to a code block as shown in the figure below, where the program reads the user input via fgets and disappears off into a function I affectionately labelled “doTheMagic”.

IDA Pro disassembly of main function

Delving into the “doTheMagic” function we can observe a few things. Firstly, there are lots of bit-wise operations happening on hard-coded file offsets. Secondly, there is a loop that will run 33 times that results in a call ecx instruction. Thirdly, if any of these calls return zero, the code branches off to an _exit call.

IDA Pro disassembly showing magic function loop and branch to exit
IDA Pro Disassembly showing hard coded offset operation and dynamic function call

At this point, I used the remote Linux debugger from my IDA Pro VM (W7x64) and set a breakpoint at the start of the “doTheMagic” function. Stepping through, I observed that the hard-coded values were actually offsets into a data structure. This structure contains a few things:

  • XOR encrypted magic shellcode offset
  • Encrypted magic shellcode size
  • XOR decryption key for decrypting magic shellcode
  • Magic function “win”/comparison values
  • Magic function character count [1–3]
  • Offset into user input to take characters from

At this point we can infer that the function will run 33 dynamically generated shellcode blobs, each taking 1–3 characters from our user inputted key, running them against some as-yet-unknown algorithm and comparing the output with some hard-coded reference values.

My first thrust at solving this was to slowly debug and try to re-implement some of the shellcode functions in Python (unsigned ints are fun in Python!). Once I got 3–4 functions in, I realised this was not going to be a practical approach, bearing in mind there are 33 magic functions and 666 executions of said functions to potentially unravel.

My second thrust was to try and use angr and leverage symbolic execution to do the hard work for me. I won’t cover it here, I taught myself some angr and got some working code, and given enough time, angr probably could solve this, but I would have been old, grey and long forgotten why my PC fan had been spinning for 30 years :). There are some cool CTF tutorials for those wanting to learn angr and if anyone solved it this way, I’d love to see the code!

Having established via some peers (thanks @daubsi) that a lot of people were just emulating the magic functions and bruteforcing the solution (the keyspace for a 3 character string is small enough to make this a practical attack), I rolled up my sleeves and got to grips with the fantastic Unicorn engine. Unicorn basically allows us to take arbitrary shellcode, setup the execution environment and emulate away to our hearts content. One of the most helpful resources I found was actually the FLARE-ON 2017 Challenge 3 write-up, which showed how to use Unicorn practically against a similar sort of problem.

So, at this point, there are a few things we need to solve to start putting some skeleton PoC code together to vanquish our foe:

  • Extraction/parsing of the 33 magic structures
  • XOR decryption of the 33 magic shellcode blobs
  • Unicorn environment setup/initialisation
  • A way to quickly brute-force possible key values.
  • A way to repeat the above 666 times!

Step 1: Extracting the 33 magic structures

Due to the offsets being hard-coded, this is a case of rolling through and pulling out the requisite values from the magic binary. To reach the next offset out of the 33 pieces, a small bit-wise operation is performed after each iteration. Note — Python doesn’t play too well with endianess, hence the horrible hex munging going on here!

def readMagic():
f = open("magic","r")
data = f.read()
f.close()
start = 0x5100
params = []
for i in range(33):
j = ((i << 3) + i) << 5 # This finds us the next offset
jStart = start + j
mFunc = binascii.hexlify(data[jStart:jStart+8][::-1])
mFuncSize = binascii.hexlify(data[jStart+8:jStart+12][::-1])
mKeyOffset = binascii.hexlify(data[jStart+12:jStart+16][::-1])
mLoopCount = binascii.hexlify(data[jStart+16:jStart+20][::-1])
mOutOffset = binascii.hexlify(data[jStart+20:jStart+24][::-1])
mFuncXOR = binascii.hexlify(data[jStart+24:jStart+32][::-1])
mRefVars = binascii.hexlify(data[jStart+32:jStart+64])
params.append([mFunc,mFuncSize,mKeyOffset,mLoopCount,mOutOffset,mFuncXOR,mRefVars])

Step 2: Decrypting the shellcode blobs

Now we have the offsets, sizes and XOR keys for our 33 shellcode blobs, we can iterate through them and store them in a list for use with Unicorn later on.

shellcodes = []
for i in range(33):
a = array("B",data[int(params[i][0],16)-0x400000:(int(params[i][0],16)-0x400000) + int(params[i][1],16)])
b = array("B",data[int(params[i][5],16)-0x600000:(int(params[i][5],16)-0x600000) + int(params[i][1],16)])
c = None
c = bytearray()
for j in range(int(params[i][1],16)):
c.append(a[j] ^ b[j])
shellcodes.append(c)

Step 3: Setting up Unicorn

This part was tricky and required a reasonable amount of self-learning, testing, tweaking and swearing to get working. First off we need to allocate some memory for things like our stack, our user input, our magic “success” reference values etc.

ADDRESS = 0x400000
STACK = 0x410000
UKEYMEM = 0x420000
ENCKEYMEM = 0x430000
STACK_SIZE = 1024 * 1024
mu = Uc(UC_ARCH_X86, UC_MODE_64) # This creates the actual UC engine
mu.mem_map(ADDRESS, 5 * 1024 * 1024) # This gives us 5MB of memory
# Now we need to poke in our values as they would be in the real program - see full script for complete example
mu.mem_write(ADDRESS,  binascii.unhexlify(binascii.hexlify(shellcodes[iNum])))

OK, we have an emulator and things allocated into memory, we also need to make sure that our CPU registers are also filled with the expected data, luckily for each of the 33 iterations, the same registers are used for the same functions. In Unicorn, registers are set like so:

mu.reg_write(UC_X86_REG_ESI, int(params[iNum][3]))
mu.reg_write(UC_X86_REG_RAX, UKEYMEM)
mu.reg_write(UC_X86_REG_RDI, UKEYMEM + kOff)
mu.reg_write(UC_X86_REG_RDX, ENCKEYMEM)
mu.reg_write(UC_X86_REG_RSP, STACK + STACK_SIZE - 1)

Now, if we call mu.emu_start(ADRESS + len(shellcode)), our magic shellcode blob will run to completion and helpfully leave all of its registers and memory query-able. Based on reviewing the shellcode, we can see that if the correct characters are passed, the return value of the EAX register will be non-zero. We can read the register like this:

mu.reg_read(UC_X86_REG_RAX)

Cool — we can reliably run those shellcode blobs, now we need to automate/brute-force the user inputs.

Step 4: Doing the bruting

Now at the start of my conquest to solve this challenge, I had no idea what the key looked like, only its probable length (based on adding up the characters counts from parsing the magic data structures). My initial solution was to assume anything that was ASCII printable was viable, which Python helpfully provides us via the string library and string.printable object. We know we need incantations of 1,2 and 3 character strings, so can use something like this to get 3 lists containing all possible permutations:

import itertools
perms = [list(itertools.permutations(string.printable,1)),list(itertools.permutations(string.printable,2)),list(itertools.permutations(string.printable,3))]

We can combine this with our Unicorn shellcode emulator, which I turned into a discrete function that sets up the registers and pokes the user inputs into the right offsets etc (see gist for more). So what we now have is a brute-force function that will work through each of the 33 magic shellcode blobs and find the value that results in a positive EAX return value and logs the characters into the right position in the key.

Tentatively, I set it running on the first attempt and a key popped out. I entered it into our magic binary and low and behold, it works!

$ ./magic
Welcome to the ever changing magic mushroom!
666 trials lie ahead of you!
Challenge 1/666. Enter key: inds isng llg w. e HthitheoftheAh,urnolik inefe yo blrhot in owace
Challenge 2/666. Enter key:

Great, so we can bruteforce the shellcode and get the key, but after each successful key is entered, the binary self-modifies and all of the magic parameters and shellcodes are now different. We also need to figure out how to keep entering the key each time without exiting the program or things will get messy very quickly.

Step 5: Automate all the things

Enter pexpect — a handy little Python library for spawning and controlling child processes programmatically. We can now read the magic binary, extract the magic variables, brute force the key, enter it into the binary, rinse and repeat. The snippet below shows what this looks like.

def doMain():
masterKeys = []
child = pexpect.spawn("./magic")
child.expect("Challenge.+")
print(child.before)
print(child.after)
  for i in range(0,666):
magicParams,magicCodes = readMagic()
thisKey = doDaBrute(magicParams,magicCodes)
masterKeys.append(thisKey)
print("Key " + str(i) + ":" + thisKey)
child.sendline(thisKey)
child.expect("Challenge.+")
print(child.before)
print(child.after)

Step 6: Shit, this is taking it’s sweet ass time

So I now have my all-singing, all-dancing win script. The only problem is, those 3 character-requiring magic shellcodes are making each function take 10+ minutes to get a single key and we need 666 of them. After leaving it running over night and finding a HUGE bug in my code (not provisioning for more than one of the same character in any given permutation, DOH!) which lead to it bombing out after a few hundred keys, I reviewed the data I had to see if I could make any optimisations.

Reviewing the keys that had been successfully found, I noticed that they were all comprised of only a small subset of letters and punctuation. This allowed for shrinking the keyspace considerably to:

keyspace = "inds glw.eHthofA,urkybac"

Pretty nippy, but then I also noticed that not only did the key only include those characters, the 1,2 & 3 character permutations were repeated too.

perms = []
perms.append(['f', ' ','.','e','r', 'g'])
perms.append(['ow','ll','no',' H', 'ng ', 'e ','in','of', ' w','is', 'ur'])
perms.append(['lik', 'thi', 'ds ', 'Ah,','hot','ng ','ace','the',' in', ' bl',' yo'])

Excited, I ran the script with this new found trick up its sleeve and it solved the challenge in under 2 minutes flat, giving me the prized flag:

mag!iC_mUshr00ms_maY_h4ve_g!ven_uS_Santa_ClaUs@flare-on.com
#winning

A fun fact that I only spotted afterwards, is that the keys are all anagrams of a Monkey Island Pirate Le-Chuck quote:

“Ah, there’s nothing like the hot winds of Hell blowing in your face.”

Playing with some of the shellcode blobs, there were also a bunch of references to the Monty Python movies (“Tis’ but a scratch!”). Nothing like a challenge author with good taste!

Conclusion

This was a tough little cookie to crack, but it forced me to go and experiment with a swathe of tools I have never properly gotten to grips with before and still need to devote more time to, primarily Angr, Frida and Unicorn. These tools are fantastic and will 100% come in handy in my daily malware analysis travels.

It also leveled up my Python PoC skills, I leaned heavily on iPython, which is another excellent utility. In the early phases I also played around with other more sensible languages that handle binary data much better, like C#. Being able to quicly transpose concepts between languages, even ones you have never used before, is a real handy skill to try and acquire, you just need to put yourself out of your comfort zone once in a while.

Reading the other write-ups, there were WAY more elegant ways to have solved this and brute-forcing is always just that, a blunt instrument, but in this instance, it got the job done.

Above all I had fun, I learnt many new things, I wrote some code I can re-purpose for real world applications and I persevered until I cracked it. Hopefully some or all of this is useful to someone, I know how useful I find reading everyone elses writeups!

Full code at: https://gist.github.com/MrAdz350/78421f040631002660c4194f630abf7a

A.

“Swordfighting is a little like making love. It’s not always what you do, but what you say.”