All roads lead to Rome, but even more passwords lead to the target: The case for craxploitmes.

How many roads lead to Rome?

In this article, I demonstrate the use of buffer overflow as a technique for solving (at least some) crackmes in the 32-bit x86 architecture. The prevalence of protection mechanisms such as Data Execution Protection (DEP) and Address Space Layout Randomization (ASLR) renders this technique largely inapplicable in the x86_64 architecture, but the matter is still a worthy exercise in reverse engineering. 

The prototype of challenge addressed here is akin to this source code, whereby the comparison between user's input and a hardcoded string precludes the execution of a supposedly inaccessible function. Since the opcodes in an executable will significantly vary based on the operating system and the compiler (and of their release versions, and settings), in this illustration I will apply the buffer overflow technique to the readily available crackme0x00. The platform used for this reverse engineering analysis is Windows XP.

In this simple crackme, user's input is compared with the hardcoded string "250382" (without double quotes). If hardcode and user's input are equal, message "Password OK :)" is displayed on the screen. At first glance, it appears that "250382" is the only input leading to the successful outcome. That is not the case, though, since it is possible to enter other strings so as to control what the program should do upon retrieving user's input. Moreover, where buffer size permits, it is possible to make a clean exit from the program  rather than making the executable crash and burn.

Indeed, a copy/paste of the output of this Perl command will serve as user's input or "shellcode":

perl -e "print \"\x8B\xEC\x58\x58\x58\xB8\x27\x12\x40\x80\xD1\xE0\xD1\xE8\x50\x50\x66\xB8\x41\x40\x50\x50\x66\xB8\x91\x13\xFF\xE0\x60\xFF\x22\""

The label of "shellcode" is an overstatement because strictly speaking the opcodes do not lead to an OS shell whereby the user can run any arbitrary commands. However, as discussed below, the resulting opcodes satisfy the various constraints that are needed for a clean execution.

The length of this quasi-shellcode suffices to overwrite the return address 401227h, which is the address that was pushed into the stack by the opcode at address 401222h (CALL 401310h). In this crackme, that is the only area of memory through which the user is able to control the EIP register. In fact, the last three bytes of the quasi-shellcode replace the return address with 22FF60h. That redirects the program to run the opcodes written into the stack by means of the quasi-shellcode.

Upon returning from scanf, the quasi-shellcode is validated against the hardcoded string 250382 (and validation obviously fails), but thanks to the overwriting of the return address the rest of quasi-shellcode gets the attention it always wished for: The address awaiting RETN is 22FF60h.

The new opcodes as read from the stack are shown in the following image:

There are multiple constraints that make the writing of shellcode challenging. Creativity and optimization are indispensable if one aims at flawless execution:

1. The LEAVE opcode at 40139Bh spells trouble for shellcode writing because of its impact on EBP and/or ESP register(s). Hence the need to preserve and manage EBP in the quasi-shellcode.
2. The purpose for having three consecutive POP EAX is to set the ESP register to the value we need for subsequent parameters and execution/return addresses. Had this step been performed first, the LEAVE opcode would lead to runtime error. Furthermore, both the buffer size and the well-known constraint that no zeroes are allowed in a buffer (henceforth the "zero-restriction") eliminate the option of modifying ESP through opcodes such as ADD, SUB, MOV.
3. To allow for a clean termination of process, the quasi-shellcode needs to write into the stack a proper return address. Hence the need for the opcode at 22FF65h. To overcome the zero-restriction, the most significant bit of EAX is set [to 1] and eliminated by means of the two subsequent Shift opcodes.
4. PUSH EAX, with EAX now holding the return address 401227h, ensures a clean termination of the program.
5. The address of message "Password OK :)" is pushed into the stack in preparation for the call to printf.
6. EAX is modified to point to the address where the crackme calls printf. Due to [buffer] size and stack constraints, printf is executed by means of the JMP opcode rather than by CALL.

Upon execution of printf, the program flow resumes in the original crackme routine. Hence the importance of setting the return address 401227h properly.

One alternative quasi-shellcode is to directly or indirectly execute printf twice with the benign message (for instance, to outweigh the prior display of message "Invalid Password!"). However, due to size constraints, that would be at the expense of a clean termination of the process.

The structure of this quasi-shellcode obviously allows for several minor or trivial variations while still satisfying all the constraints and even the ambition for a clean exit. Some variations are:

• Not all POP/PUSH instructions need to involve the same register, since many of these opcodes are entered solely for purposes of controlling ESP.
• The quasi-shellcode could use as workhorse some general purpose register other than EAX.
• Instead of 401227h, other possible return addresses 401229h, 40122Fh, 401232h, or even the address with the instruction JMP DWORD PTR DS:[kernel32.ExitProcess].
• The SHL opcode could be replaced by a ROL. The very next opcode, SHR, disappears the troubling bit anyway.
• This quasi-shellcode is not even optimal because there was no need to increase ESP by 0Ch and PUSH twice each offset. It is possible to save three bytes by omitting one POP instruction, one PUSH with the message address, and one PUSH with the return address.
• The previous idea allows for replacing the pair of Shift opcodes (see point 3) with the instruction AND EAX,7FFFFFFFh or any number that resets EAX's most significant byte.
• In relation to the previous two items, the AND opcode in combination with the MOV opcode at 22FF65h open a variety of variations as long as these lead to the setting of the desired return address.

Thus, although at first glance one and only one unique password could lead to the printing of the benign message, the technique of buffer overflow leads to literally millions of valid "passwords" while still preserving a normal termination of the program.

Iñaki Viggers