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

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