Exodus Adventure CTF 2015

This is a walkthrough of the 2015 Exodus Adventure CTF.
The CTF takes the form of a text adventure game. Players are provided with an x86 Linux ELF binary of the game and a web page that runs the same binary inside a javascript x86 emulator called JS Linux.
Let’s get started.

,.        ___________                .___
\%`.      \_   _____/__  _______   __| _/_ __  ______
 `.%`.     |    __)_\  \/  /  _ \ / __ |  |  \/  ___/
   `.%`.   |        \>    <  <_> ) /_/ |  |  /\___ \
     `.%`./_______  /__/\_ \____/\____ |____//____  >
       `.%`.    __\/      \/          \/          \/
         `.%`.  \ \__       .___                    __                     ._.
           `.%`./ /_ \    __| _/__  __ ____   _____/  |_ __ _________  ____| |
             `./ //_\ \  / __ |\  \/ // __ \ /    \   __\  |  \_  __ \/ __ \ |
            __/ /:/;.  \/ /_/ | \   /\  ___/|   |  \  | |  |  /|  | \|  ___/\|
            \__/  `:/;./\____ |  \_/  \___  >___|  /__| |____/ |__|   \___  >_
                    `:/;.    \/           \/     \/                       \/\/
                      `:/;.,
                        `:/ ;
                          `'

You are in a dark cave. It smells like something hairy lives here.
You can see light to the north.

Exit is north.
> n
You can see shadows on the cave walls.

There is a bear here.
Exits are north and south.
> look bear
You see a cave bear, probably the last one alive.
> kill bear
With what? Your bare hands?
y/n? y
Congratulations! You killed the bear with your bare hands.
You find a flag on the corpse.
> inventory
You are carrying:
a flag
> look flag
You see a white silk flag with screen-printed lettering which reads:
71948222c27c8927a11d67f16167c47b.

This is the easy flag worth only 12 points. The description of the flag is stored in the adventure binary XORed with “xyzzy” (repeating) so that it doesn’t show up in plain text.
We continue north.

> n
You find yourself under a huge dome of rock with light coming in through an
opening too high up to reach.

There is a sign here.
Exits are north, south, east and west.
> look sign
To the east you see a sign which reads:
Klein's Maze
The only exit is the only entrance, but beware the path you take.
> e
You are in a little maze of twisting passages, all different.

Exits are north, south, east and west.
>

This flag is worth 150 points. You must carry the flag you got from the bear through the maze taking the path e-n-e-w-s-n-e-w-s-n-e-w-s-n-e-w-s-n-e-w-s-n-e-w-s-n-e-w-s-n-e-w-s. There are no walls in the maze; from each room you can go any direction. There are 5 rooms that form various loops inspired by the shape of a Klein bottle.


Each move after entering the maze is fed into a CRC32 checksum. Once the checksum is equal to 0xDBC67E22, this happens:

A wild Amatus appears!
Amatus looks pleased and you become aware of a tingling in your pocket.
Before you can react he vanishes in a puff of entropy.
> look flag
You see an orange flannel flag with machine-embroidered lettering which reads:
d2ae9f4db70cd6949fe824bb3793a651.

If you do not have the flag from the bear:

He looks at you circumspectly, shakes his head, and turns to dust.

The value of the flag is generated from the checksum. Since this value is known to be 0xDBC67E22 at this point, it’s easy to work out the value of the flag without “solving” the maze. Or, using a debugger, you could just break right before the comparison and set the value of the checksum to the expected value and continue execution to generate the flag.
Going west a few times exits the maze and we continue our adventure.

You find yourself under a huge dome of rock with light coming in through an
opening too high up to reach.

There is a sign here.
Exits are north, south, east and west.

> n
You are in a server room. There are four rows of cages packed with Dell, HP,
and Sun hardware.

There is a PE2650 here.
There is a VP here.
Exits are north and south.
> look PE2650
You notice a PowerEdge 2650 with a message scrolling on its LCD:
All Hail Eris.
> hack PE2650
You pull out your evil-maid USB stick but notice all the USB ports are covered
with epoxy.

This flag is worth 150 points. The “hack” function calculates the Collatz chain length for 42, verifies that it is indeed 8, then denies you access. The solution is to bypass this check and execute the “dead” code which generates the flag.
Next we continue deeper into the server room.

> n
At the back of the server room you see a cat-5 cable running down through the
opening of a displaced floor tile.

Exits are south and down.
> d
A staircase spirals down under the server room. You smell something sweet and
suspect it's a halon leak, perhaps you shouldn't spend a lot of time down here.

Exits are up and down.
> d
In the basement is a row of car batteries connected to what you can only assume
is a UPS. Next to the UPS is a rack with an Oracle server.

There is a terminal here.
Exit is up.
> look terminal
You see a rackmount terminal with a blinking cursor.
> type terminal
SQL> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
MySQL Error 1064: You have an error in your SQL syntax near 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa080581f00804b38a08053f2208052f8f'
SQL> SQL>
SQL> select * from memory where address = 0x080581f0;
0x9af58cab
SQL> select * from memory where address = 0x0804b38a;
0xa81a664b
SQL> select * from memory where address = 0x08053f22;
0xf40e3585
SQL> select * from memory where address = 0x08052f8f;
0x6e696f64

The flag is the concatenation of these 4 DWORDS from memory, and is worth 150 points. The mock SQL REPL is vulnerable to a missing null termination if you completely fill up the 80-byte buffer with input. The function which prints the error message echoes your input and reads past the end of the buffer where you see something that looks like four memory addresses. The values at these addresses are static except for the first one which is used in the maze code for storing the checksum. It is 0 when the program starts and is 0xFFFFFFF after leaving the maze. At the beginning of the SQL function however it is XORed with 0x650a7354 to give you 0x9af58cab. This is quite easy to solve with just a disassembler as the function directly references all these memory locations to print them into the space on the stack after the input buffer. To befuddle those using a disassembler, the last DWORD is in the middle of the string “You’re doing it wrong.”
Next we run back up the staircase and out of the cave to get some fresh air.

> u
A staircase spirals down under the server room. You smell something sweet and
suspect it's a halon leak, perhaps you shouldn't spend a lot of time down here.

Exits are up and down.
> u
At the back of the server room you see a cat-5 cable running down through the
opening of a displaced floor tile.

Exits are south and down.
> s
You are in a server room. There are four rows of cages packed with Dell, HP,
and Sun hardware.

There is a PE2650 here.
There is a VP here.
Exits are north and south.
> s
You find yourself under a huge dome of rock with light coming in through an
opening too high up to reach.

There is a sign here.
Exits are north, south, east and west.
> w
You are in a long narrow passageway, there is a strong breeze from the west.

Exits are east and west.
> w
You are standing outside. There is a cave to the east.

Exits are north, south and east.
> s
You are on a long twisting mountain path.

Exits are north and south.
> s
You are standing outside a yurt near the top of a mountain.
There is a path leading down to the north and up to the south.

Exits are north, south and east.
> e
You are inside a large yurt. You see filing cabinets, stacks of fan-fold
tractor-feed printouts piled on pizza boxes, a bug collection, and a jar
labeled "developer tears."

There is a wizard here.
Exit is west.
> look wizard
You see a gray old wizard, he doesn't have a long beard or a pointy hat,
but you can see the wisdom and authority in his eyes.
> talk wizard
The wizard looks deep into /dev/urandom and says: antilacrijudiintrazakordo.
> talk wizard dudatacodudanosemosaqueso
The wizard scratches many letters and numbers onto a piece of paper and hands
it to you. As soon as you read "5085d650d97d48bfc91c4fc93793a651" the paper
slips out of your hands as if it had passed right through them and dissolves
before reaching the floor.

This flag is worth 150 points but turned out to be the most difficult. The wizard gives you a random 30-bit number, n, encoded as 6 “magic words.” The wizard then expects a 30-bit number back from you, x, and computes (x - n) % 65413 and checks that this value is equal to 26347. He then generates the flag from (x - n). Since there are 16,415 30-bit numbers which satisfy the modulo check, you need to figure out which one is actually a valid flag. Brute-forcing the scoreboard would be difficult because of the CAPTCHA. The value the wizard is looking for is the last 30 bits of the maze flag. Due to a typo when modifying the maze level to use the memory address from the oracle level, this value comes directly from the pre-computed table in the CRC32 algorithm. This made it possible to solve this level with another kind of brute force: simply checking every DWORD in the adventure binary, only one of which passes the modulo check.
Next we continue up the mountain.

> w
You are standing outside a yurt near the top of a mountain.
There is a path leading down to the north and up to the south.

Exits are north, south and east.
> s
At the top of the mountain you stand before a grand stone altar.

There is a necronomicon here.
Exit is north.
> look necronomicon
You see the book of the dead, bound in human flesh and inked in blood; this
ancient Sumerian text contains bizarre burial rights, funeral incantations,
and 128-bit hex numbers; it was never meant for the world of the living.
> talk necronomicon
Do you remember the words?
> talk necronomicon klaatu barada nikto
Segmentation fault (core dumped)

What happened here? Examining this function you’ll find that it executes “int 42h” which will cause it to crash on a normal Linux system. Here we need a hint from Aaron:

Trying this again in the JS Linux emulator:

> talk necronomicon klaatu barada nikto
Your vision blurs, stumbling to the ground you try to hold on. You fall
through the earth...

You find yourself under a huge dome of rock with light coming in through an
opening too high up to reach.

This flag is worth 300 points. Looking at the function in a disassembler shows that the input is compared against “klaatu barada nikto” but just before the strcmp call the code executes the “int 42h” instruction. To figure this out you had to examine JS Linux to find the code that we added:

if (0x42 == ga) {
    fa = xa[0] + 7;
    sb(118);
    fa += 1;
    sb(101);
    fa += 3;
    sb(116);
    fa += 4;
    sb(101);
    fa += 1;
    sb(99);
    fa += 1;
    sb(107);
    fa += 1;
    sb(116);
    fa += 1;
    sb(105);
    fa += 1;
    sb(101);
    fa += 1;
    sb(0);
}

This code transforms the string pointed to by eax from “klaatu barada nikto” to “klaatu verata necktie.” After the strcmp the string is then zeroed out so that it can’t be found in memory afterwards. This also means you only have one shot at speaking the right words.

> talk necronomicon klaatu verata necktie
The wind picks up and builds into a high-pitched scream. The book slams open,
pages flying, suddenly stopping on a blank page. Blood-red spots appear,
growing larger and joining until the entire page is covered, then fade away
leaving only: 23eb43f3071731e5c1a189aa8cdbfbc4.

Let’s see what we can find to the north.

> n
You are standing outside a yurt near the top of a mountain.
There is a path leading down to the north and up to the south.

Exits are north, south and east.
> n
You are on a long twisting mountain path.

Exits are north and south.
> n
You are standing outside. There is a cave to the east.

Exits are north, south and east.
> n
You stand in front of a tavern, the lights are on but it's eerily quiet.

Exits are south and west.
> w
In the center of the tavern are shelves of colorful bottles reaching to the
ceiling and an oval-shaped bar surrounding them. On the bar are 1024 shots of
some sort of moonshine forming a line completely encircling it.

There is a bartender here.
Exit is east.
> look bartender
You see a bartender named Josephus, but you can call him Joe.
> talk bartender
Would you like to play a little drinking game?
y/n? y
Josephus takes out a tiny flag on a tiny stick and places it in the glass in
front of you and says:
Let's call this shot number 7, you must start at shot number 1. You pick a
number between 0 and 1024 and that is how many glasses you skip before taking
the next shot. Once you take a shot that glass is removed from the bar. You
continue around the bar skipping and drinking, over and over, until you have
consumed all the drinks except for number 7, then you can take the flag.
What number do you choose? 0
You drink shot number 1.
You drink shot number 2.
You drink shot number 3.
You drink shot number 4.
You drink shot number 5.
You drink shot number 6.
Josephus snatches the flag from the shot in front of you and says:
You lose! There are 1018 shots left on the table. C'mon, Euler got this on his
first try.
Josephus sets up the game for the next player.
> talk bartender
Would you like to play a little drinking game?
y/n? y
Josephus takes out a tiny flag on a tiny stick and places it in the glass in
front of you and says:
Let's call this shot number 7, you must start at shot number 1. You pick a
number between 0 and 1024 and that is how many glasses you skip before taking
the next shot. Once you take a shot that glass is removed from the bar. You
continue around the bar skipping and drinking, over and over, until you have
consumed all the drinks except for number 7, then you can take the flag.
What number do you choose? -73
You drink shot number 952.
You drink shot number 883.
You drink shot number 842.
...
You drink shot number 604.
You drink shot number 717.
You drink shot number 393.
Victorious, you snatch the flag from the last glass. The flag reads:
a642940d0033a5fe920c275a6667c9e2.
Your head is spinning; you black out and hit the floor. Josephus loots your
corpse and sets up the game for the next player. You come to the next morning,
wondering where your pants are.

This flag is worth 250 points. This drinking game is better known as the Josephus problem. The strait-forward approach is to write a program to simulate the game and try every possible input. This will show that there is no solution in the range 0 to 1,024. However the bartender is vulnerable to a signedness bug. The input is compared against 1,024 as a signed integer and if it is less than or equal to 1,024 it is accepted. When it is used as a count for how many glasses to skip it is used as an unsigned integer, so an input of -73 is interpreted as 4,294,967,223. There are multiple negative solutions so to restrict it to a single solution, from which a unique flag is generated, the input is taken modulo 1,024. The bartender code is very inefficient so it cannot be used to find the negative solution directly by trying all possibilities.

The Map

The last two flags are hidden in the map.
CTF-Final-edge
One flag is simply 16 hex ascii digits appended to the end of the JPEG file worth 75 points. The other flag is a QR code worth 100 points.
The hint on the map, bHFoczovL2Nlb2hrLmd6eC9LM2g1N1VhDQo=, is base64-decoded to: lqhs://ceohk.gzx/K3h57Ua
This is Vigenère-decoded with the key “ExodusIntelligence” to: http://imgur.com/C3b57Qn

Which is folding instructions for the map. The fold lines are faintly visible in the map. Once folded the QR code containing the flag appears. Some trimming of edges and color-enhancing with a sharpie, or GIMP, might be necessary.

CTF-map-folded

Finally

Congratulations to our winners!
Team DatNoobs took first place for $3,000 by completing all of the challenges first. Team StratumAuhuur took second place for $1,500 by being the second team to finish. No team took the third place prize of $750 before the competition ended.

We had a ton of fun organizing this competition for all of you adventurers. Thanks for playing and see you again next time!

Introducing LiveFire

Exodus Intelligence is excited to announce a new service offering developed via a partnership with Syndis, an Icelandic information security think-tank based in Reykjavik.

Here at Exodus, we focus exclusively on developing sophisticated zero-day exploits that mimic the characteristics of real-world advanced attackers. By partnering with Syndis, we are able to put these tools in the hands of their seasoned team of security professionals, thereby allowing our joint customers to experience what it would be like to be targeted by a well-equipped adversary. Departing from the check-box security mentality and entering engagements as if they were actual attacks conducted by operators with sophisticated zero-day vulnerabilities results in metrics that enable our clients to empirically analyze and improve their defensive methodologies.

A LiveFire exercise is unlike any other service offering on the market; we’ve studied high-profile breaches and analyzed the tactics of today’s most capable adversaries to ensure that the experience we deliver is on-par, and even above, what a high-value target must be prepared to withstand.

livefire_logo_crop

LiveFire: This is not a drill.

logo_transparent

syndis_cropped

You can read the full press release here (PDF).

Reversing the Interview Process

As you may know, we recently brought Rolf Rolles on board the team here at Exodus. We all met at our Austin office and Rolf spent a week working alongside us. Our interview process doesn’t consist of contrived questions intended to observe the interviewee’s capacity for mental acrobatics. Traditionally, when we bring someone in for consideration we are already familiar with their past work and skillset. What we are more interested in is evaluating their capacity to work as part of our team. So, Rolf spent his time auditing code and writing some instrumentation tools for some of the problems we were facing at the time. It went very well, and we’re thrilled that he decided to join us.

One night during that week we were chatting with Rolf about random programming problems and he recalled the story of a past interview whereby he was asked to implement a strlen() function in C that, when compiled, would not contain any conditional branches. He didn’t pose the problem as a challenge but Brandon, Zef, and I all found it intriguing and took a shot at solving it. Leave it to Rolf Rolles to reverse the interview process itself…

Spoiler alert: what follows are our independently created solutions.


Brandon’s Solution:


#include <stdio.h>
#define f(b) ((-b)>>31)&1
typedef unsigned int (*funcptr)(unsigned int x);
funcptr functable[2];
unsigned char *p;
unsigned int done(unsigned int x)
{
    return x;
}
unsigned int counter(unsigned int x)
{
    return(functable[f(*(p+x+1))](x+1));
}
int  main(int argc, char *argv[])
    unsigned int len;
    p = (unsigned char *)argv[argc-1];
    functable[0] = (funcptr)&done;
    functable[1] = counter;
    len = functable[f(*p)](0);
    printf("len is %un", len);
    return 0;
}


Zef’s Solution:


/*
*
* strlen without conditional branch
* compiles with -Wall -ansi
*/

#include <stdio.h>

int _gtfo(char *s);
int _str_len(char *s);
int (*f[])(char *s) = {_gtfo, _str_len};

int _gtfo(char *s)
{
    return -1; /* set to '0' to include trailing null */
}

int _str_len(char *s){
    char c = *s;
    return f[((c & 0x01))|
    ((c & 0x02) >> 1)|
    ((c & 0x04) >> 2)|
    ((c & 0x08) >> 3)|
    ((c & 0x10) >> 4)|
    ((c & 0x20) >> 5)|
    ((c & 0x40) >> 6)|
    ((c & 0x80) >> 7)](++s) +1 ;

}

int main(int argc, char *argv[])
{
    if(argc > 1 ) printf("strlen("%s") = %dn", argv[1], _str_len(argv[1]));
    return 0;
}

Zef’s description:

“So, my immediate thought was to use function pointers to ‘conditionally’ execute code without a conditional branch. There are two possible states for each member of a string when performing a ‘strlen’-type operation. ‘Terminator’ and ‘Not Terminator’. In this case the ‘Terminator’ for a C-string is ‘NULL’ (0x00). This of course is the only value with 0 bits set; by masking each bit in the 8 bit value and shifting to the lsb then combining the values with a ‘|’ operation, a binary state is created allowing for the indepedent execution of the two defined states ‘Terminator’ and ‘Not Terminator'”.


Aaron’s Solution:

As I admittedly suck at C, I approached the problem in straight assembly (I know, that’s cheating. And yes, this could be achieved with a rep scasb, but that’s just too easy). However, I was able to solve the problem in 27 bytes:


[BITS 32]

section .text

global _start

_start:
    pop eax
    pop eax
    xor eax, eax
    xor ebx, ebx
    pop esi

_continue:
    mov al, [esi]
    add al, 0xFF
    salc
    inc al
    lea ecx, [0x8048097+eax*4]
    jmp ecx
inc ebx
inc esi
jmp _continue
int 0x80

The three pops that occur within _start are to get access to argv[1] (the string to be measured, provided on the command line). The last pop esi puts a pointer to the string into the esi register.

The mov al, [esi] grabs a single byte off the string. Then, the add al, 0xFF is used to determine whether the byte is NULL or not. If the value is non-NULL, the add to the 8-bit register al will set the Carry flag. If it is NULL, it will not set the CF.

The next instruction is actually considered undocumented (even objdump shows the mnemonic as ‘bad’). What the salc instruction does is sets the al register to 0xFF if the Carry flag is set, otherwise it sets it to 0x00. This is the method I used to implement a binary state to determine if the character is NULL or not.

The inc al instruction then increments al, which was either 0xFF or 0x00. After the inc it will either be 0x00 or 0x01.

The lea ecx, [0x8048097+eax*4] instruction loads into ecx either the address 0x8048097 or 0x804809b. These addresses are significant and can be observed by objdump’ing the assembled binary:


$ objdump -d strlen_no_conditionals -M intel

strlen_no_conditionals: file format elf32-i386

Disassembly of section .text:

08048080 :
 8048080:       58                      pop    eax
 8048081:       58                      pop    eax
 8048082:       31 c0                   xor    eax,eax
 8048084:       31 db                   xor    ebx,ebx
 8048086:       5e                      pop    esi

08048087 :
 8048087:       8a 06                   mov    al,BYTE PTR [esi]
 8048089:       04 ff                   add    al,0xff
 804808b:       d6                      (bad)
 804808c:       fe c0                   inc    al
 804808e:       8d 0c 85 97 80 04 08    lea    ecx,[eax*4+0x8048097]
 8048095:       ff e1                   jmp    ecx
 8048097:       43                      inc    ebx
 8048098:       46                      inc    esi
 8048099:       eb ec                   jmp    8048087 
 804809b:       cd 80                   int    0x80
$

So, if the character is not NULL, the code will jmp ecx to 0x8048097 which increments the string length counter (ebx) and increments the string pointer (esi) and then branches unconditionally to _continue.

If the value was NULL, the jmp ecx will land directly at the int 0x80. As the size of the inc ebx and inc esi and jmp _continue is exactly 4 bytes, the lea instruction very conveniently can load either the address of the inc ebx or directly at the int 0x80, thus removing the need for any NOP-like instructions.

The last convenient optimization to note is that the int 0x80 will execute the syscall specified by the eax register. Well, because the result of the add/salc/inc condition will set eax to 1 only when a NULL is found, the int 0x80 will execute syscall #1 which on Linux is exit(). Additionally, the exit code is specified by the ebx register. That is why I used the ebx register as my counter to hold the string length. So, upon execution of the interrupt, the exit code will contain the length of the string as can be observed by running the assembled binary and inspecting the return value:


$ nasm strlen_no_conditionals.asm -f elf -o a.o
$ ld -o strlen_no_conditionals a.o
$ ./strlen_no_conditionals "ExodusIntel" ; echo $?
11
$ ./strlen_no_conditionals "should return 16" ; echo $?
16
$


Rolf’s Solution:

“Basically, the fundamental problem to overcome with this challenge is to ‘make a decision’ — that is to say, decide when to terminate the iteration upon reaching a NULL character — without using an explicit jcc-style conditional branch. A few minutes’ reflection upon this problem yields that we could use recursion into a function pointer table with 256 entries, where 255 of the entries increased some counter variable, and the entry at 0 terminates the procedure and returns the counter. In doing so, we have replaced all conditional jumps with one indexed, switch jump. Some further reflection provides the reduction of the table size from 256 entries down to two.”


typedef int (*ctr)(char *);
int func(char *);
int func_x(char *c) { return 1+func(c); }
int func_0(char *c) { return 0; }
ctr table[2] = { &func_0, &func_x };
int func(char *c) { return table[!!*c](c+1); }


If you’ve come up with an interesting approach, we’d love to see it. Feel free to leave a comment or some such.


Aaron Portnoy
@aaronportnoy