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.
R1SC
This was a fairly tricky VM problem implementing a subleq architecture.
Source (for GNU AS):
.att_syntax
.global _start
.text
_start:
leaq s_enter(%rip), %rsi
callq puts
xorq %rdi, %rdi
leaq t_chk(%rip), %rsi
movq $0x30, %rdx
# sys_read
xorq %rax, %rax
syscall
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
win:
leaq s_win(%rip), %rsi
callq puts
xorq %rdi, %rdi
exit:
# sys_exit
movq $0x3C, %rax
syscall
puts:
movq $1, %rdi
movzbq -1(%rsi), %rdx
# sys_write
movq $1, %rax
syscall
retq
subleq:
# branch to index 1 to quit
cmpq $1, %rsi
jne subcheck
retq
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
dbp:
int3 # let's hope some people find this :)
next:
addq $3, %rsi
jmp subleq
.data
.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
.endm
.macro _DBP
.quad 9; .quad 9; .quad 2
.endm
.macro _ADD a=9, b=9
SUBLEQ \a, 9
SUBLEQ 9, \b
SUBLEQ 9, 9
.endm
.macro _MOV a=9. b=9
SUBLEQ \b, \b
SUBLEQ \a, 9
SUBLEQ 9, \b
SUBLEQ 9, 9
.endm
# registers
.set Z, 9
.set O, 10
.set A, 11
.set B, 12
.set C, 13
.set D, 14
.set N2, 15
tbl:
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
t_main:
SUBLEQ A, A
_MOV O, B
_MOV B, C
# ramp up fib until big enough
t_fibinit:
_ADD A, C
_MOV B, A
_MOV C, B
SUBLEQ O, D, (t_fibready-tbl)/8
SUBLEQ Z, Z, (t_fibinit-tbl)/8
t_fibready:
# 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
t_win:
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:
.att_syntax
.global _start
.text
# GAME FORMAT
# 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
error:
movq $60, %rax
movq $1, %rdi
syscall
decode_hexchar:
cmpb $0x30, %al
jl error
cmpb $0x39, %al
jle dh_digit
cmpb $0x41, %al
jl error
cmpb $0x46, %al
jg error
subb $0x07, %al
dh_digit:
subb $0x30, %al
retq
_start:
movq %rsp, %rbp
# WELCOME
movq $1, %rax # write
movq $1, %rdi
leaq s_welcome, %rsi
movq $0x59, %rdx
syscall
# CREATE_MEMORY_RW
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
syscall
# remove when ready:
movq %rax, p_game
movb $0xC3, (%rax) # ret
# INPUT
xorq %rax, %rax # read
xorq %rdi, %rdi # fd
leaq game_enc, %rsi # buf
movq $0x200, %rdx # count
syscall
movq %rax, %rbx # nbytes read
shrq $1, %rbx
movw %bx, game_len
xorq %rcx, %rcx
decode_hexpair:
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
# VALIDATE
# 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
header_ok:
# 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
crc_byte:
movb (%rsi), %bl
movb $7, %cl
crc_bit:
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
# COPY
leaq game_enc, %rsi
leaq 0x14(%rsi), %rsi
movq p_game, %rdi
movzwq game_len, %rcx
subq $0x14, %rcx
rep movsb (%rsi), (%rdi)
# GAMING
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)
syscall
movq p_game, %rax
callq *%rax
exit:
movq $60, %rax
movq $0, %rdi
syscall
.ascii "int main(){puts(flag);}" # lol
.data
p_game: .quad 0x03010102464C457F # ELF header ;)
s_welcome:
.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
game_enc:
.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
6E37D96B
// GAME
!rasm2 -b 64 -a x86.as -s att 'movq $59, %rax'
!rasm2 -b 64 -a x86.as -s att 'movq $0x00402000, %rdi'
!rasm2 -b 64 -a x86.as -s att 'movq $0x0068732F6E69622F, %rbx'
!rasm2 -b 64 -a x86.as -s att 'movq %rbx, (%rdi)'
!rasm2 -b 64 -a x86.as -s att 'xorq %rsi, %rsi'
!rasm2 -b 64 -a x86.as -s att 'xorq %rdx, %rdx'
!rasm2 -b 64 -a x86.as -s att 'syscall'
This compiles to the following input:
4E494976302E313A416D6E6C58696E676E37D96B48C7C03B00000048C7C70020400048BB2F62696E2F73680048891F4831F64831D20F05