rp2sm
Categories: re
2021-07-12
by not_really
Part 1 of 2
The flag for this part is in flag1.txt.
nc mc.ax 31802
Author: asphyxia
Files: rp2sm.tar
Part 1 of 2
The flag for this part is in flag1.txt.
nc mc.ax 31802
Author: asphyxia
Files: rp2sm.tar
This insane challenge has you not only reversing a vm but writing code for it to do a task.
The goal is to find the modular multiplicative inverse of two values with only the code in the vm.
Program format
struct RtsMethodInfo {
int ptr;
int size;
byte argCount;
byte returnCount;
byte localCount;
byte unk;
}
struct RtsFile {
long rtsMagic; //must be 7f727032736d0d00
int memAddrA;
int memLenA;
int memMmapSizeA;
int memAddrB;
int memLenB
int memMmapSizeB;
ushort methodTableSize;
RtsMethodInfo methodTable[methodTableSize];
}
I’m not entirely sure what the memAddr/Len fields do, I think you can just load up bytes from the file at the address, but I never had to use it to solve this chall. I just gave them some random values and never touched them again.
I didn’t figure all of these fields at the beginning. I had localCount and returnCount set to 0 and argCount had to be 2 or the program wouldn’t even run. As I discovered more instructions, I figured out localCount would allow loading locals without crashing. And figuring out returnCount came at the end when I had written all the code and was trying to figure out how to return the result from the function.
Instructions
The instruction infos (16 bytes) are listed at 0x5d20. +0x08 has a pointer to the function that it calls. The other values seem to be flags and values indicating pushing and popping to stack. If you try to write code that will pop an empty stack, the program will quit.
Below are the x86 instructions written from rp2sm instructions. I figured these out by throwing the hex from their functions into radare2.
0x00:
nop
0x01:
add rsp, 8
0x02:
mov eax, [rsp]
push rax
0x08: //push constant int
push arg0(32)
0x09: //push constant short
push arg0(16)
0x0a: //push constant byte
push arg0(8)
0x10: //call function? idk never used it
call ???
0x11: //jump to return, all other instructions are skipped
return ???
0x12: //set a label
set label
0x13: //jump to label unconditionally by index
jump to label[arg0(16)]
0x14: //jump to label if stack is 0
pop rax
test eax, eax
jne label[arg0(16)]
0x20: //load local
mov eax, [rbp - 4 - arg0(8)*4]
push rax
0x21: //set local
pop rax
mov [rbp - 4 - arg0(8)*4], eax
0x22:
mov eax, [rsp]
mov [rbp - 4 - arg0(8)*4], eax
0x23: //load argument
mov eax, [rbp + 0x10 + arg0(8)*8]
push rax
0x30: //read data from file
pop rsi
mov eax, [rsi + r13]
push rax
0x31-0x34: //read data from file
pop rsi
mov eax, (word/byte/movzx word/movzx byte) [rsi + r13]
push rax
0x35: //set data from file
pop rdi
pop rax
mov [rdi + r13], eax
0x40: //equal to 0
pop rdx
xor eax, eax
test edx, edx
sete al
push rax
0x41: //not equal to 0
pop rdx
xor eax, eax
test edx, edx
setne al
push rax
0x42: //compare equal
pop rdx
pop rcx
xor eax, eax
cmp ecx, edx
sete bh
0x43: //compare not equal
pop rdx
pop rcx
xor eax, eax
cmp ecx, edx
setne bh
0x44-0x47: //compare < > <= >= signed
pop rdx
pop rcx
xor eax, eax
cmp ecx, edx
setl/setnle/setle/setnl al
push rax
0x48-0x4b: //compare < > <= >= unsigned
pop rdx
pop rcx
xor eax, eax
cmp ecx, edx
setb/setnbe/setbe/setnb al
push rax
0x50-0x54: //add, or, xor, add, sub values
pop rdx
pop rax
and/or/xor/add/sub eax, edx
push rax
0x5c-0x5d: //shift values
pop rcx
pop rax
shl/shr/sar rax, cl
push rax
Now that we know what kind of instructions we have, it’s time to write the program. Wikipedia has pseudo code to do this. I wrote it in javascript (no particular reason) to make sure it worked right.
function inverse(a, n) {
var t = 0;
var newt = 1;
var r = n;
var newr = a;
while (newr != 0) {
var quo = Math.floor(r / newr);
var temp = newt;
newt = t - quo * newt;
t = temp;
temp = newr;
newr = r - quo * newr;
r = temp;
}
if (r > 1) {
return "fail";
} else if (t < 0) {
t += n;
}
return t;
}
It wasn’t as easy as it may seem. Here are the issues I ran into while writing this program.
Forward jumps
The vm allows you to set a label with instruction 0x12 and jump to it with 0x13 or 0x14. The instructions are special because their arguments are two bytes, not one. When I writing the code for the program and initially writing this writeup, I thought that forward jumps were not possible because I missed this at first. Because of that, I wrote all code thinking that jumps could only jump backwards. So the following code was a lot more complicated than it should’ve been.
Multiplication/Division
Repeated addition and subtraction will do this.
//division
var la; //left hand side
var lb; //right hand side
var quo = 0;
while (true) {
la -= lb;
if (la < 0) {
break;
}
quo++;
}
//multiplication
var la;
var lb;
var prod = 0;
while (true) {
if (la == 0) {
break;
}
prod += lb;
la--;
}
Loops
Since I needed a forward jump to break out of a loop and I thought I couldn’t do that, all loop code would happen in one place with a break at the end. For example, this would not work:
while (true) {
la -= lb;
if (la < 0) {
break;
}
quo++;
}
Instead, I subtract one from the quo counter first and put it up front in the loop like this:
quo--;
la += lb;
while (true) {
quo++;
la -= lb;
if (la < 0) {
break;
}
}
This allows me to only have to jump backwards but never forwards.
If statements
If statements need forward jumps as well. Sometimes t < 0 and needs to be added with n. But again, this is sometimes. So I just left out the code for the if statement entirely and kept running the script until t >= 0.
Argument too large
The a argument of the inverse function is always 2 bytes and the n argument is always 4. n is also always > 0x80000000. This causes issues with the repeated division since it will instantly exit with the < 0 check. So I just added another loop to subtract until it’s < 0x80000000, then do the same loop but checking until < 0.
Final javascript
function inverse(a, n) {
var t = 0;
var newt = 1;
var r = n;
var newr = a;
while (newr != 0) {
var la = r + newr;
var lb = newr;
var quo = -2;
//label 1
while (true) {
quo++;
la -= lb;
if (la < 0x80000000) { //la > 0
break;
}
}
//label 2
while (true) {
quo++;
la -= lb;
if (la < 0) {
break;
}
}
la = quo;
la++;
lb = newt;
var mulRes = 0;
mulRes -= lb;
//label 3
while (true) {
mulRes += lb;
la--;
if (la == 0) {
break;
}
}
var temp = newt;
newt = t - mulRes;
t = temp;
la = quo;
la++;
lb = newr;
var mulRes = 0;
mulRes -= newr;
//label 4
while (true) {
mulRes += newr;
la--;
if (la == 0) {
break;
}
}
temp = newr;
newr = r - mulRes;
r = temp;
}
if (r > 1) {
return "failure";
} else if (t < 0) {
t += n;
console.log("you got unlucky, this number had to add");
}
return t;
}
Writing the assembly
I did all of the assembly in text first, then manually typed the hex by hand after writing it.
;local 0 = a
;local 1 = n
;local 2 = t
;local 3 = newt
;local 4 = r
;local 5 = newr
;local 6 = la
;local 7 = lb
;local 8 = quo
;local 9 = tmp
;local 0a = mulRes
;test with input
;0a 3
;21 0 ;store in a
;0a 1a
;21 1 ;store in n
23 1 ;load argument 1
21 0 ;store in a
23 0 ;load argument 0
21 1 ;store in a
0a 0
21 2 ;store in t
0a 1
21 3 ;store in newt
20 1 ;load n
21 4 ;store in r
20 0 ;load a
21 5 ;store in newr
12 ;label 0 ;;;;;;;;;;;;;;;;;;
20 4 ;load r
20 5 ;load newr
53 ;add r + newr
21 6 ;store in la
20 5 ;load newr
21 7 ;store in lb
0a 0
0a 2
54 ;-2
21 8 ;store in quo
12 ;label 1 ;;;;;;;;;;;;;;;;;;
20 8 ;load quo
0a 1
53 ;add quo + 1
21 8 ;store in quo
20 6 ;load la
20 7 ;load lb
54 ;sub la - lb
21 6 ;store in la
20 6 ;load la
0a 0
46 ;test la > 0 (inverted <=)
14 0x0100 ;if la > 0, break (TWO BYTES NOT ONE)
12 ;label 2 ;;;;;;;;;;;;;;;;;;
20 8 ;load quo
0a 1
53 ;add quo + 1
21 8 ;store in quo
20 6 ;load la
20 7 ;load lb
54 ;sub la - lb
21 6 ;store in la
20 6 ;load la
0a 0
47 ;test la < 0 (inverted >=)
14 0x0200 ;if la < 0, break (TWO BYTES)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
20 8 ;load quo
0a 1
53 ;add quo + 1
21 6 ;store in la
20 3 ;load newt
21 7 ;store in lb
0a 0
20 3 ;load newt
54 ;sub 0 - newt
21 0a ;store in mulRes
12 ;label 3 ;;;;;;;;;;;;;;;;;;
20 0a ;load mulRes
20 3 ;load newt
53 ;add mulRes + newt
21 0a ;store in mulRes
20 6 ;load la
0a 1
54 ;sub la - 1
21 6 ;store in la
20 6 ;load la
14 0x0300 ;jump is la != 0 (TWO BYTES)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
20 3 ;load newt
21 9 ;store in tmp
20 2 ;load t
20 0a ;load mulRes
54 ;sub t - mulRes
21 3 ;store in newt
20 9 ;load tmp
21 2 ;store in t
;;;
20 8 ;load quo
0a 1
53 ;add quo + 1
21 6 ;store in la
20 5 ;load newr
21 7 ;store in lb
0a 0
20 5 ;load newr
54 ;sub 0 - newr
21 0a ;store in mulRes
12 ;label 4 ;;;;;;;;;;;;;;;;;;
20 0a ;load mulRes
20 5 ;load newr
53 ;add mulRes + newr
21 0a ;store in mulRes
20 6 ;load la
0a 1
54 ;sub la - 1
21 6 ;store in la
20 6 ;load la
14 0x0400 ;jump is la != 0 (TWO BYTES)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
20 5 ;load newr
21 9 ;store in tmp
20 4 ;load r
20 0a ;load mulRes
54 ;sub r - mulRes
21 5 ;store in newr
20 9 ;load tmp
21 4 ;store in r
20 5 ;load newr
14 0x0000 ;jump is la != 0 (TWO BYTES)
;;;; main loop end
20 2 ;load t
22 0 ;idk what I was doing here lol
20 2 ;load t (return t)
;eh who needs if statements when we have random
;20 2 ;load t
;20 1 ;load n
;53 ;add t + n
;21 2 ;store in t
The final item on the stack is returned, and from there we’re good!
Final code
00000000 7f 72 70 32 73 6d 0d 00 60 00 00 00 20 00 00 00 |.rp2sm..`... ...|
00000010 20 00 00 00 60 00 00 00 20 00 00 00 20 00 00 00 | ...`... ... ...|
00000020 01 00 00 00 60 00 00 00 f0 00 00 00 02 01 20 00 |....`...ð..... .|
00000030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00000040 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00000050 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00000060 23 01 21 00 23 00 21 01 00 00 0a 00 21 02 0a 01 |#.!.#.!.....!...|
00000070 21 03 20 01 21 04 20 00 21 05 12 20 04 20 05 53 |!. .!. .!.. . .S|
00000080 21 06 20 05 21 07 0a 00 0a 02 54 21 08 12 20 08 |!. .!.....T!.. .|
00000090 0a 01 53 21 08 20 06 20 07 54 21 06 20 06 0a 00 |..S!. . .T!. ...|
000000a0 46 14 01 00 12 20 08 0a 01 53 21 08 20 06 20 07 |F.... ...S!. . .|
000000b0 54 21 06 20 06 0a 00 47 14 02 00 20 08 0a 01 53 |T!. ...G... ...S|
000000c0 21 06 20 03 21 07 0a 00 20 03 54 21 0a 12 20 0a |!. .!... .T!.. .|
000000d0 20 03 53 21 0a 20 06 0a 01 54 21 06 20 06 14 03 | .S!. ...T!. ...|
000000e0 00 20 03 21 09 20 02 20 0a 54 21 03 20 09 21 02 |. .!. . .T!. .!.|
000000f0 20 08 0a 01 53 21 06 20 05 21 07 0a 00 20 05 54 | ...S!. .!... .T|
00000100 21 0a 12 20 0a 20 05 53 21 0a 20 06 0a 01 54 21 |!.. . .S!. ...T!|
00000110 06 20 06 14 04 00 20 05 21 09 20 04 20 0a 54 21 |. .... .!. . .T!|
00000120 05 20 09 21 04 20 05 14 00 00 20 02 00 00 00 00 |. .!. .... .....|
00000130 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00000140 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
When we pass this onto the server, we have to give it two bytes representing the size of the input.
from pwn import *
p = remote("mc.ax", 31802)
f = open("pwninput.dat","rb")
p.write(f.read())
print(p.recvline())
p.close()
$ python3 submit.py [+] Opening connection to mc.ax on port 31802: Done b'\x05flag{rp2sm: the redpwn retargetable performance stack machine (performance coming soon:tm:)}\n' [*] Closed connection to mc.ax port 31802