'Magic' was the 6th binary in this years Flare-On Challenge. From looking at the intro to this level we can guess that this might have something to do with Linux. Usually when looking at an unknown binary, I will load it up in IDA, run it through strings/FLOSS, and open it in a hex editor to check out the headers. But since we have the linux hint, lets just go ahead and fire it up in IDA and see what we find. IDA confirms our suspicion and offers to load the file as ELF64.
Looking at the Strings window and in main show us some interesting strings. You can also see in the graph overview that overall structure of the program looks fairly standard. Digging through the code a little more, and we can see that the variables [rbp-1C0] and [rbp-1B4] look to be our counter and the number of rounds. We can see [rbp-1C0] is set to 0 at 0x4039FC and [rbp-1B4] is set to 0x29A (666) at 0x403926. These variables are compared at 0x403BD9 and if they are equal, then we jump to our "Congrats" message, otherwise we check the next key and make a call at 0x403B5D (to 0x402DCF). Once we get inside this call, things get a bit more difficult to understand.
There are a lot of shift/adds and references to 6051xx addresses. There is also a call at 0x402E8A that looks like it may be some kind of encryption/decryption function. After that call, there are a few more shift/adds and then a 'call rcx'. We will also notice that there is a check after our call rcx and the encryption/decryption function is called again on both branches. This seems like a good time to fire up the debugger and see if we can figure out whats going on.
Lets load magic in gdb and set a breakpoint at 0x402DCF (the start of the interesting function) and run it. Stepping through the code a few times, we notice that the code at rcx is decrypted (and then encrypted again after use). If the response from this call is 0, then we jump to code that leads to the function at 0x402CC7, which is our badboy 'No soup for you!' message. So it seems we need to make the call to rcx not return 0. Stepping through this code I noticed that the function was calculating a Fibonacci sequence. If the result from the Fibonacci matches one of the calculated values before the call rcx (I need to go back through and see which char it was).
I stepped through this first function a few times and decided to put the calculated Fibonacci number into google and this gave me my first character. I tested it, setting a breakpoint at the 'test rax, rax, after the 'call rcx' and it worked. Stepping through the code some more we will land at a 'cmp rax, rdx' (after setting rdx to 21h (33)) at 0x403044 that appears to be a counter for the number of functions we have to go through. I stepped through a couple more of the rcx functions, but I didnt spend much time studying them. They seemed like fairly simple calculation functions that need to return non-zero. At this point it seems like we might have enough info to brutefore this problem. So lets go ahead and give it a try!
My original plan was to use a tool that I haven't used before such as frida or Angr. I had no experience with either and after briefly reading up on both of them, I opted to try frida. My idea was to hook the function at rcx (like here), check its return value, and retry if it was 0. But, since rcx was computed dynamically, I couldn't set a breakpoint on an unknown address in frida (or at least I didnt know how). While talking this issue out on the Reverse Engineering Discord, I came to the conclusion that I could probably do a little 'brute-force injection' and code my bruteforcer in a code cave in the file itself. This is by no means a new idea (originally coined 'Kwazy Webbit style'), it seemed like a perfect solution.
Although I had not done this on linux or in a 64-bit environment before, I didn't expect either one to cause any issues. Looking at the code again in Ida, it looks like there is probably enough room in our 'No soup' branch to patch up our loader.
I started my patch at file offset 0x2F0C, after the good boy check. I used hiew to edit the binary. I do not have my original code, but it looked something like this:
0x402F06 call rcx
0x402F08 test rax, rax
0x402F0A jnz 0x402F70 ; passed this section, on to the next one
0x402F0C mov al, dword ptr [rdi] ; move current char to al
0x402Fxx inc al ; next char
0x402Fxx cmp al, 0x80 ; out of ascii charset
0x402Fxx ja somethingWrong
0x402Fxx mov dword ptr [rdi], al ; save new char
0x402Fxx jmp 0x402E8F ; try again. jump to right the decryption function
0x402Fxx nop ; breakpoint here
0x402Fxx int 3
I set breakpoints at 0x402F70 and at my 'somthingWrong' label so I could track progress and errors. This worked for the first function, and possibly a couple more (may go back and double check), but then it failed and hit my breakpoint at somethingWrong. I lazily looked for some reasons for the failures. I then patched the binary to run through all functions just so I could see how many the bruteforcer passed (I think it was 7 or 8 the first time through). I was also able to guess the key size by looking at the (although incorrectly decrypte) string. I then started looking through the other functions to see why they didnt pass. Here are a few things I tried to resolve the issue, before I decided to start really digging in to the functions.
- Added code for 2 chars (used ax instead of al). To account functions that had 2 char keys.
- Added code for 3 chars...
- Push rdi/rcx before call rcx, pop afterwards, just in case one of the functions wasn't restoring them
When none of those solutions completely solved the issue, I finally looked at the function to find the uninitialized variable in [rbp-45] that needed to be zeroed before making the next attempt. I also had some issues with the binary rewriting itself. Leaving breakpoints in the code and/or forcing the binary to accept my incorrect solutions caused the file to re-write itself incorrectly. Once I discovered that, I downloaded a fresh copy of the binary, made my new patch, and ran the file.
Below is the commented IDA disassembly. You can see the error checks that I inserted to try to track down the issue that I was having related to the static variable (in [rbp-45] in the one function) not being zeroed. Youll also notice I zero [rbp-55], this is because of me saving rcx and rdi before the 'call rcx'.
My bruteforcer increases the hex value of the characters in the string we enter, stepping through the Ascii char set. Entering a string of 69 space characters (0x20h), will allow the program to check the whole char set. Running the patched binary will and entering 69 spaces as our first key will shortly (after a few seconds) display the 'Challenge 2/666. Enter key:' message pops up. Success! Now we just need to enter our string of 69 spaces 665 more times.
While copy/pasting our 69 space string, 666 times, is not very difficult, it is boring and time comsuming. Heres a short python script I wrote to run the binary and enter our pass 666 times:
bf = pexpect.spawn('./magic')
bf.logfile = sys.stdout
bf.logfile_send = sys.stdout
for i in range(0, 666):
index = bf.expect ([':', pexpect.EOF])
if index == 0:
bf.sendline (' ' * 69) // key is set to 69 spaces.
elif index == 1:
print "eof:", bf.before," after:", bf.after
print("Exception was thrown")
Running our python script and waiting about 20 minutes will give us what we are looking for:
I wrote up this solution because it was a bit different than most of the others that I had seen (I saw write-ups using frida and Angr, so next time I will know how to properly use them). Although, I did see that celophi solved it using the same method. I only completed 8 out of the 12 challenges but I had fun and learned a lot. Looking forward to next year!
You can send any questions or comments to me or track me down in the Reverse Engineering Discord, on EFnet in #cracking4newbies, or on Twitter. Thanks to majorkebab for helping me get the words to come out right and helping clean up the python a bit.