Intended solution of Wannavmbe challenge from InCTF Internationals 2019
tl;dr
tl;dr
Challenge Points: 769
Challenge Solves: 7
Solved by: R3x
Initial analysis shows us that there are minor changes between this binary and the signal_vm binary - in the way the VM works. Please refer to the writeup of signal_vm for learning about the VM structure.
In the first stage of the challenge - we had access to all of the VM registers since they were all in the parent itself. Now in signal_vm_de1ta they are all in the memory space of the child - This makes it hard for us to track what is happening in the VM since we aren’t able to directly view its memory or registers.
The VM uses the same four signals (SIGTRAP, SIGILL, SIGSEGV and SIGFPE) to serve as instruction classes. However there are a few significant differences from the first stage.
The VM(parent) uses PTRACE_PEEKDATA and PTRACE_POKEDATA to read and write data into the child memory which contains the memory and the registers.
We tweaked the script for the old challenge to work for this one. Since we don’t have the register and memory states this time as that happens in the child, we decided to go ahead and write our own code to parse the instructions. So we were able to predict the contents of the VM registers accurately which helped us in figuring out what the child did.
1 | import gdb |
This was probably the most complicated VM algorithm I have seen in CTFs. I have written the python version of the code below - you can take a look at it.
1 |
|
Looking a bit deeper into the algorithm we see that it is actually taking the numbers in a very specific order.
| x | z = ((x * (x + 1)) >> 1) | range of y + z |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1..2 |
| 2 | 3 | 3..5 |
| 3 | 6 | 6..9 |
| 4 | 10 | 10..14 |
| … | … | … |
| 100 | 5050 | 5050..5150 |
From this order we figured out that this was basically dividing the array in form of a triangle and then trying to find the path which has the maximum sum.
Now we know what the VM is trying to do and it is taking a long time since the VM is trying to bruteforce the path. Now all we need to do is to find a more efficient way to solve this.
Since it is copying the path that has the maximum sum. I printed out the entire array in the form of a triangle and then I searched for the flag format manually - that is de1ctf{ and then I followed it until I reached the end.
You can probably trace - ~triangle~is from the above screen shot. That was like a wrapper around the flag.
flag was
de1ctf{no~n33d~70-c4lcul473~3v3ry~p47h}
After talking to the admin at the end of the CTF I learned that this was a DP problem and the solution was pretty simple.
You can take a look at the problem statement and the solution techniques here.
tl;dr
Challenge Points: 500
Challenge Solves: 21
Solved by: R3x, silverf3lix, Ayushi
Challenge takes an input - and running strace we see that it forks a child and then does some ptrace calls.
1 | ~> strace ./signal_vm |
Taking a look into the binary for a better understanding we come across the main function.
1 | signed __int64 sub_40172D() |
This leads us to understand that the code is basically forking and trying to establish some communication between the child and parent using ptrace.
Run the binary on gdb with set follow-fork-mode child to observe the behaviour of the child. We get SIGILL.
Let take a close look at the disassembly of the child.
1 | push rbp |
This is strange - looks like the child is made to trigger the signal. This leads us to the conclusion that the parent is responsible for handling the signal and continuing the execution of the child somehow.
Now lets take a look at what is happening in the parent. On reversing the function handler we come to the following conclusions.
First thing to understand the role ptrace actually plays. Strace gives us -
1 | ptrace(PTRACE_GETREGS, 1763, NULL, 0x7ffc4cb9c0e0) = 0 |
Having not seen anything other than PTRACE_TRACEME - we start digging into the man page.
The
ptrace()system call provides a means by which one process (the “tracer”) may observe and control the execution of another process (the “tracee”), and examine and change the tracee’s memory and registers.
PTRACE_PEEKTEXT/POKETEXT - Read/Write a word at the address addr in the tracee’s memory.
PTRACE_GETREGS/SETREGS - Read/Write into the registers of the tracee.
The parent has handlers for the following signals and each of them define a certain class of instructions:
move classlogical classcompare classjump classNow the following script skims through the signals triggered and parses them to give a set of readable instructions which decreased our work.
1 | import gdb |
From the instructions given out by the above script we were able to deduce that it is basically Hill cipher.
The key Matrix is a 7x7 one generated from the string below
1 | .data:00000000006D5100 aAlmostHeavenWe db 'Almost heaven west virginia, blue ridge mountains',0 |
The ciphertext matrix can be found from the instructions generated by the above script.Then we used sagemath to do the math for us.
1 | from sage.all import * |
Running the above script gave us the flag =>
de1ctf{7h3n_f4r3_u_w3ll_5w337_cr4g13_HILL_wh3r3_0f3n_71m35_1_v3_r0v3d}