RedpwnCTF2020 author writeups: R1SC, Wintendo Nii

2020, June 25 (Thursday)

Both of my problems for this CTF were reversing problems, and are hosted (alongside their source) at this link.


This was a fairly tricky VM problem implementing a subleq architecture.

Source (for GNU AS):

.global _start



        leaq s_enter(%rip), %rsi
        callq puts

        xorq %rdi, %rdi
        leaq t_chk(%rip), %rsi
        movq $0x30, %rdx
        # sys_read
        xorq %rax, %rax

        leaq tbl(%rip), %rbp
        xorq %rsi, %rsi
        callq subleq

        cmpq $0, tbl(%rip)  # return code, this time
        je win
        leaq s_lose(%rip), %rsi
        callq puts
        movq $-1, %rdi
        jmp exit

                leaq s_win(%rip), %rsi
                callq puts
                xorq %rdi, %rdi
                # sys_exit
                movq $0x3C, %rax

        movq $1, %rdi
        movzbq -1(%rsi), %rdx
        # sys_write
        movq $1, %rax

        # branch to index 1 to quit
        cmpq $1, %rsi
        jne subcheck
                movq (%rbp, %rsi, 8), %rax
                movq (%rbp, %rax, 8), %rax
                movq 8(%rbp, %rsi, 8), %rbx
                subq %rax, (%rbp, %rbx, 8)
                ja next
                cmpq $2, 0x10(%rbp, %rsi, 8)
                je dbp
                cmpq $0, 0x10(%rbp, %rsi, 8)
                je next
                movq 0x10(%rbp, %rsi, 8), %rsi  # branch
                jmp subleq
                int3    # let's hope some people find this :)
                addq $3, %rsi
                jmp subleq


.byte 19
s_enter: .ascii "Enter access code: "
.byte 19
s_win: .ascii "Access authorized.\n"
.byte 15
s_lose: .ascii "Access denied.\n"

.macro SUBLEQ a=9, b=9, c=0
        # default to SUBLEQ Z, Z
        .quad \a; .quad \b; .quad \c
.macro _DBP
        .quad 9; .quad 9; .quad 2
.macro _ADD a=9, b=9
        SUBLEQ \a, 9
        SUBLEQ 9, \b
        SUBLEQ 9, 9
.macro _MOV a=9. b=9
        SUBLEQ \b, \b
        SUBLEQ \a, 9
        SUBLEQ 9, \b
        SUBLEQ 9, 9

# registers
.set Z, 9
.set O, 10
.set A, 11
.set B, 12
.set C, 13
.set D, 14
.set N2, 15


        SUBLEQ Z, Z, (t_main-tbl)/8

        # registers:
        t_chk: .fill 6, 8, 0
        # Z @09,   O @10,    A @11
        .quad 0; .quad 1; .quad 0
        # B @12,   C @13,    D @14
        .quad 0; .quad 0; .quad 82
        # N2 @ 15
        .quad -2


        SUBLEQ A, A
        _MOV O, B
        _MOV B, C
        # ramp up fib until big enough
                _ADD A, C
                _MOV B, A
                _MOV C, B
                SUBLEQ O, D, (t_fibready-tbl)/8
                SUBLEQ Z, Z, (t_fibinit-tbl)/8

        # subtract A from the input
        SUBLEQ A, (t_chk-tbl)/8

        # continue encrypting input by subtracting keys
        _ADD A, C
        _MOV B, A
        _MOV C, B
        SUBLEQ A, (t_chk-tbl)/8+1
        _ADD A, C
        _MOV B, A
        _MOV C, B
        SUBLEQ A, (t_chk-tbl)/8+2
        _ADD A, C
        _MOV B, A
        _MOV C, B
        SUBLEQ A, (t_chk-tbl)/8+3
        _ADD A, C
        _MOV B, A
        _MOV C, B
        SUBLEQ A, (t_chk-tbl)/8+4
        SUBLEQ B, (t_chk-tbl)/8+5

        # subtract encrypted input from ciphertext (want result to be -1)
        SUBLEQ (t_enc-tbl)/8, (t_chk-tbl)/8
        SUBLEQ (t_enc-tbl)/8+1, (t_chk-tbl)/8+1
        SUBLEQ (t_enc-tbl)/8+2, (t_chk-tbl)/8+2
        SUBLEQ (t_enc-tbl)/8+3, (t_chk-tbl)/8+3
        SUBLEQ (t_enc-tbl)/8+4, (t_chk-tbl)/8+4
        SUBLEQ (t_enc-tbl)/8+5, (t_chk-tbl)/8+5

        # win if t_chk is all 0xFF
        SUBLEQ N2, (t_chk-tbl)/8+2, (t_lose-tbl)/8
        SUBLEQ N2, (t_chk-tbl)/8+4, (t_lose-tbl)/8+3
        SUBLEQ N2, (t_chk-tbl)/8+1, (t_lose-tbl)/8+6
        SUBLEQ N2, (t_chk-tbl)/8+3, (t_lose-tbl)/8+9
        SUBLEQ N2, (t_chk-tbl)/8+5, (t_lose-tbl)/8+12
        SUBLEQ N2, (t_chk-tbl)/8, (t_lose-tbl)/8+15
        SUBLEQ 0, 0, 1  # ret 0

        t_enc:  # hidden ciphertext ;)
        .ascii "\x20\x95\xBE\xB0\x30\x94\x89\x73"
        .ascii "\xCD\xD4\x29\xEE\x47\xF6\xD2\x5D"
        .ascii "\x7A\x0A\x8E\x3F\xF6\x3E\x29\x72"
        .ascii "\xD1\x7E\x46\xC0\x8C\xBF\xD8\x71"
        .ascii "\xDA\x17\x58\x89\x02\x89\x9D\x5F"
        .ascii "\x53\xE7\x29\xCE\x96\xFE\xC3\x73"
        t_lose: # fill with nops to foil instruction count attacks
        SUBLEQ Z, Z
        SUBLEQ Z, Z
        SUBLEQ Z, Z
        SUBLEQ Z, Z
        SUBLEQ Z, Z
        SUBLEQ Z, Z, 1  # ret

As you can see, the backbone of the program is an interpreter, running subleq instructions in the data segment of the binary. I included an Easter egg here: if you wanted to debug this subleq, you could actually create a debug breakpoint by setting the third number of any operation to 2. A value of 0 would mean branch to the next instruction, and a value of 1 would mean return; any other value is a regular branch.

The actual flag checking is done by generating Fibonnaci numbers until they are 8 bytes, and then those are subtracted 8 bytes at a time from the input as a sort of encryption.

Then, this is checked against the ciphertext near the end of the file, in an interesting way: every quadword of the ciphertext is supposed to be one less than the encrypted input, that way a subtraction of the encrypted flag from the input yields the value 0xFFFFFFFFFFFFFFFF for every quadword.

This allows me to then verify the flag in a similar manner to this pseudocode:

subleq $0xFFFFFFFFFFFFFFFE, result, lose

In other words, if the result of subtracting the encrypted flag from the input is less than or equal to 0xFFFFFFFFFFFFFFFE, the VM jumps to “lose.” Only of the subtraction yields 0xFFFFFFFFFFFFFFFF for all six quadwords of the flag, will it zero the return value (index 0 in the subleq table) and return. This is a rather unconventional way of implementing the “cmp” instruction in subleq, but it was the most efficient method I could think of.

Here’s my Python script I used to create the ciphertext:

#!/usr/bin/env python3

flag = "flag{actually_3_instructions:_subleq,_ret,_int3}"

assert len(flag) == 6*8

a = 0x00D9CD4AB6A2D747
b = 0x016069317E428CA9
d = 0

for i in range(0, 6*8, 8):
    f = int.from_bytes(flag[i:i+8].encode("ascii"), "little")
    k = a - 1
    print(int.to_bytes(f-k, 8, "little").hex(r'_').upper())
    d = a + b
    a = b
    b = d

Wintendo Nii

This problem was also written in x86 ASM for GNU AS. Source:

.global _start



# Input must be 0 to 256 bytes, encoded into 0 to 512 bytes of (uppercase) hex.
# first 8 bytes must match the file signature "NIIv1.0:"
# next 8 bytes must match a valid game title (e.g. "AmnlXing")
# next 4 bytes are a CRC-32 of the code portion of the game
# remaining bytes are game code

        movq $60, %rax
        movq $1, %rdi

        cmpb $0x30, %al
        jl error
        cmpb $0x39, %al
        jle dh_digit
        cmpb $0x41, %al
        jl error
        cmpb $0x46, %al
        jg error
        subb $0x07, %al
                subb $0x30, %al


        movq %rsp, %rbp

        movq $1, %rax        # write
        movq $1, %rdi
        leaq s_welcome, %rsi
        movq $0x59, %rdx

        movq $9, %rax        # mmap
        xorq %rdi, %rdi                # addr
        movq $0x1000, %rsi        # len (page size)
        movq $0x1, %rdx                # prot (+r
        orq $0x2, %rdx                # +w)
        movq $0x2, %r10                # flags (private
        orq $0x20, %r10                # anonymous)
        movq $-1, %r8                # fd
        xorq %r9, %r9                # off
        # remove when ready:
        movq %rax, p_game
        movb $0xC3, (%rax)        # ret

        xorq %rax, %rax # read
        xorq %rdi, %rdi # fd
        leaq game_enc, %rsi # buf
        movq $0x200, %rdx   # count
        movq %rax, %rbx # nbytes read
        shrq $1, %rbx
        movw %bx, game_len
        xorq %rcx, %rcx
                movb 0(%rsi, %rcx, 2), %al
                callq decode_hexchar
                salw $12, %ax   # %al -> %ah; salb $4, %ah
                movb 1(%rsi, %rcx, 2), %al
                callq decode_hexchar
                addb %ah, %al
                movb %al, 0(%rsi, %rcx)
                incq %rcx
                cmpq %rbx, %rcx
                jl decode_hexpair

        # check for valid 8-byte signature
        movq $0x3A312E307649494E, %rax  # "NIIv1.0:"
        cmpq %rax, (%rsi)
        jne error
        # check for valid 8-byte title
        movq $0x636E7250746C7754, %rax  # "TwltPrnc"
        cmpq %rax, 8(%rsi)
        je header_ok
        movq $0x747261436F72614D, %rax  # "MaroCart"
        cmpq %rax, 8(%rsi)
        je header_ok
        movq $0x2B2B73656E746946, %rax  # "Fitnes++"
        cmpq %rax, 8(%rsi)
        je header_ok
        movq $0x676E69586C6E6D41, %rax  # "AmnlXing"
        cmpq %rax, 8(%rsi)
        je header_ok
        jmp error
        # validate CRC
        xorq %rbx, %rbx
        xorq %rdx, %rdx
        movl 0x10(%rsi), %edx
        leaq 0x14(%rsi), %rsi
        movzwq game_len, %rbx
        # apped zeroes
        movl $0, 0x14(%rsi, %rbx)
        # polynomial: x³²+x³¹+x⁴+1
        movq $0b110000000000000000000000000010001, %rax
        # %rax: polynomial; %bl: message byte; %r8: loop counter
        # %edi: remainder; %edx: checksum from game; %rsi: address of byte
        movq $0x14, %r8
                movb (%rsi), %bl
                movb $7, %cl
                        xorq %r9, %r9
                        # shift remainder accumulator
                        shll $1, %edi
                        # check if bit shifted out was 1
                        cmovcq %rax, %r9
                        # move next bit of message byte into remainder's LSB
                        movb %bl, %r10b
                        shrb %cl, %r10b
                        andb $1, %r10b
                        xorb %r10b, %dil
                        # remainder ^= poly iff bit shifted out was 1
                        xorq %r9, %rdi
                        # loop
                        decb %cl
                        cmpb $0, %cl
                        jge crc_bit
                incq %rsi
                incq %r8
                cmpw game_len, %r8w
                jl crc_byte
        cmpl %edi, %edx
        jne error

        leaq game_enc, %rsi
        leaq 0x14(%rsi), %rsi
        movq p_game, %rdi
        movzwq game_len, %rcx
        subq $0x14, %rcx
        rep movsb (%rsi), (%rdi)

        movq $10, %rax  # mprotect
        movq p_game, %rdi   # addr (p_game)
        movq $0x1000, %rsi  # len (page size)
        movq $0x1, %rdx # prot (+r
        orq $0x4, %rdx  # +x)
        movq p_game, %rax
        callq *%rax

        movq $60, %rax
        movq $0, %rdi
        .ascii "int main(){puts(flag);}"    # lol

p_game: .quad 0x03010102464C457F    # ELF header ;)
        .ascii "\xE4\xBA\x8C\xE3\x80\x87\xE4\xBA"
        .ascii "\x8C\xE3\x80\x87\xE5\xB9\xB4\xEF"
        .ascii "\xBC\x8C\xE7\xA8\xB3\xE5\xA4\xA9"
        .ascii "\xE5\xA0\x82\xE8\xBD\xAF\xE4\xBB"
        .ascii "\xB6\xE5\x85\xAC\xE5\x8F\xB8\xE2"
        .ascii "\x80\x94\xE2\x80\x94\xE7\x89\x88"
        .ascii "\xE6\x9D\x83\xE6\x89\x80\xE6\x9C"
        .ascii "\x89\xE3\x80\x82\x0A\xE8\xAF\xB7"
        .ascii "\xE6\x8F\x92\xE5\x85\xA5\xE6\xB8"
        .ascii "\xB8\xE6\x88\x8F\xE7\xA3\x81\xE7"
        .ascii "\x9B\x98\xE2\x8B\xAF\xE2\x8B\xAF"
        .ascii "\x0A\x00"
game_len: .short 0
        .long 0x90C03148
        .word 0x050F    # all just junk, will be overwritten
        .fill 0x200-(.-game_enc), 1, 0x90
        .long 0 # extra space for appended CRC width

Overall, I actually expected this problem to be much easer than R1SC but it had fewer solves in the end. The CRC can be calculated by setting it to something random and then running the binary, setting a breakpoint at the end of the CRC check, and stealing the CRC from %edi.

My final payload (in pail:axd format):

// header
.ascii "NIIv0.1:"

// game title
.ascii "AmnlXing"

// CRC

!rasm2 -b 64 -a -s att 'movq $59, %rax'
!rasm2 -b 64 -a -s att 'movq $0x00402000, %rdi'
!rasm2 -b 64 -a -s att 'movq $0x0068732F6E69622F, %rbx'
!rasm2 -b 64 -a -s att 'movq %rbx, (%rdi)'
!rasm2 -b 64 -a -s att 'xorq %rsi, %rsi'
!rasm2 -b 64 -a -s att 'xorq %rdx, %rdx'
!rasm2 -b 64 -a -s att 'syscall'

This compiles to the following input: