The most engaging Reverse Engineering challenge of my life
The initial pitch
It started as a normal work-day morning, when my friend Alessio comes out of the blue and asked me to play some CTF.
Challenge name: VeryMuch RE
Description: Implementing my own VM - Can you check if I did it right?
Milestones
- 15 minutes: player recognizes the implemented virtual machine
- 30 minutes: (the player) starts writing a disassembler
- 1 hour: (the player) has the whole program disassembled
- 1 hour and a half: (the player) understands the logic
- 2 hours and a half: (the player comes up with a) solution
Later in the evening, I picked the challenge up. It was a ELF64 static binary written in Rust, which implemented a custom Virtual Machine.
Running it would play an animation and then it would ask for a flag. If a parameter was passed, it would output the allowed symbols the flag could contain.
Once opened up in Ghidra, I generated the graph of the main function’s Basic BLocks.
Looking at the disassembly, it was easy to spot the Virtual 32bit Registers including the Virtual Program Counter, which in this case was EBP.
|
|
I was able to locate and dump the bytecode. Each instruction was composed of a dword (4 bytes).
Giving up
After spending one hour on it, I gave up and told my friend Alessio some clues on how it could be possible to solve the challenge. I was giving up because due to the optimization done by Rust using SIMD instructions, it was too difficult for me to reverse engineer the Virtual Instructions.
Even though I was confident I could do it, I did not want to spend my time doing something that was steering me away from my studies and my job. Since it was something “I knew how to do”, I thought that I would have learned nothing from this and that I would just waste my time playing CTF instead of studying.
After this happened, I noticed my girlfriend getting really nervous and histerically laughing. After she suggested to me that this “May be important” and that “I should continue because it would be impolite to my friend” I knew she was cooking something 👩🍳
Down the rabbit hole
Now that I knew there was something more to it other than being just a CTF, I tried to focus more on the SIMD instructions to try to build a correct disassembler for the VM bytecode.
The SIMD instructions I am referring to are the following:
|
|
The program contained two blocks similar to this one. I was not able to understand how EBP was computed against the mask to then call the right virtual instruction.
To this day, I am still not able to understand how the instructions get decoded 😂
NOTE: If you understand the logic of this code block, please contact me!
UPDATE: I think I may have cracked the code. If so, I will write a follow up post at some point!
On the bright side, I was able to find some strings at the end of the bytecode, containing the
badboy (Try Again
), the godboy (YAYYY
) and what I thought was the start of the flag (flag{
).
The whole night passed then I went to bed.
Defeat?
I tried again the same approach the day later, without success. At this point I felt completely defeated and pretty bad about myself.
Not only I was not able to solve the challenge that was supposed to be easy, but I also felt I was failing my girlfriend and my friend.
Fortunately, she promptly picked me up and she gave me the force and support to continue.
Solving it, that’s what counts
At this point, I spent many hours on the challenge. It was time to pick another approach. This approach was living rent free in my head from the start and after I got it as a hint on my first give-up I knew it would work: Side-Channels.
The basic idea to this strategy is to try to count the number of instructions the programs executes in its Virtual Machine and compare the results with different given flag inputs.
I decided to try to do this with Intel-PIN. Intel-PIN allows anybody to Dynamic Binary Instrument any target, allowing at a high-level to add custom instructions after every instruction.
After downloading Intel-PIN source code, I duplicated the inscount2.cpp
tool and coded the following patch:
|
|
Using the resulting PIN tool, it was possible to infer the length of the flag. Running the target while counting the number of instructions ran in the Virtual Machine, it was possible to understand the length of the flag by observing the instrunctions increasing with the lenght of the given input up until the 39th character.
The same approach can be used to bruteforce the right character of the flag. Thanks to the strings I
found in the bytecode before, I was able to test this by replacing the initial characters of the flag
with the expected flag{
. I was able to notice an increase of the number of instructions executed in
the virtual machine for each right character in the flag 😎
It was just a matter of coding a bruteforce solution, which would run in parallel n targets with n variations of the flag, while instrumenting the target to count the number of instructions and in the end pick the flag variation which executed the maximum number of instructions.
|
|
It was only a matter of time and eventually the solution would arrive:
FLAG=flag{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=5
Found next character: 'm'
FLAG=flag{m}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=6
Found next character: 'a'
FLAG=flag{ma}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=7
Found next character: 'r'
FLAG=flag{mar}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=8
Found next character: 't'
FLAG=flag{mart}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=9
Found next character: 'i'
FLAG=flag{marti}}}}}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=10
Found next character: 'n'
FLAG=flag{martin}}}}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=11
Found next character: 'a'
FLAG=flag{martina}}}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=12
Found next character: '_'
FLAG=flag{martina_}}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=13
Found next character: ':'
FLAG=flag{martina_:}}}}}}}}}}}}}}}}}}}}}}}}} INDEX=14
Found next character: 'm'
FLAG=flag{martina_:m}}}}}}}}}}}}}}}}}}}}}}}} INDEX=15
Found next character: 'i'
FLAG=flag{martina_:mi}}}}}}}}}}}}}}}}}}}}}}} INDEX=16
Found next character: '_'
FLAG=flag{martina_:mi_}}}}}}}}}}}}}}}}}}}}}} INDEX=17
Found next character: 'v'
FLAG=flag{martina_:mi_v}}}}}}}}}}}}}}}}}}}}} INDEX=18
Found next character: 'u'
FLAG=flag{martina_:mi_vu}}}}}}}}}}}}}}}}}}}} INDEX=19
Found next character: 'o'
FLAG=flag{martina_:mi_vuo}}}}}}}}}}}}}}}}}}} INDEX=20
Found next character: 'i'
FLAG=flag{martina_:mi_vuoi}}}}}}}}}}}}}}}}}} INDEX=21
Found next character: '_'
FLAG=flag{martina_:mi_vuoi_}}}}}}}}}}}}}}}}} INDEX=22
Found next character: 's'
FLAG=flag{martina_:mi_vuoi_s}}}}}}}}}}}}}}}} INDEX=23
Found next character: 'p'
FLAG=flag{martina_:mi_vuoi_sp}}}}}}}}}}}}}}} INDEX=24
Found next character: 'o'
FLAG=flag{martina_:mi_vuoi_spo}}}}}}}}}}}}}} INDEX=25
Found next character: 's'
FLAG=flag{martina_:mi_vuoi_spos}}}}}}}}}}}}} INDEX=26
Found next character: 'a'
FLAG=flag{martina_:mi_vuoi_sposa}}}}}}}}}}}} INDEX=27
Found next character: 'r'
FLAG=flag{martina_:mi_vuoi_sposar}}}}}}}}}}} INDEX=28
Found next character: 'e'
FLAG=flag{martina_:mi_vuoi_sposare}}}}}}}}}} INDEX=29
Found next character: '?'
FLAG=flag{martina_:mi_vuoi_sposare?}}}}}}}}} INDEX=30
Found next character: '_'
FLAG=flag{martina_:mi_vuoi_sposare?_}}}}}}}} INDEX=31
Found next character: 'i'
FLAG=flag{martina_:mi_vuoi_sposare?_i}}}}}}} INDEX=32
Found next character: 'n'
FLAG=flag{martina_:mi_vuoi_sposare?_in}}}}}} INDEX=33
Found next character: 'a'
FLAG=flag{martina_:mi_vuoi_sposare?_ina}}}}} INDEX=34
Found next character: '_'
FLAG=flag{martina_:mi_vuoi_sposare?_ina_}}}} INDEX=35
Found next character: 't'
FLAG=flag{martina_:mi_vuoi_sposare?_ina_t}}} INDEX=36
Found next character: 'u'
FLAG=flag{martina_:mi_vuoi_sposare?_ina_tu}} INDEX=37
Found next character: 'a'
flag{martina_:mi_vuoi_sposare?_ina_tua}
Martina, my girlfriend, proposed me through a Reverse Engineering challenge!
Thanks Alessio for partercipating in the surprise and the Fiverr coder who created this lovely challenge ❤️❤️❤️
Download
You can download the code and binaries related to this post here. The password is the flag.
NOTE: Even though I have analyzed the target, I did not fully reverse engineered it.
Please be careful if you wish to execute it. If you decide to execute it, do it in a VM.