# vmwhere2 (rev)
Writeup by: [xlr8or](https://ctftime.org/team/235001)

This is a continuation of the `vmwhere1` challenge, so please read my [writeup](https://ctftime.org/writeup/37368) about it, because I am skipping some details, assuming the reader is already familiar with the first one.

In this challenge the complexity of the VM increases. The general layout is the same, the only difference is that a couple of more instructions are added. As last time, not all instructions supported by the VM are used, therefore no need for the disassembler to support all of them.

Here's the disassembler for the upgraded VM:
```python
bts = open('./program', 'rb').read()

def aschar(num):
try:
return chr(num)
except:
return num

ptr = 0
while ptr < len(bts):
cur = bts[ptr]
print(ptr, end=' - ')
if cur == 0xA:
print(f'push {hex(bts[ptr+1])} - "{aschar(bts[ptr+1])}"')
ptr += 2
elif cur == 0x00:
print('exit 0')
ptr += 1
elif cur == 0x01:
print('TOS[-2] = TOS[-2] + TOS[-1]; TOS--')
ptr += 1
elif cur == 0x04:
print('TOS[-2] = TOS[-2] | TOS[-1]; TOS--')
ptr += 1
elif cur == 0x05:
print('TOS[-2] = TOS[-2] ^ TOS[-1]; TOS--')
ptr += 1
elif cur == 0x07:
print('TOS[-2] = TOS[-2] >> TOS[-1]; TOS--')
ptr += 1
elif cur == 0x08:
print('TOS++; get(TOS[-1])')
ptr += 1
elif cur == 0x09:
print('put(TOS[-1]); TOS--')
ptr += 1
elif cur == 0xF:
print('dup')
ptr += 1
elif cur == 0xC:
jump_val = ctypes.c_int16(int.from_bytes(bts[ptr+1:ptr+3], 'big'))
print(f'if TOS[-1] == 0: ip = {ptr + jump_val.value + 3}')
ptr += 3
elif cur == 0xD:
jump_val = ctypes.c_int16(int.from_bytes(bts[ptr+1:ptr+3], 'big'))
print(f'ip = {ptr + jump_val.value + 3}')
ptr += 3
elif cur == 0x0E:
print('TOS--')
ptr += 1
elif cur == 0x11:
# LSB goes to TOS[-7] and MSB goes to TOS[-1]
print('TOS[-8..-1] = bits8(TOS[-1])')
ptr += 1
elif cur == 0x10:
rev_val = bts[ptr+1]
print(f'reverse(TOS[-{rev_val}..-1])')
ptr += 2
else:
print('Stopping at', hex(ptr))
break
```

Compared to last time, we also have some extra arithmetic operations, an operation that replaces an 8-bit value with its bits on the stack, and an operation that can reverse some portion of the stack from the current top of the stack.

This time all the flag characters are read before we can get any feedback about the correctness of it. First let's see what happens to each character of the flag:
```
116 - push 0x0 - ""
118 - TOS++; get(TOS[-1])
119 - TOS[-8..-1] = bits8(TOS[-1])
120 - push 0xff - "ÿ"
122 - reverse(TOS[-9..-1])
124 - reverse(TOS[-8..-1])
126 - push 0x0 - ""
128 - reverse(TOS[-2..-1])
130 - dup
131 - push 0xff - "ÿ"
133 - TOS[-2] = TOS[-2] ^ TOS[-1]; TOS--
134 - if TOS[-1] == 0: ip = 141
137 - TOS--
138 - ip = 145
141 - TOS--
142 - ip = 167
145 - reverse(TOS[-2..-1])
147 - reverse(TOS[-2..-1])
149 - if TOS[-1] == 0: ip = 159
152 - TOS--
153 - push 0x1 - ""
155 - TOS[-2] = TOS[-2] + TOS[-1]; TOS--
156 - ip = 160
159 - TOS--
160 - dup
161 - dup
162 - TOS[-2] = TOS[-2] + TOS[-1]; TOS--
163 - TOS[-2] = TOS[-2] + TOS[-1]; TOS--
164 - ip = 128
167 - TOS--
```

I spent a bit of time wrapping my head around this, but I got a bit stuck to be honest. Therefore I started attacking the problem from the other end, the verification of the flag. At offset 2418, the `get` blocks (there are 46 of them btw.) stop and the flag checking starts:
```
2418 - push 0xc6 - "Æ"
2420 - TOS[-2] = TOS[-2] ^ TOS[-1]; TOS--
2421 - reverse(TOS[-46..-1])
2423 - reverse(TOS[-47..-1])
2425 - TOS[-2] = TOS[-2] | TOS[-1]; TOS--
2426 - reverse(TOS[-46..-1])
2428 - reverse(TOS[-45..-1])
2430 - push 0x8b - "‹"
2432 - TOS[-2] = TOS[-2] ^ TOS[-1]; TOS--
2433 - reverse(TOS[-45..-1])
2435 - reverse(TOS[-46..-1])
2437 - TOS[-2] = TOS[-2] | TOS[-1]; TOS--
2438 - reverse(TOS[-45..-1])
2440 - reverse(TOS[-44..-1])
2442 - push 0xd9 - "Ù"
2444 - TOS[-2] = TOS[-2] ^ TOS[-1]; TOS--
2445 - reverse(TOS[-44..-1])
2447 - reverse(TOS[-45..-1])
2449 - TOS[-2] = TOS[-2] | TOS[-1]; TOS--
2450 - reverse(TOS[-44..-1])
2452 - reverse(TOS[-43..-1])

...

2970 - if TOS[-1] == 0: ip = 2976
2973 - ip = 3004
2976 - push 0x0 - ""
2978 - push 0xa - ""
2980 - push 0x21 - "!"
2982 - push 0x74 - "t"
2984 - push 0x63 - "c"
2986 - push 0x65 - "e"
2988 - push 0x72 - "r"
2990 - push 0x72 - "r"
2992 - push 0x6f - "o"
2994 - push 0x43 - "C"
2996 - if TOS[-1] == 0: ip = 3003
2999 - put(TOS[-1]); TOS--
3000 - ip = 2996

```

Here are the first few blocks of the flag check. As you might see there's some sort of repeating pattern again:
1. push some value
2. xor value with TOS
3. get bottom stack element (more on this below)
4. or top of stack (bottom element) with previous xor result
5. move back the bottom element to the bottom (indices decrease by one, because top element is consumed in the computations)

Then the pattern keeps repeating until we have no more chars in the *"array"* of 46 (+1 for the bottom element). Then we check if the top of the stack (after all computations) is zero, and if so, the user input is correct.

Now the *bottom element*. The bottom element is initially zero, and then it is `|`'d with the xor results of hardcoded values against the converted user input. At the end we still want the bottom element to be zero, therefore all xor operations need to result in zero, that is the converted user input needs to match the hard coded values.

Next we need to know the converted user input values, that I have skipped at the start. I have resorted to dynamic analysis here, instead of understanding the conversion process.

First we need to break on the position where the instruction are being decoded. This way we will know what the current instruction is, where is it in the program blob, and what the state of the stack is. To do this, we can execute the vm in `gdb` and hit `CTRL-C` when the user input is being read.
```
Program received signal SIGINT, Interrupt.
0x00007ffff7ea8b21 in read () from /usr/lib/libc.so.6
LEGEND: STACK | HEAP | CODE | DATA | RWX | RODATA
───────────────────────────────[ REGISTERS / show-flags off / show-compact-regs off ]────────────────────────────────
*RAX 0xfffffffffffffe00
*RBX 0x7ffff7f8a9c0 (_IO_2_1_stdin_) ◂— 0xfbad2288
*RCX 0x7ffff7ea8b21 (read+17) ◂— cmp rax, -0x1000 /* 'H=' */
*RDX 0x400
RDI 0x0
*RSI 0x55555555b4a0 ◂— 0x0
*R8 0x410
*R9 0x1
*R10 0x4
*R11 0x246
*R12 0x7ffff7f8b6a0 (_IO_2_1_stdout_) ◂— 0xfbad2a84
*R13 0xa68
*R14 0x7ffff7f86ca0 ◂— 0x0
*R15 0x7ffff7f87708 ◂— 0x0
*RBP 0x7ffff7f875a0 (_IO_file_jumps) ◂— 0x0
*RSP 0x7fffffffdf48 —▸ 0x7ffff7e2ea04 (_IO_file_underflow+404) ◂— test rax, rax
*RIP 0x7ffff7ea8b21 (read+17) ◂— cmp rax, -0x1000 /* 'H=' */
────────────────────────────────────────[ DISASM / x86-64 / set emulate on ]─────────────────────────────────────────
► 0x7ffff7ea8b21 <read+17> cmp rax, -0x1000
0x7ffff7ea8b27 <read+23> ja read+112 <read+112>
↓
0x7ffff7ea8b80 <read+112> mov rdx, qword ptr [rip + 0xe11b1]
0x7ffff7ea8b87 <read+119> neg eax
0x7ffff7ea8b89 <read+121> mov dword ptr fs:[rdx], eax
0x7ffff7ea8b8c <read+124> mov rax, -1
0x7ffff7ea8b93 <read+131> ret

0x7ffff7ea8b94 <read+132> nop dword ptr [rax]
0x7ffff7ea8b98 <read+136> mov rdx, qword ptr [rip + 0xe1199]
0x7ffff7ea8b9f <read+143> neg eax
0x7ffff7ea8ba1 <read+145> mov dword ptr fs:[rdx], eax
──────────────────────────────────────────────────────[ STACK ]──────────────────────────────────────────────────────
00:0000│ rsp 0x7fffffffdf48 —▸ 0x7ffff7e2ea04 (_IO_file_underflow+404) ◂— test rax, rax
01:0008│ 0x7fffffffdf50 —▸ 0x7ffff7f8b6a0 (_IO_2_1_stdout_) ◂— 0xfbad2a84
02:0010│ 0x7fffffffdf58 —▸ 0x7ffff7f875a0 (_IO_file_jumps) ◂— 0x0
03:0018│ 0x7fffffffdf60 ◂— 0xa /* '\n' */
04:0020│ 0x7fffffffdf68 —▸ 0x7ffff7f8a9c0 (_IO_2_1_stdin_) ◂— 0xfbad2288
05:0028│ 0x7fffffffdf70 —▸ 0x7ffff7f875a0 (_IO_file_jumps) ◂— 0x0
06:0030│ 0x7fffffffdf78 ◂— 0x0
07:0038│ 0x7fffffffdf80 —▸ 0x7fffffffe170 —▸ 0x7fffffffe48e ◂— 'SHELL=/usr/bin/zsh'
────────────────────────────────────────────────────[ BACKTRACE ]────────────────────────────────────────────────────
► f 0 0x7ffff7ea8b21 read+17
f 1 0x7ffff7e2ea04 _IO_file_underflow+404
f 2 0x7ffff7e2fdd6 _IO_default_uflow+54
f 3 0x555555555608
f 4 0x555555555a28
f 5 0x7ffff7dd2850
f 6 0x7ffff7dd290a __libc_start_main+138
f 7 0x5555555551e5
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
```

As the backtrace shows, we are in the `read` call right now, a result of calling `getchar` from the vm. `0x555555555608` is the address of the instruction after the call to `getchar` has finished. In ghidra, this can be found at address `0x101608`. At address `0x101486` in ghidra, the pointer to the next byte of the current instruction will be loaded, and the pointer to the current instruction is already in `rax`
```
LAB_00101482 XREF[1]: 00101950(j)
00101482 48 8b 45 e8 MOV RAX,qword ptr [RBP + local_20]
00101486 48 8d 50 01 LEA RDX,[RAX + 0x1]
```

Based on this we calculate that the offset from the return address to the desired break point is `0x182`, therefore the desired breakpoint is at `0x555555555486`.
* `x/xb $rax` will give the opcode of the current instruction
* `x/xg $rbp-16` will give the current stack pointer (recall that pointer-1 is the actual last pushed element)
* `x/xg $rbp-0x38` will give the pointer to the start of the program blob.

Now that we have this setup, we need to go offset 2418 in the program blob, where the checking will start and inspect the stack. To do this we can use a conditional breakpoint in gdb, that will stop when we reach the desired vm instruction. We know `rax` holds the current instruction address, and that `rbp-0x38` holds the address of the first instruction. Therefore we can calculate the offset at which to break.
```
pwndbg> x/xg $rbp-0x38
0x7fffffffdfc8: 0x000055555555a490
pwndbg> i r rax
rax 0x55555555a507 93824992257287
pwndbg> i b 1
Num Type Disp Enb Address What
1 breakpoint keep y 0x0000555555555486
breakpoint already hit 1 time
pwndbg> break *0x0000555555555486 if $rax == 0x000055555555a490+2418
Note: breakpoint 1 also set at pc 0x555555555486.
Breakpoint 2 at 0x555555555486
pwndbg> i b
Num Type Disp Enb Address What
1 breakpoint keep y 0x0000555555555486
breakpoint already hit 1 time
2 breakpoint keep y 0x0000555555555486
stop only if $rax == 0x000055555555a490+2418
pwndbg> disable 1
pwndbg> c
Continuing.
LLLL
LLLLAAAABBBBCCCCDDDDEEEEFFFFGGGGHHHHIIIIJJJJKKKK
```

The bottom line is the input I have entered for the flag. It is a pattern that will make it easier to recognize it in the stack dump.
```
pwndbg> x/70xb 0x00005555555594b1-70
0x55555555946b: 0x00 0x00 0x00 0x00 0x00 0xe0 0x71 0xf8
0x555555559473: 0xf7 0xff 0x7f 0x00 0x00 0x11 0x10 0x00
0x55555555947b: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x555555559483: 0xf7 0xf7 0xf7 0xf7 0x5a 0xf7 0xf7 0xf7
0x55555555948b: 0xf7 0x8e 0x8e 0x8e 0x8e 0x94 0x94 0x94
0x555555559493: 0x94 0x97 0x97 0x97 0x97 0xa6 0xa6 0xa6
0x55555555949b: 0xa6 0xa9 0xa9 0xa9 0xa9 0xaf 0xaf 0xaf
0x5555555594a3: 0xaf 0xb2 0xb2 0xb2 0xb2 0xdc 0xdc 0xdc
0x5555555594ab: 0xdc 0xdf 0xdf 0xdf 0xdf 0xe5
```

This is the stack before the checking executes. The last item here (`0xe5`) is the top of the stack (address `0x00005555555594b0`). In the items before we can notice our pattern of 4 bytes being the same. This is good, it means that conversion is not affected by previous items, each byte is converted in isolation from the others.
The top 46 bytes on the stack are our user input, ending at address `0x555555559483`. The only element that repeats 8 times here is `0x7f`, and since we have put 8 `L` characters, we know that the top of the stack will contain the last user input. Also `0x5e` denotes the new line, as can be seen after the first set of 4 `L`s.

Using this techinque we can build a map for each character that might occur in the flag, 46 characters at a time. Below are some of the results:
```python
# !! 0xf7 == 'L' !!
# LabcdefghijklmnopqrstuvwxyzABCDEFGHIJKMNOPQ
# 0x555555559483: 0xf7 0x67 0x6d 0x70 0x7f 0x82 0x88 0x8b
# 0x55555555948b: 0xb5 0xb8 0xbe 0xc1 0xd0 0xd3 0xd9 0xdc
# 0x555555559493: 0x57 0x5a 0x60 0x63 0x72 0x75 0x7b 0x7e
# 0x55555555949b: 0xa8 0xab 0xb1 0x8e 0x94 0x97 0xa6 0xa9
# 0x5555555594a3: 0xaf 0xb2 0xdc 0xdf 0xe5 0xe8 0xfa 0x00
# 0x5555555594ab: 0x5a 0x03 0x5a 0x7e 0x5a 0x81

# RSTUVWXYZ0123456789_!@#$%&*(){}LLLLLLLLLLLLLLLLLLLL
# 0x555555559483: 0x87 0x8a 0x99 0x9c 0xa2 0xa5 0xcf 0xd2
# 0x55555555948b: 0xd8 0xcc 0xcf 0xd5 0xd8 0xe7 0xea 0xf0
# 0x555555559493: 0xf3 0x1d 0x20 0xf6 0xdc 0x8b 0xe5 0xf4
# 0x55555555949b: 0xf7 0xfd 0x33 0x2a 0x2d 0xb4 0xc6 0x5a
# 0x5555555594a3: 0xf7 0xf7 0xf7 0xf7 0xf7 0xf7 0xf7 0xf7
# 0x5555555594ab: 0xf7 0xf7 0x5a 0xf7 0xf7 0xf7
```

These are the stack dumps for all characters I though could appear in the flag. `0x5e` should be ignored in the stack dump, as it is only the newline character.

Based on this mapping, and that we know what hardcoded values are used for the xor operation, we can create the following python script to recover the flag:
```python
mp = {
0x87: 'R',
0x8a: 'S',
0x99: 'T',
0x9c: 'U',
0xa2: 'V',
0xa5: 'W',
0xcf: 'X',
0xd2: 'Y',
0xd8: 'Z',
0xcc: '0',
0xcf: '1',
0xd5: '2',
0xd8: '3',
0xe7: '4',
0xea: '5',
0xf0: '6',
0xf3: '7',
0x1d: '8',
0x20: '9',
0xf6: '_',
0xdc: '!',
0x8b: '@',
0xe5: '#',
0xf4: '$',
0xf7: '%',
0xfd: '&',
0x33: '*',
0x2a: '(',
0x2d: ')',
0xb4: '{',
0xc6: '}',
0xf7: 'L',
0x67: 'a',
0x6d: 'b',
0x70: 'c',
0x7f: 'd',
0x82: 'e',
0x88: 'f',
0x8b: 'g',
0xb5: 'h',
0xb8: 'i',
0xbe: 'j',
0xc1: 'k',
0xd0: 'l',
0xd3: 'm',
0xd9: 'n',
0xdc: 'o',
0x57: 'p',
0x5a: 'q',
0x60: 'r',
0x63: 's',
0x72: 't',
0x75: 'u',
0x7b: 'v',
0x7e: 'w',
0xa8: 'x',
0xab: 'y',
0xb1: 'z',
0x8e: 'A',
0x94: 'B',
0x97: 'C',
0xa6: 'D',
0xa9: 'E',
0xaf: 'F',
0xb2: 'G',
0xdc: 'H',
0xdf: 'I',
0xe5: 'J',
0xe8: 'K',
0xfa: 'M',
0x00: 'N',
0x03: 'O',
0x7e: 'P',
0x81: 'Q',
}

values = [0xc6, 0x8b, 0xd9, 0xcf, 0x63, 0x60, 0xd8, 0x7b, 0xd8, 0x60, 0xf6, 0xd3, 0x7b, 0xf6, 0xd8, 0xc1, 0xcf, 0xd0, 0xf6, 0x72, 0x63, 0x75, 0xbe, 0xf6, 0x7f, 0xd8, 0x63, 0xe7, 0x6d, 0xf6, 0x63, 0xcf, 0xf6, 0xd8, 0xf6, 0xd8, 0x63, 0xe7, 0x6d, 0xb4, 0x88, 0x72, 0x70, 0x75, 0xb8, 0x75]

ans = ''
for v in values:
ans += mp[v]
# print(v, mp[v])

print('flag:', ans[::-1])
```
* `mp` defines the mapping from encoded characters to the original input character
* `values` is an array of hardcoded values that will be used for the xor checks

The loop will get the original value for all the characters, and lastly it will reverse the flag, since the checks start from the top of the stack, which is the last user input.
```
➜ vmwhere2 python solve.py
flag: uiuctf{b4s3_3_1s_b4s3d_just_l1k3_vm_r3v3rs1ng}
```