r1sc (487pt)

Rev

Files:

• r1sc

Extra:

• subleq_bin (extracted subleq code)
• subleq.py (Binary Ninja subleq disassembler)

Overview:

TLDR: It’s subleq

The provided binary is fairly small. In _start we see a basic password-checker type problem:

There is a syscall to read user input into a region of memory and then we see a call to this run function:

This turns out to be a simple subleq interpreter.

Specifically, instructions consist of 3 words (each 8 bytes): [A][B][C]. This interpreter executes:

*B -= *A
if *B < 0:
    if C == 2: trap()
    elif C != 0: PC = C

Since this is already a defined esolang, I was able to find a binary ninja disassembler (created by itszn) here: https://gist.github.com/itsZN/781411170d36adb3197cba86b8653136.

The only change I made was to use 8 byte words instead of 4 and remove a specific instruction case that was not present in this version of subleq. My version is here: subleq.py.

Then I extracted the subleq ROM and disassembled with the new plugin:

After renaming some memory addresses we can start to break down the control flow:

This first loop computes the 51st fibonacci number (mod 2^64).

In the next section, we continue computing fibonacci numbers and subtract each number from an 8 byte chunk of user input. (the main program reads user input directly into the ROM).

After this, each value is compared to an existing 8 byte value in the ROM.

We can solve this with a simple python program:

import struct

def fib(x):
    a = 1
    b = 1
    
    i = 0
    while i < x:
        c = a+b & 0xffffffffffffffff
        a = b
        b = c
        
        i += 1
        
    return a

# constant values from the ROM
r = [
    0x73899430b0be9520,
    0x5dd2f647ee29d4cd,
    0x72293ef63f8e0a7a,
    0x71d8bf8cc0467ed1,
    0x5f9d8902895817da,
    0x73c3fe96ce29e753
]

s = b''

for i in range(len(r)):
    v = (-1 + r[i] + fib(0x51 + i))
    s += struct.pack('<Q', v)

print(s)

flag{actually_3_instructions:_subleq,_ret,_int3}