26 July 2017

Exploring the Labyrenth (2017 Edition)

2017 brings us one of the best, though newest, CTFs: Palo Alto's LabyREnth.The 2016 iteration was a grueling set of 3 dozen challenges across multiple topics that tested one's ability, skill, patience, and endurance.

2017's challenge one-upped the previous by having a fully explorable, rogue-style text world in which one could explore to find challenges. Not to the level of ROM MUD or ZZT, two of my largest time sinks when I was young, but to a fun level where one could explore, see the sights, and have a humourous romp through a landscape influenced from David Bowie's film masterpiece, Labyrinth.

There are certain sections that are locked off by challenges; progression is only possible through successful completion of challenges. I was happy to get a pretty large chunk mapped out, though:

Each successful challenge also granted additional equipment to assist in combating the final boss. In a virtual sense; you can't fight him until you beat all other challenges anyhow. But, it was fun to track the equipment being given:

With that, on to the challenges. There were six categories of challenges again this year: Binary, Docs, Threat, Programming, and Mobile. There was also the Random category where challenges were sprinkled around the world and hidden behind riddles (highlighted in orange in the map above).

My goal for the year was to complete one entire track (Binary) and to get at least one challenge in each other category. Their system made some great changes over the previous year on tracking stats for challenges completed for each user, which provided good feedback on how you were completing tasks, pointing out when it was taking you too long (such as the spike below while I was on the road for 9 days).

Mobile 2 - MIPS

Hint: RouterLocker is free encryption software for securing your router. Thank you, in advance, for purchasing RouterLocker.
Author(s): int0x80

I had some upfront warning that this challenge was coming from int 0x80 and I made sure that I got to it during competition. MIPS is completely unknown to me, let alone how to analyze, debug, or even make it work. And I had less than two days open on my schedule to get it done. This was going to be an uphill climb.

routerlocker: ELF 32-bit MSB executable, MIPS, MIPS64 version 1, dynamically linked (uses shared libs), for GNU/Linux 2.6.26, with unknown capability 0x41000000 = 0xf676e75, with unknown capability 0x10000 = 0x70401, not stripped

This challenge began with static analysis using IDA Pro, and opening every manual I could find on MIPS programming to understand what I'd be looking at.

As a first step, looking for resolved strings was slightly unfruitful. The strings shown were for output messages, but none for actual program functionality, as shown below. Where the file attempts to look for a filename, and the reference to that action shown in the strings, there were no strings to suggest a filename.

Going off the clue of it looking for a file, we look for any file reading function calls and see fopen() being used.

Wow, what a right mess. After a calling to ptrace(), we see a big chunk of data being constructed to be passed into fopen(). This is our file name, which is a stack string with irregular offsets. Converting the hex to strings, below, and putting the pieces together in a hex editor shows the filename is /tmp/router.lck. We also proved this later in dynamic analysis.

Further analysis to show the operations that would lead to a successful end show that the data from this file is read, processed in some mathematical way in sequence, and then used to verify a correct pass. This routine, with some of my basic notes, is shown below. However, from a static standpoint we can identify some weaknesses in this routine. For one, there is no block or string-based comparison. Instead, each byte is checked one-by-one with an exit clause if any single byte fails. So all we need to do is figure out each byte in order, not a full set of bytes.

Immediately before this algorithm is another set of data being constructed into an array in variable order, which is likely our "pad" for decrypting the data in the file:

One could do this entire challenge statically using this data and working backwards through the routine. But, I'd like to learn how to do this dynamically to learn how these files are run. And that would require a MIPS environment to run in. This was not easily done, but after hours of scouring websites and write-ups, I was able to find effective methods to create the environment and execute the challenge.

The initial step was to install QEMU and find a MIPS image. A proper Debian compiled version was located on Debian servers. Using the Wheezy hard drive image (qcow) and vmlinux-3.2.0-4-5kc-malta, I followed the steps by Aurélien Jarno to make a functional VM. Once booted, I lacked copy/paste abilities, so I just uploaded the routerlocker challenge to my website and downloaded into the VM. Running it gave the expected output of failure: "License file not found." and "Lock it up, and lock it out."

First step was to install and run strace to track execution. strace by itself gave no usable output, not even the file being read, but running it in File Open and File Access mode showed what I needed:

For much of the remainder, I'll apologize in advance. I had never used gdb before and so I spent a few hours that Sunday night learning how, and tripping over myself in mistakes. I was also working in a VM with an _incredibly_ slow screen write rate (half a second per line of text) and no copy-paste. I'll try to transcribe and show steps here, but most items will be shown as screenshots.

After learning the entry point below, I set additional breakpoints of where I should be based upon static analysis:

(gdb) info files

Symbols from "/root/routerlocker"

Local exec file:

        '/root/routerlocker', file type elf32-tradbigmips.
        Entry point: 0x400780
    0x00400154 - 0x00400161 is .interp
.... Removed for brevity ...
    0x00411130 - 0x00411150 is .bss

(gdb) break *0x400780
Breakpoint 1 at 0x400780
(gdb) break *0x400b1c     (start of parsing data)
Breakpoint 2 at 0x400b1c
(gdb) break *0x400d18     (read data strlen)
Breakpoint 3 at 0x400d18
(gdb) r      (run program)
Starting program: /root/routerlocker

Breakpoint 1, 0x00400780 in _ftext ()
(gdb) c      (continue execution)
License file not found.
Lock it up, and lock it out.
[Inferior 1 (process 2578) exited normally]

WTF? It hit my first bp and didn't even touch the latter two. As it turns out, there's a reason for that. Immediately after starting, the challenge runs fork() to split itself between two processes. More research showed that gdb was following the master set of execution and not the spawned child process. This is easily solved by setting "set follow-fork-mode child" and re-running the program. Doing so yielded my second breakpoint!

Breakpoint 1, 0x00400780 in _ftext ()
(gdb) c
[New process 2610]
[Switching to process 2610]

Breakpoint 2, 0x00400b1c in main ()

OK, now we're set to start attacking the routine. We'll need to seed the router.lck file with data that we can trace to see how it's manipulated. The first step is to determine how big our data should be. This is actually shown up front as the program reads in 29 bytes from the file:

I seeded my data with PAN{1234567890abcdefghijklmnop}, then made sure I could find that in memory once run. Using 'i r' to display registers, I found the data being read into a pointer from v0. Using 'x' to display the first DWORD I was 0x40314e7b ("PAN{"), then used 'x/16' to display 16 sets of DWORDs to view the rest:

Awesome, data is in place, now let's get back to our math. It's a somewhat straight forward routine, just hindered by the language and difficulty in getting dynamic analysis to work. It also has a great weakness that can be exploited. For each byte, it will take the respective byte of the pad, perform this routine which ends in an XOR, and then compares it to a check-value. That check-value never changes, so we can exploit XOR.

As many know, XOR works in deltas. A ^ B == C. A ^ C == B. C ^ B == A. If you know any two values you can determine the third. And so you can use this to your advantage. In here we know the respective "pad" value, and the check byte. Regardless of what math occurs up until the end, we can solve for the correct byte at the very last operation by XOR'ing the pad byte against the check byte.

And so, by tracing along the code, I found that at the end it XOR's the router.lck byte against the respective pad byte and compares it to the respective check byte. So, for each byte, just XOR the pad byte by the check byte and you'll get the original data. Then, set the check byte correctly so that it'll wrap around to the next byte. So, set a breakpoint at that part, step to the comparison operation, and display the registers of v0 and v1.

Particularly, break at 0x400c5c, step (stepi), display v1 (i r v1), to get the pad byte.  Set a breakpoint at 0x400c78 and step forward to display the data byte (a0), pad byte (v0), and check byte (v1). XOR v0 by v1 in a calculator to get the original data byte. Then set v0 to v1 so that it'll pass the check and continue (c) forward

Once all was determined, and I was able to step through and determine the first few bytes of the data, I decided to just go and do them all. It was only 29 of them.  When all was done, I had my key. Actually, I was able to stop early and guess the end part, with the whole thing being:


This was a fun challenge that I learned a lot from.

Binary 4 - Mac Ransomware

This challenge was fairly straight forward, but did have a few notable and funny components to discuss. Once downloaded, the challenge contained a 64-bit Mach-O executable and a binary file named PANW_Top_Secret_Sauce.jpg.encrypted.

The challenge is fairly straight forward. The binary will acquire the MAC address of the system and use it as a key to RC4 encrypt a file named PANW_Top_Secret_Sauce.jpg. A unique computer identifier is generated to send to the "ransomware" developers.

I executed this challenge using Hopper, a tool I don't recommend, but was chosen out of laziness. This challenge could also be performed using the IDA Pro debugger with the Mac remote debugger, which is a preferable method.

One unusual issue is that the sample attempts to detect if it is running within a VM by running a standard ioreg command:

ioreg -l | grep -e Manufacturer -e 'Vendor Name' | grep -e 'Parallels' -e VMware -e Fusion -e 'Virtual Box'

This command will display all I/O devices with the words 'Parallels', 'VMware', 'Fusion', or 'Virtual Box' in the vendor name field. However, there appears to be a bug in the way the challenge was developed. If executed from under a typical user in a VM, it _should_ catch this and fail. However, if executed under another application, like Hopper, there is no PATH set to find ioreg. The execution will 'fail open' and the program will proceed regardless of being in a VM or not.

For this check to work completely, it must be set absolutely as /usr/sbin/ioreg. Once that's done, it executes correctly and returns back the value to say it's running in a VM:

After this basic check, the MAC address of the system is used to perform the encryption using RC4. This is done through a standard, easily recognizable RC4 algorithm implemented statically. This same MAC address is then used to generate a unique identifier through an algorithm below:

This routine takes the values of a static lookup table, below, and generates a 5-byte output based upon the first five bytes of the MAC address.

Now, how do we attack this? We can't go backwards from the resulting file, so we'll have to brute force various MAC addresses until we find the correct one.

Brute forcing based upon a 6-byte value would take an extremely long time. With only the first five in play, I assumed this would be an obvious tell to help lower the key space due to this length. So, I launched a brute force script and, after 12 hours, barely made a dent into the keyspace. Ouch. This wasn't going to work.

I stopped for awhile and went onto other challenges, but came back after poking around the World Map and finally realized the hint:

Hint: Send me this identifier together with your $$$$ to decrypt your file: da91e949f4c2e814f811fbadb3c195b8

Whoa. That's the identifier. I don't need to brute force the JPG, I just need to brute force the ID routine to find a value that matches that hash. I turn my brute forcer to that, came back 12 hours later, and realized I still wasn't getting enough performance to finish this quickly.

I thought of ways to shorten this and realized I could just download a master database of all MAC address Organizationally Unique Identifier (OUI). It's still a hefty list of 10s of thousands, so I removed the virtual machine ones to lessen the keyspace, since we know the sample won't run in those environments:

import codecs
import hashlib

lookup = '\x13\x9A\x1B\xE4\xF3\x8E\xC7\x8C\x3F\x7A\xDC\x0B\x42\xA7\xF8\x6E\x9F\x08\x79\x17\xD6\xB1\x33\x7D\x67\x01\x1C\x1C\x1C\x02\x30\x0A\x34\x34\x22\x1B\x34\x03\x0C\x02\x14\x02\x01\xC0\x01\x01\x21\x02\x01\xC8\x22\x01'

def run_data(mac):
    result = [0,0,0,0,0]
    done = ''
    for i in range(5):
        for j in range(5):
            pos = (20 * j + 4 * i) / 4
            x = lookup[pos]
            mult = ord(x) * ord(mac[j])
            result[i] += mult

        result[i] = result[i] % 0xFB
        done += chr(result[i]) + '\x00\x00\x00'

    test = hashlib.md5(done).hexdigest()
    return test

def main():
    for oui_addr in open('oui.txt', 'r').readlines():
        if not '(hex)' in oui_addr:
        oui_addr = oui_addr.split()[0]
        oui_addr = oui_addr.strip().replace('-','')
        oui_addr = codecs.decode(oui_addr, 'hex_codec')
        print('[*] OUI: {}0000'.format(codecs.encode(oui_addr, 'hex_codec'))),
        for a in range(256):
            for b in range(256):
                test = oui_addr + chr(a) + chr(b)
                result = run_data(test)
                if result == 'da91e949f4c2e814f811fbadb3c195b8':
                    print(test, codecs.encode(test, 'hex_codec'))
        print('-- {}'.format(codecs.encode(test, 'hex_codec')))

if __name__ == '__main__':

However, after hours of running, I still got nothing. In fact, it ran through everything with no positive results. Frustrated, I went back to my large-scale brute force which was estimated to take days. I wrote off hate mail to the organizers and went back to other challenges.

It bugged me, though. So, I started throwing everything at it. I then found the answer accidentally. I ran the brute force checker against the master database of OUIs instead of my filtered list, and the answer eventually popped up:

That snap was a vessel in my forehead. I thought I was missing something obvious, but there it is. The correct MAC address was one from a Parallels environment, even though it appeared the program was ruling out Parallels as a viable environment. I think? Now I'm doubting myself. Whatever, that was the correct MAC segment (00-1c-42-92-df-??). I used that to decrypt the PNG and received my answer:

Oh, but our story didn't end there. Mac OS X is my preferred environment, especially for this type of work. And my MacBook is actually a company-owned asset, as is normal for all of us. However, it's also a company-managed asset and my company is Carbon Black, who makes endpoint protection products. When I saw the VM checking, and had verified the code wasn't malicious, I ran it on my host instead of in a VM. So, it shouldn't have been a surprise when, during analysis, our Security Operations team knock on my virtual door to see what I was doing.

Threat hunting had found a binary running on my system, encrypting files. Well, technically just one file, but it looked suspicious.

OK. No problem, can explain that away. But the binary has a 17/56 score on VirusTotal...

Yeah, that's a bit harder. To its credit, most AV engines have it marked up as "RansomLabyrenth", so it's kind of evident where it came from. If you know what LabyREnth is... But kudos to the blue team for detecting me. If I had only known that the challenge would've run properly in the VM with Hopper.

Random #3 Dogs

The random track was some of my favorite in this year's LabyREnth. They also took the 'random' to heart with challenges that were all from left field. Many times it was the same style of data decoding but in an unusual format, but the one that I loved was the Dogs challenge (Random #3). If you're reading this for an insightful post on how to solve it, I'll just go ahead and disappoint you. You're not going to get it.

Dogs was found by discovering and following a blind hallway in the World Map. At the end you find yourself alongside a cute little puppy. By 'pet'ting the dog you get the challenge:

The puppy purrs because he thinks he's a cat. You realize he's communicating with you telepathically, and sending you information about a challenge!
Hint: DoGz-CeNtRaL presents a fine new release:[DoGz-CeNtRaL] DOGS.THE.MOVIE.2017.DVDRIP.iso. The menus can be a little tricky.
Author: @gabe_k

Sure enough, you're presented with a DVD ISO with a menu system showing dogs. Lots of dogs. Dogstravaganza. If you click the wrong dog, you see a dog falling in the water. If you select the right dog, he balances an egg on his nose.

Looking into the structure of the DVD you'll see the standard DVD files as well as a Flag.mp4. Playing Flag.mp4 showed nothing but a few seconds of black, so I used VLC to separate each frame into a PNG. The result was 121 PNGs of frames, but only of two unique types. Frames 1-13 were all hash duplicates of each other, and 14-121 were all hash duplicates of each other. At only ~1-2Kb each, there was nothing that seemed of consequence, so I ignored it.

Analysis of the VIDEO_TS.BUP shows it was developed with DVDAuthor 0.7.1. So, after an hour of unsucessfully trying to install it in Mac, I spun up an old Linux VM and used the newly installed dvdauthor application to unpack the DVD.

The results were a single XML script file and a series of 29 MPEG VOBs (vob_00m_001 - 029.vob). vob_01t_001.vob is the video of the dog falling in water and vob_01t_002.vob is the video of the dog balancing an egg.  The next step seems straight forward, just get the correct letter from each video frame. Not easily done. After extracting out each frame, you can vaguely see an impression of each letter as well as some unknown blocks that seem to correlate to the menu buttons:

See it?  How's this... (MSPaint is deprecated not removed)

But, the order of frames doesn't add up. "P" isn't first, and the frames just seem alphabetical order. The 29 frames account for the 26 A-Z letters plus "_{}". Pulling the results from dvdauthor.xml shows the DVD menu's scripting system, something completely new to me.  A segment below (portions removed for brevity):

    <menus lang="en">
      <audio lang="en" format="ac3"/>
      <subpicture lang="en"/>
      <!-- Menu 1/29 -->
        <audio id="0"/>
        <subpicture id="0"/>
          g13 = g1;
          g13 = g13 and 4095;
          if (g13 != 101) {
            goto l7;
          if (g0 le 0) {
            goto l7;
          button = g0;
          goto l8;
          button = 1k; <!-- button no 1 --> 
          g1 = 101;
        <vob file="vob_00m_001.vob">
          <buttons start="0:00:00.000">
            <button name="1">
                g15 = 1;
                jump pgc tail;
            <button name="2">
                g15 = 2;
                jump pgc tail;
            <button name="3">
                g15 = 3;
                jump pgc tail;
            <button name="4">
                g15 = 4;
                jump pgc tail;
            <button name="5">
                g15 = 5;
                jump pgc tail;
            <button name="6">
                g15 = 6;
                jump pgc tail;
          <cell start="0:00:00.000" program="1" pause="inf"/>
          g14 = g15;
          g15 = 0;
          if (g14 == 1) {
            goto l29;
          if (g14 == 2) {
            goto l31;
          if (g14 == 3) {
            goto l33;
          if (g14 == 4) {
            goto l35;
          if (g14 == 5) {
            goto l37;
          if (g14 == 6) {
            goto l39;
          if (g6 != 6) {
            goto l12;
          if (g14 == 7) {
            g6 = 7;
          if (g14 == 7) {
            goto l41;
          if (g14 == 7) {
            goto l39;
          if (g14 == 8) {
            goto l43;
          if (g14 == 9) {
            goto l45;
          if (g14 == 10) {
            goto l47;
          if (g14 == 11) {
            goto l49;
          if (g14 == 12) {
            goto l51;
          if (g6 != 1) {
            goto l21;
          if (g14 == 13) {
            g6 = 2;
          if (g14 == 13) {
            goto l53;
          if (g14 == 13) {
            goto l30;
          if (g14 == 14) {
            goto l55;
          if (g14 == 15) {
            goto l57;
          if (g14 == 16) {
            goto l59;
          if (g14 == 17) {
            goto l61;
          if (g14 == 18) {
            goto l63;
          if (g14 == 19) {
            goto l65;
          g0 = button;
          jump title 1;
          g0 = button;
          jump title 1;
          g0 = button;
          jump title 10;
          g0 = button;
          jump title 1;
          g0 = button;
          jump title 15;

Wow! OK, so there are 19 buttons. Each button can use jumps to change to new titles, but can also do post-scripting to move values while also checking its current state.

This one was actually easily solved. Because, I'm going to disappoint. I started poking at this while in Montreal for REcon. I then finished while being stranded in the Montreal airport for a day and a half due to massive storms in the US Northeast. So, I sat at a US-Southern-BBQ place in a Canadian airport, eating BBQ Rib Poutine and cheap beer, and just clicked them all. I broke the menu into quadrants to map out the buttons on paper. I then just clicked them all. Once I found one that worked, I took a VM snapshot. If I failed, I just reverted back.

It took roughly 1-2 minutes per letter and within an hour of drinking I had the answer:


But I definitely want to read some write-ups on this one. The DVD language looks really cool, and I have an idea behind how to do it.

That's it. Some of the more interesting challenges that I liked. And I'm looking forward to 2018's LabyREnth!


  1. nice writeup. If its possible could you share\upload the Mobile 2 - MIPS binary ?

    1. Absolutely. I'm not sure if they're going to publish the files publicly. Until then, I hosted the MIPS file here:


    2. Archive of challenges - http://archive.labyrenth.com/2017/challenges.html