<-- Flare-On 2015 Index / FLARE-On 2015 Challenge #2 
1
FLARE-On 2015 Challenge #2

Date: Aug 7, 2015

CHALLENGE MATERIALS:

filename:    very_success    DOWNLOAD
md5d88dafdaefe27e7083ef16d241187d31
size2 k (1,536 bytes)
typeWin32 Console App
Original FLARE AuthorNick Harbour
 
tool:    OllyDbg 2.01 / Debugger    Visit Website
tool:    Hex Editor
tool:    Your favorite C/C++ compiler

SUMMARY:
This is a modified version of the challenge #1. Everything is the same except the encryption algorithm is more involved.

FIRST LAUNCH:
A hex dump of the first few bytes of the supplied file reveals that it is a Windows PE executable image. A PE executable begins with the initial DOS header "MZ" sequence followed by the sequence "PE" usually within the same screenfull of information. Renaming the file to very_success.exe, allows us to execute it for the first time:

Flare-On 2015 Challenge #2 - First Run

RUNNING APP UNDER DEBUGGER:
Just as you did with Challenge #1, fire up the executable under OllyDbg.

Note: While this executable has the same size as challenge #1, it has considerably more code packed into the same area previously padded with zeros to keep the code section a multiple of 0x1000 bytes (the PE section alignment).

This module's entry point has been modified to 4010DF and you should be there at a breakpoint on a CALL instruction. All of the functionality for the app occurs within this CALL branch, so if you step over it, you'll miss it all. Instead, press F7 to step-into the CALL instruction and you should find yourself at the original entry point 401000 of challenge #1. This extra CALL has no purpose, because the return address it saves on the stack is immediately thrown away at the instruction 401000, so the program has the same effect as if the entry point remained at 401000. This was probably thrown in to trip up newbies that might not know the difference between step-into and step-over debugger commands. Since a CALL instruction will normally return just like a function does, step-over tells the debugger you don't want to step through any instructions within the CALL, so execute the entire CALL until the called code returns and pause on the instruction following the CALL. With step-into, you tell the debugger you want to branch-within the CALLed address to execute those instructions individually.

Everything else we see sofar looks surprisingly similar to challenge #1 with the calls to GetStdHandle(), WriteFile() and ReadFile() to output the prompt and input the password. Use the F8 key to step-over all of these instructions. As before when you step past ReadFile(), you'll need to switch to the debugged console Window to type in something unique and memorable for the password (so when you see it in memory, it won't blend in with what else might be there).

Flare-On 2015 Challenge #2 - Olly Entry Point

Now this is where this app differs from challenge #1. At location 40104C, we begin pushing 6 arguments on the stack in preparation for calling the routine at 401084, with the 2nd to last PUSH being a pointer to the buffer containing the password we just typed in. Like a typical function call, this function returns a boolean result in the EAX register that is used to determine whether the password was correct or not. If we only cared about making this program think it always received the correct password (simulating a program that thinks you purchased a valid license when you did not), we could easily change the JZ instruction at 401069 to two NOP instructions (that do nothing) and we'd be done. Since we actually need to discover the correct password, we need to dig into the internals of the validation algorithm just as if we might be making our own keygen. Using F7 or F8, advance to the CALL instruction at 40105F and then use F7 to step-into it so you are inside the function at 401084.

Flare-On 2015 Challenge #2 - Olly About to Call Input Handler

SIFTING THROUGH THE ALGORITHM:
Deciphering this function is a great exercise if you want to practice your assembly language skills. Have your Intel Instruction Set reference handy. One technique I like to use is to make a pass over the code in question (in this case, the entire function at least down to the LOOP which encompasses the algorithm). While making this pass, add comments on the far left. Sometimes its useful to step over instructions in the debugger especially when dealing with flags, reading from arbitrary locations on the stack as well as instructions you aren't sure what they do so you can double check your assertions are correct. Now go through the code with the comments and turn it in to pseudo code, doing as many passes as necessary until you distill the algorithm to its essence. Or, at least until you simplify it enough to make sense of it.

There is a lot going on in this function, and the author certainly succeeded in making this function consume time and effort of a potential reverse engineer. This is in hopes that you will give up. Amongst the "junk" instructions (the net effect is that they do nothing or ultimately cancel themselves out adding to the complexity of understanding the algorithm) are simple operations that broken into more instructions than necessary and those instructions are spread out between other instructions.

Here is the function code, with a couple comments to help you along:

00401084 PUSH EBP ;boilerplate stack frame setup 00401085 MOV EBP, ESP 00401087 SUB ESP, 0 ;does nothing 0040108A PUSH EDI ;backup EDI and ESI pointers 0040108B PUSH ESI ; 0040108C XOR EBX, EBX ;EBX = 0 0040108E MOV ECX, 25 00401093 CMP DWORD PTR SS:[EBP+10], ECX ;is input password length (including CRLF) correct? 00401096 JL SHORT 004010D7 ;if not, immediately jump to error 00401098 MOV ESI, DWORD PTR SS:[EBP+0C] 0040109B MOV EDI, DWORD PTR SS:[EBP+8] 0040109E LEA EDI, [ECX+EDI-1] ;point at end of encrypted password buffer; two clues? 004010A1 NOP 004010A2 MOV DX, BX ;BX is our running "sum" value, which is unnecessarily moved 004010A5 AND DX, 0003 ; between DX - only keep the lower 2 bits (values 0-3) 004010A9 MOV AX, 1C7 ;this value is special (AH = 1, AL=C7) 004010AD PUSH EAX ;get the C7 value on the stack (for later) 004010AE SAHF ;load the flags register with AH (i.e. set the carry) 004010AF LODS BYTE PTR DS:[ESI] ;AL = next user input char 004010B0 PUSHFD ;this might look like junk, but we're preserving the carry flag 004010B1 XOR AL, BYTE PTR SS:[ESP+4] ;XOR by the C7 value stuffed on the stack earlier 004010B5 XCHG DL, CL 004010B7 ROL AH, CL ;a roundabout left-shift by remnants of running sum (ah becomes either a 1,2,4 or 8) 004010B9 POPFD ;restore flags above (remember the carry flag?) 004010BA ADC AL, AH ;AL = AL+AH+1 (ADC = add with carry / carry flag ALWAYS set!) 004010BC XCHG DL, CL ; ^^^AL now contains encrypted user input char 004010BE XOR EDX, EDX 004010C0 AND EAX, 000000FF ;zero out everything in EAX except encrypted byte AL 004010C5 ADD BX, AX ;BX is somewhat of a running sum of encrypted byte 004010C8 SCAS BYTE PTR ES:[EDI] ;roundabout way of performing a CMP, incrementing EDI too 004010C9 CMOVNE CX, DX ;roundabout way of zeroing CX if enc byte doesn't match 004010CD POP EAX 004010CE JECXZ SHORT 004010D7 ;if we didn't match enc byte, jump to failure branch 004010D0 SUB EDI, 2 ;EDI is actually counting backwards by 1; subtracting 2 offsets 004010D3 LOOP SHORT 004010A2 ; ^^^the fact that the SCAS above added 1 004010D5 JMP SHORT 004010D9 004010D7 XOR EAX, EAX 004010D9 POP ESI 004010DA POP EDI 004010DB MOV ESP, EBP 004010DD POP EBP 004010DE RETN

My distillation of this algorithm consists of both facts and pseudocode derived from the instructions:
-EDI initially points to the END of the encrypted password buffer and goes backwards for each loop iteration
 (the encrypted password is actually backwards in memory)
-the encrypted password is 37 bytes
-just before we reach the LOOP instruction, we compare an encrypted input character with our encrypted
 password character, so there is a 1:1 correlation; the plaintext password should also be 37 bytes

PSEUDOCODE:

//runningSum adds a bit of randomness to the encryption so its not plain XOR (a salt)
runningSum = 0
do
{
    runningSum &= 3 //only keep lower 2 bits of our running sum (BX and DX are used for this)
    encByte (AL) = (inByte XOR C7) + (1 << runningSum) + 1
    runningSum += encByte

    go to next encPassChar (backwards in memory)
    go to next inByte (forwards in memory)

} while (have_input_bytes)
SAVE ENCRYPTED KEY TO FILE:
Using the step-over function in the debugger, advance to the LEA instruction at 40109E. EDI will point to the base address of the key buffer. Right-click the address next to "EDI" in the register window to the right and select "Follow in Dump". In the dump Window, if the heading displays "ASCII dump", I like to click the heading until it reads "Hex dump". When the dump window displays hex values, I find them easier to select. Select these values with the mouse (37 bytes total) and press CTRL+Insert (or Right-Click values and select "Edit" -> "Binary copy" to copy them to the clipboard. Now using your hex editor, save these bytes into a binary file, such as password.bin. If you need a refresher on how to do this, go to the "EXTRACT ENCRYPTED PASSWORD INTO SEPARATE FILE" section from challenge #1.

CRACKING THE PASSWORD:
Note that the algorithm in the app only encrypts input characters to compare against the encrypted password in memory. This can't be used directly to decrypt the password because we're not dealing with a symmetric algorithm. In this case, decrypting the password will require reversing the algorithm. Since the encryption algorithm is basically:
runningSum &= 3
encByte (AL) = (inByte XOR C7) + (1 << runningSum) + 1
runningSum += encByte
Our decryption algorithm would be:
runningSum &= 3
plainTextByte = (encByte - (1 << runningSum) - 1) XOR C7
runningSum += encByte
Sometimes it is tricky to figure out which steps to reverse and which ones to keep the same when turning an encryption algorithm into a decryption one. The only thing being reversed here is the addition operations and the when we perform the XOR (the XOR needs to happen last). I set up the encryption algorithm equation and solved for plainTextByte just like in high-school algebra to arrive at the decryption sequence.

I then wrote a C++ function that loads password.bin, performs the decryption, and dumps the result to the console. The only dependency is the standard C library so it shouldn't need many modifications to get running on your favorite compiler (perhaps some typedefs for byte and word, plus include <io.h>):

// // flare2015crackme2_algo() - solution to crackme2 rather than brute // void flare2015crackme2_algo(void) { //open file const char* pszFile = "password.bin"; FILE* pFile = fopen(pszFile,"rb"); if (!pFile) { printf(TEXT("ERROR: unable to load file %s\n"),pszFile); } else { //get file size under Windows / under linux, use this instead: // struct stat fileinfo; filesize_t uSize; if (-1 != fstat(fileno(pFile),&fileinfo) uSize = (filesize_t)fileinfo.st_size; DWORD uSizeHi = 0; DWORD uSize = GetFileSize((HANDLE)_get_osfhandle(_fileno(pFile)),&uSizeHi); if (INVALID_FILE_SIZE == uSize) { printf("ERROR: GetFileSize() failed; lasterr=%u\n",GetLastError()); uSize = 0; } //validate size if (!uSize) { printf("ERROR: encrypted bytes file cannot be empty\n"); } else if (uSizeHi) { printf("ERROR: encrypted bytes file is too large\n"); } else { //allocate buffer for encrypted bytes byte* pBuffer = new byte[uSize]; if (!pBuffer) { printf("ERROR: failed to allocate buffer %u bytes\n",uSize); } else { //fill the buffer with the contents of the file size_t uBytesRead = fread(pBuffer,1,uSize,pFile); if (uBytesRead != uSize) { printf("ERROR: tried to read %u bytes but instead read %u\n",uSize,uBytesRead); } else { printf("successfully loaded buffer with %u bytes from %s\n",uSize,pszFile); fputs("decrypted key is: ",stdout); // // DECRYPTION ROUTINE // //loop backwards through encrypted bytes byte chPlainText = 0; byte* p = pBuffer + uSize; //pointing one past end of buffer word uSum = 0; do { --p; //calculate shift value uSum = uSum&3; byte uShiftValue = (byte)((1 << (byte)uSum) + 1); //subtract this from encryptyed val allowing overflow/wrap chPlainText = (*p - uShiftValue); chPlainText = chPlainText ^ 0xC7; uSum = uSum + (word)*p; putchar(chPlainText); } while (p>pBuffer); //exit after we're at base of buffer fputs("\n",stdout); } //cleanup buffer delete[] pBuffer; pBuffer = NULL; } //buffer allocated } //size of file OK //cleanup file fclose(pFile); pFile = NULL; } //file opened successfully } //flare2015crackme2_algo()

Running the function on our saved key results in the password "a_Little_b1t_harder_plez@flare-on.com", which we double-check by plugging it back into the app. Success!

Flare-On 2015 Challenge #2 - Cracking the Password

ALTERNATIVE CRACKING METHOD: BRUTE FORCING:
I have an admission to make. When I originally encountered the encryption function above and started to make some sense out of it, I realized it could be easily brute forced. For me, this was less effort and time than trying to understand it. It wasn't until after the contest was finished that I came back to this crackme to understand the algorithm when writing this tutorial. This illustrates up an important concept in reverse engineering. If you can bypass security with a shortcut, why not take it - at least while the clock is ticking?

I found if we patch the function's length check at the top so it is skipped, we have the ability to input passwords with as many characters as we want and we can get confirmation on the correctness of each character position in sequence. This turns cracking a 37 character password from computationally infeasible (for a secure algorithm) to linear. Since we can safely assume that each character of the password consists of a printable ASCII character, that's only 95 tries per character position (126 is last_printable minus 32 control codes +1). Therefore, a 37 character password can be broken in AT MOST 3,515 tries (before you can blink an eye). Heck with an hour to kill, you could even do it from the command line manually: Start with one character and keep trying characters until you get "SUCCESS". For the second character, use the verified 1st character followed by a guess for the second character. Repeat until you reach the "@" symbol and then you can guess the final part of the password is "flare-on.com".

Here are the modifications to make the app susceptible to brute forcing:

0040108E MOV ECX, DWORD PTR SS:[ARG.3] ;set ECX = input password length 00401091 DEC ECX ;now subtract 2 from ECX 00401092 DEC ECX ; so that it excludes the CR LF 00401093 NOP ; 00401094 NOP ;NOP out the extra space this freed up 00401095 NOP ; 00401096 NOP 00401097 NOP

0040109E LEA EDI, [EDI+24] ;hard code pointing at the end of the password buffer (37 bytes) 004010A1 NOP

I wasn't going to brute force this app manually, so I wrote a small C++ program with the raw bytes of the entire modified function embedded in an array (from 401084 to 4010DE). I also hardcoded another array containing the encrypted password buffer. The program then repeatedly invoked the validation function in a loop. Since the function handily returns SUCCESS or FAILURE via EAX, the program can easily loop through characters until it gets a success before advancing onto the next character position.

Although it might seem like more work than understanding the algorithm, it really wasn't. I had the password cracked in 30 minutes. When I later went back to understand the algorithm, I easily spent more time working on a decryptor. For speed of challenge completion, I feel like the brute force method was best for me. Each situation is different and your mileage may vary. The judgment call you make will be based on your own skills as there is no "one" correct way to crack software.

The source code for brute forcing program is HERE.
The output of the program is can be viewed HERE (cracked in 2,505 tries).

The problem with this program is that it was only useful for this particular challenge. With this in mind, I took a break from FLARE and wrote shelljmp. With shelljmp, I could simply store the function being cracked and any other buffers (such as the encrypted password) in their own binary files and control the brute forcing from the command line. If you are interested, download the shelljmp sample, which helps describe a real-world use case. It contains the modified function shellcode (described above), the encrypted password buffer and a batch file that invokes the tool so the function being cracked receives all the parameters it expects. You can plug-in different passwords and see the results in the register dump.
NOTE: I never needed shelljmp for the remaining challenges.

CONCLUSION:
The official solution used IDA Pro to statically analyze the file as with Challenge #1. The author also offered a brute forcing IDA Python script if you did not deduce the "inverse" function to decrypt the key.

E-MAIL RESPONSE:
Response from a_Little_b1t_harder_plez@flare-on.com:
Subject: FLARE-On Challenge #2 Completed! From: a_Little_b1t_harder_plez@flare-on.com To: <HIDDEN> Date: Fri, 07 Aug 2015 13:31:42 -0400 Great job, you're really knocking these out! Here's the next binary for your goaty enjoyment. The password to the zip archive is "flare" again. Keep up the good work, and good luck! -FLARE attachment_filename="3BD127AEDB12472EB288DAAFDEE76953.zip"

<< Flare-On 2015 Index  --  Go on to Challenge #3 >>

 1:1