STEM CTF: Cyber Challenge 2017 Binary 200 Writeup

Binary 200

We get a file called b2_79d817f70e8e9a0c0e001069d7d488e9a4211eac that contains some comments and some assembler source code.

# Can U reverse spim-er 3017?
# R U a memel0rd lik le l00per kn0wn as kierk

# l4st ye4r we le4rned th4t sEcUrItY tHr0uGh 0bScUrItY is a bad meme
#       th1s ye4r you will never get my fl4g.. well not never but not before the competition ends..
# U also m1ght run 0ut 0f memory by th3n
#
# run my new new asm script for the mipster skeletal processer 2.0
# it will print muh flag
# much improve on l4st ye4r, n0w U R bones lik me b4 it runs MUAHWHAHWHUEHUEHUEHUE

#░░░░░░░░░░░░▄▐░░░░░░
#░░░░░░▄▄▄░░▄██▄░░░░░
#░░░░░▐▀█▀▌░░░░▀█▄░░░
#░░░░░▐█▄█▌░░░░░░▀█▄░
#░░░░░░▀▄▀░░░▄▄▄▄▄▀▀░
#░░░░▄▄▄██▀▀▀▀░░░░░░░
#░░░█▀▄▄▄█░▀▀░░░░░░░░
#░░░▌░▄▄▄▐▌▀▀▀░░░░░░░
#▄░▐░░░▄▄░█░▀▀░░░░░░░ U HAVE BEEN RE-SPOOKED BY THE
#▀█▌░░░▄░▀█▀░▀░░░░░░░ SPOOKY SKILENTON
#░░░░░░░▄▄▐▌▄▄░░░░░░░ CAN U REVERSE THE CURSE?
#░░░░░░░▀███▀█░▄░░░░░
#░░░░░░▐▌▀▄▀▄▀▐▄░░░░░
#░░░░░▐▀░░░░░░▐▌░░░░░
#░░░░░░█░░░░░░░░█░░░░
#░░░░░▐▌░░░░░░░░░█░░░
#░░░░░█░░░░░░░░░░▐▌░░

    .text

.globl main
main:
        la      $a0, meme_in
        li      $v0, 4
        syscall

        la      $a0, new_meme
        li      $v0, 4
        syscall

        lw      $a0, meme_num
        move    $t0, $a0

        jal bif

        move $t0, $v0

w00t:
        la      $a0, meme_out
        li      $v0, 4
        syscall

        move $a0, $t0
        li $v0, 1
        syscall

        la      $a0, new_meme
        li      $v0, 4
        syscall

        j       rekt

bif:
        addi $sp, $sp, -12
        sw   $ra, 0($sp)
        sw   $s0, 4($sp)
        sw   $s1, 8($sp)

        add $s0, $a0, $zero

        addi $t1, $zero, 1
        beq  $s0, $zero, return0
        beq  $s0, $t1,   return1

        addi $a0, $s0, -1

        jal bif

        add $s1, $zero, $v0

        addi $a0, $s0, -2

        jal bif

        lw      $a0, leet_meme
        move    $t2, $a0
        div $v0, $t2
        mfhi $v0

        add $v0, $v0, $s1

        exitbif:
            lw   $ra, 0($sp)
            lw   $s0, 4($sp)
            lw   $s1, 8($sp)
            addi $sp, $sp, 12
            jr $ra

        return1:
            li $v0,1
            j exitbif

        return0:
            li $v0,0
            j exitbif
rekt:
    li      $v0, 10
    syscall

    .data
meme_in:                .asciiz "Run progr4m run! MAUAHAHAHA..."
meme_out:               .asciiz "Nice Meme: MCA-"
meme_num:               .word 200
leet_meme:      .word 13371337
new_meme:               .asciiz "\n"

The hint for the challenge mentioned SPIM a mips32 simulator that simulates mips assembler and something what seems to be simplified mips assembler. Running the given source in SPIM did not yield any results. The code just ran forever. So I manually translated the assembler to C.

#include <stdio.h>

int bif(int a){
    int s = a;
    if (s == 0) {
        return 0;
    }
    if (s==1) {
        return 1;
    }
    return bif(s -1) + bif(s -2) % 13371337;
}

int main() {
   printf("%d\n", bif(200));
   return 0;
}

Running the code as is does not give a result either, but running it with smaller parameters for the bif function eventually gives a result. Looking at the return statement in the bif function one can see that the function is highly recursive. This causes the long runtime when trying to calculate the function naively. A programming technique used to solve problems like this is called dynamic programming. An easier/different way to picture this solution is adding a cache for return values to the function. This prevents the function from recalculating already calculated results (which are used often in resolving this recursion). Since I was to lazy to implement this in C and Python already contains a function decorator that does exactly what we need, I rewrote bif in Python and added the mentioned decorator.

#!/usr/bin/env python3

import functools

@functools.lru_cache(maxsize=None)
def bif(a0):
    s0 = a0
    if s0 == 0:
        return 0
    if s0 == 1:
        return 1

    return bif(s0 - 1) + (bif(s0 - 2) % 13371337)

print ('Nice Meme: MCA-{}'.format(bif(200)))

Running this script outputs the flag in less than 100ms on my system.

Nice Meme: MCA-1193021963