Intro to Reverse Engineering-Part 2

Intro to Reverse Engineering - Part 2

In Part 1, Intro to Reverse Engineering - No Assembly Required, we extended the series of coding articles for non-programmers with an area of high interest in the infosec community. We're proud to be able to bring you the highly anticipated follow-up complete with screen shots, sample code and applications. This one is long and detailed, so strap yourselves in for some great educational content.

This paper is designed to outline some essential reverse engineering concepts, tools and techniques - primarily, debuggers and using the debugging process to reverse engineer application functions and algorithms. It is assumed you have knowledge of basic assembly and C programming. An understanding of Win32 programming and API calls is also helpful. This tutorial does not necessarily have to be read in order (although it is strongly advised), as some sections do not contain information that directly relates to subsequent sections. However, if you begin skipping around and find that you have trouble understanding a concept, or feel like you missed an explanation, it would be best to go back to previous sections of the tutorial and read them first.  

del.icio.us

Discuss in Forums (11)

Before we begin... 

The Windows platform was chosen as the focus of this paper. Because of Window's wide-spread use and its closed-source nature, RCE is performed most often on Windows applications. This tutorial is time-consuming and intense, so let's do a quick overview of the topics that will be covered:

1. Introduction to debuggers, specifically, OllyDbg.
2. Finding the beginning of the actual code (i.e., the main() function as opposed to code generated automatically by the compiler).
3. Identifying how source code is translated into assembly instructions.
4. Locating specific functions and API calls.
5. Identifying and un-packing basic packers.
6. Real-time debugging and patching.
7. Serial fishing.
8. Self-key generation.
9. Translating disassembled functions and algorithms into higher-level languages (aka, creating key-generation programs the right way).
10.  Identifying and exploiting stack-based buffer overflows in closed source programs.

Helpful Resources

There are two directories inside the tutorial's zip file: apps, and source. The apps folder contains the pre-compiled programs we will be working with, and the source folder contains the applicable source code for all programs which I have written for this tutorial.

Several tools will be used throughout this tutorial. While it is helpful to have them all, it is really only necessary to have OllyDbg, as you are expected to be tracing through the example programs as they are being presented in the text; this will facilitate your understanding of the text and code.

1. Olly Debugger - For debugging and disassembly.

2. OllyDump - Plugin for Olly.

3. PeID - For identifying packers/encryptors.

4. Dev-C++ - For compiling source with GCC.

5. ActiveState Perl - For creating some exploit code.

Index

1. A 30-Second Intro to OllyDbg - Getting to Know Your Debugger

A quick one page introduction to the basic commands for using Olly.

2. Finding Main() - Compiler Code vs Developer Code

Here we look at some different ways to find the main() function, and also examine the differences between program entry points when they are compiled by different compilers.

3. EXE Patching

How to temporarily modify assembly instructions in Olly, as well as saving them permanently.

4. Intro to Keygens and Un-packing

Learn some basics about executable packers, do some more patching, and create our first keygen.

5. Reversing Key Generation Algorithms - Writing a Real Key Generator

Here we completely reverse a key-validation algorithm, and write a full-fledged key generator in C.

6. Discovering and Exploiting Buffer Overflows

In the final section of this tutorial, we analyze a program for BOF vulnerabilities, and write some exploit code that allows us to take control of the EIP.

A 30-Second Intro to OllyDbg - Getting to Know Your Debugger

Knowing what tools to use, and how to use them, is critical when reversing software. The tool that will most commonly be used throughout this paper is OllyDbg, a popular Win32 debugger. Olly has many plug-ins and advanced features, but we will learn just the essential commands here.

For those unfamiliar, a debugger allows you to view the assembly instructions of a program as they execute: you can set breakpoints on specific instructions to pause execution, single step through the program one instruction at a time, or just let the program run normally. To get a feel for this, open up test.exe in Olly:

The highlighted instruction ('PUSH EBP') is the entry point of the program. There are four main windows in Olly: the code window in the center, the register window on the right, the stack window in the bottom right hand  corner and the memory dump window in the bottom left corner.

Instructions and data in the code and memory dump windows can be manipulated by highlighting the desired data and pressing the space bar. Stack and register contents can be modified by right clicking them and selecting 'Modify'. To single step one instruction at a time, press the F8 key: you will see that the highlighted line goes to the next instruction, 'MOV EBP,ESP'. If you want to step into a function call, press the F7 key. The F2 key allows you to set a breakpoint on an instruction, and F9 runs the program normally (still 'inside' of Olly though); to pause the program, press F12. The use of these functions will become clearer as we work through some examples; for now, play around with them, and make note of how each instruction manipulates the stack, registers, and memory.

  

Finding Main() - Compiler Code vs Developer Code

If you look at the code at the EP of test.exe and compare it with the source code in test.c, you'll notice that they look nothing alike. The code immediately after the EP has several function calls to APIs like __set_app_type and atexit. That is because when source code is compiled, the compiler adds some code to the beginning of the program in order to properly initialize the application before executing the code written by the programmer. Different compilers will do drastically different things, so you can usually identify what compiler was used as soon as you see the EP. This particular program was compiled with Dev-C++ which uses the GCC compiler; however, in the vast majority of cases, you don't care much about the compiler code - you want to see what the programmer wrote. So, let's see how we can identify when the switch from compiler code to developer code is made.

Press F8 a several times to single step through the first few instructions, and you will notice that after you execute the 'CALL test.00401100' instruction, the program runs normally. That is because the main program loop (or a call leading to the main program loop) is located at 0041100. Because we pressed F8 to execute the call instruction, Olly executed everything inside that call instruction, and because our program waits for user input before returning from the main loop, the call instruction has not completed yet. To remedy this, restart the program in Olly (Ctl+F2), press F8 until the next instruction to be executed is 'CALL test.00401100'; this time, press F7 to step into the instruction, and you will be at the first instruction of the function at 00401100:

Let's take a moment to examine this function before executing anything...calls to SetUnhandledExceptionFilter and __getmainargs? This still doesn't look like our main function, so the main function is probably called from inside of this one. Scroll down in the code window until you see this code:

CALL test.00401290

MOV EBX,EAX

CALL <JMP.&msvcrt._cexit>

MOV DWORD PTR SS:[ESP],EBX

CALL <JMP.&KERNEL32.ExitProcess

Notice there is a call to _cexit followed by a jump to ExitProcess. Well, if ExitProcess is being called, then the call to our main function has to occur before this. Most of the function calls are located in msvcrt.dll (the '&msvcrt' before the function name is a dead give away), but look at the call just before the call to _cexit ('CALL test.00401290'). It is referenced by a memory address rather than an API function name. Select the 'CALL test.00401290' instruction and press F2 to set a breakpoint on it. Now, press F9 to let the program run normally; when the code execution reaches the breakpoint the application will pause on it before executing the instruction. When Olly breaks there, press F7 to step into the call. We are now at memory address 00401290, and the function here looks like our main loop - one call to printf(), followed by one call to getchar(), followed by a return:

In general, the compiler code will call the main loop just before a call to _cexit/ExitProcess, so looking for those two functions can help in finding the start of the main function. The Visual C++ compiler code is a bit more complicated, so we will take a look at how that differs from GCC, but first let's examine our main loop while we're here. There is a lot of data moving in and out of EAX just before the call to prinf(), so let's see if we can figure out what's going on.

Press F8 until you arrive at the instruction 'MOV EAX, DWORD PTR DS:[403000]'. This instruction is moving the contents located at the memory address of 00403000 into the EAX register. The very next instruction moves the contents of EAX into a local variable on the stack starting 28 bytes below EBP. Well, let's see what is located at 00403000: select the memory dump window in the lower left hand side and press 'Ctl+G'. Enter '403000' (no quotes) at in the text box and click OK. Starting at address 00403000, we see our text string that is displayed by the printf() function:

Since the EAX register can only hold four bytes at a time, only the first four bytes of our string have been copied into the local variable; the subsequent instructions move the rest of the string into the variable's address space four bytes at a time. Finally, the address of the local variable is loaded into EAX, and EAX and the "%s" string are placed on the stack as arguments to the printf() function.

Why did the program go through all the trouble of copying the string in four byte increments onto the stack, when it could have just referenced the original memory address where the string was located (00403000)? Well, because we told it to. In the source code, test.c, you can see that we declared a variable named 'string', and set it equal to the string we wanted passed to printf(). Since a 32-bit processor can only move 32 bits at a time, it had to copy the string from the data section of memory into the string variable four bytes at a time. If we had made the string variable a pointer, the program would have only needed to copy the 4 byte memory address of where the string was located into the variable (the pointer would then point to address 00403000). This would have required only two mov instructions rather than sixteen; it also would have eliminated the need for the LEA instruction. That's almost a 200% decrease in the number of instructions contained in our main function. Granted, this is a very simple program and CPUs are very fast these days, so no measurable difference is seen by the end user. But it is a good example of how disassembly can be used to further our knowledge of high-level programming and help us to develop more efficient applications.

I mentioned earlier that different compilers will produce different assembly instructions for the same source code. Since VC++ is the most commonly used compiler for Windows applications, I've compiled the code in test.c using VC++, and saved it as test_vc.exe. Opening test_vc.exe in Olly reveals a vastly different set of assembly instructions that we saw in test.exe:

You may have been wondering why you received a warning message from Olly that test_vc.exe had an entry point outside of the code section. Without delving too much into the subject of PE (Portable Executable) headers, each Windows program has a PE header which, among other things, identifies which sections of the program contain the code, which sections contain data, etc.

Here, we see that our EP is actually a jump to 00411840, but before we go there, let's take a look at the surrounding jumps. There are a lot of jumps to a lot of different functions, including printf()...right-click the code window and select 'Search for -> All intermodular calls'. This brings up a window that shows all of the function calls in test_vc.exe that are external to the program (i.e., API functions). Comparing the list of functions here with the list of jumps in the code window, we see that there is a jump for nearly every inter-modular function, as well as several functions that are listed only by address (these are internal to the program). The way this works is, whenever a function call is made within the program, instead of calling the memory address where the actual function is located, it calls the memory address where the jump to the function is located. For example, the jump to printf() is located at 0041118B, so wherever there is a call to printf() within the program, it will actually call 0041118B, which in turn jumps to the actual location of the printf() function. The advantage of this is that if you have a function that is called from multiple locations in your code, and the memory address of that function changes, you only have to change where the jump points to, rather than every single call to that function. It should be noted that depending on compiler options that have been set, the EP code may differ, and in fact, you will normally not see an EP that looks like this when debugging a real-world application; however, this was compiled using the default settings for VC++ 2005.

Press F8 to jump to the first function; this is a very short function which calls two functions then returns, so our main function must be somewhere inside one of those function calls:

PUSH EBP

MOV EBP,ESP

CALL test_vc.00411050

CALL test_vc.00411860

POP EBP

RETN

Press F8 until you reach the first function call, then press F7 to step into it. Notice that we are back at the jump table, and that the actual function is located at 00412AB0:

Press F8 again to follow the jump to the actual function. Here we see a lot of calls to functions like GetCurrentProcessID and GetCurrentThreadID, but no calls to any exit functions. The call to the main function is probably not located here, so press F8 until you return from this function, and you will be sitting at the second call which points to 00411860. As before, press F7 to step into it, and notice that it does not take us to the jump table, but rather directly to the function itself. Scrolling down in the function code, we see a call to exit(), and a few instructions above that a call to an internal function located at 00411136:

Set a breakpoint on the function call to 00411136 and press F9 to run the program. When it breaks, press F7 to step into the call; this again takes us to the jump table, so press F8 to get to the start of the function:

Now that looks more like it! There is a reference to our string (or at least part of it), and calls to printf() and getchar(). But getting here was kind of a pain, and there's an easier way. Notice how the call to the main function was made just before calls to exit() and _cexit(), and in the previous program that was compiled with GCC, the call to the main function was located just before a call to _cexit()? And remember how we were able to view all of the inter-modular calls? Well, right click the code window and again select 'Search for -> All intermodular calls':

Hmmm, there are two calls to _cexit() and one to exit(). Double click on the first call to _cexit() and Olly will take you to back to the code window and you will be located at 004118F6, which obviously is a call to _cexit(). Scroll up just a few instructions and there is the call to our main function located at 00411A01.

  

EXE Patching

One of the great functions of a decent debugger is that it allows you to modify instructions and data, and Olly is no exception. patchme.exe is a simple program that prints the text "This is the wrong text!" to the screen, and is very similar to the test.exe program we worked with earlier. The only differences are that no source code is supplied for patchme.exe, and the object of this program is to make it print "This is the right text!". Depending on how the program was coded, there may be several different ways to accomplish this, so let's open it up with Olly and see what we can find.

Once opened in Olly, find the main function for patchme.exe; it should look like this:

As we've seen previously, everything through the two function calls at 004012B0 and 004012B5 is generated by the compiler; the real code starts at 004012BA, where zero is moved into a local variable (we'll call it var1). Next, the memory address 0040301A is moved into another local variable, var2. In the memory dump window, go to the address 0040301A and you will see that it is our "This is the wrong text!" string; so we know that var1 is set equal to zero, and var2 is a pointer to the text string. Next, var1 is compared to 1, and if they are not equal (which we know they aren't), the program jumps down to 004012E5, where var2 is pushed onto the stack and printf() is called.

But look, there are two calls to printf(); because var1 didn't equal 1, the first one was skipped. Looking at the next instruction after the conditional jump (JNZ), we see that the memory address DS:[00402000] is placed into EAX, and then EAX is placed on the stack as an argument to printf(). To find out what is located at DS:[00402000], set a breakpoint on 004012BA (where var1 is set equal to zero), restart the application and press F9 to run it. When Olly breaks at 004012BA, press the space bar to change the assembly code:

Change the 0 to a 1, click 'Assemble' and then 'Cancel' to close the window. Now that we have changed the code to set var1 equal to 1, F8 through the next few instructions and notice that this time, the jump to 004012E5 is not taken. When you get to the 'MOV EAX,DWORD PTR DS:[402000]' instruction, notice that the information bar below the code window indicates that DS:[00402000] is the address 00403000. Take a look at this address in the memory dump window:

Well how about that...the string we want to print ("This is the right text!") is located there, just above the "wrong text" string. So, if var1 is set equal to 1, then the "right text" string is printed...to test this, press F9:

Bingo! Now if we want to permanently patch the program, all we have to do is go back into Olly, right-click the code window, select 'Copy to executable -> All modifications' and click the 'Copy All' button when prompted. Right click inside of the new window that appears and select 'Save File'. Save it as patched.exe, exit Olly, and run the new program - you'll be greeted with the "right text" string.

  

Intro to Keygens and Un-packing 

Writing  Key Generators

Why write a keygen? Because while patching a file is useful, you don't learn nearly as much about reverse engineering than you do when writing a key generator. In many cases it is not desirable to permanently patch an executable, so it is necessary to completely reverse a function or algorithm; writing key generators is good practice in performing in-depth code analysis.

For this part of the tutorial, we will be examining KeygenMe3 by Tanatos, and ArealApp.exe (both included in the apps directory). In KeygenMe3, we will learn how to un-pack a compressed executable, do some serial fishing, and trick the program into becoming its own key generator.

ARealApp is a "keygen-me" program which uses a key generation algorithm that I reversed from a real-world shareware application. For legal purposes I did not want to identify the shareware program, so I wrote ARealApp using the exact same algorithm used in the shareware executable. Here we will completely reverse engineer the algorithm used for key validation, and write our own keygen in C.

Executable Compression & Dumping

Let's focus first on KeygenMe3 first; open it up in Olly, click through any warning messages, and take a look at what we have:

As we saw in part one of this tutorial, most functions begin with a prelude which manipulates the EBP and ESP values accordingly; this program starts out with the PUSHAD instruction which pushes the contents of all the registers onto the stack. This is a sure sign of a packer, usually UPX or ASPack (opening the executable with PEiD does in fact identify this program as being packed with UPX). If you are unfamiliar with packers, they simply compress the executable file so that it takes up less space on the disk, and add a de-compression routine to the beginning of the executable in order to un-compress the program when it is loaded into memory. The basic layout of most of these simple routines is:

PUSHAD

/*de-compression routine here*/

POPAD

JMP OEP

We want to find the jump to the OEP (Original EP) so that we can view the original assembly code; since this jump is made only after the executable code has been decompressed, we will have no trouble viewing it. We could trace through the de-compression routine, but there's an easier way. Notice that the first instruction is PUSHAD (which saves all the register values onto the stack), and the last instruction before jumping to the OEP is POPAD (which restores the previously saved data from the stack to the registers). The routine does this to ensure that the register values will be set up properly for the program; in other words, it doesn't want the original code to have any idea that extra code has been run before arriving at the OEP, because the instructions there are expecting certain values, and wouldn't know how to handle any errors that might result from variations in the register values. This means that the only instruction that will touch the values placed on the stack by PUSHAD is the final POPAD instruction. If we place a hardware breakpoint on those values after they have been pushed, then the next time they are accessed (which will be by the POPAD instruction), we will be sitting at the JMP OEP instruction.

Press F8 to execute the PUSHAD instruction; notice how the value of ESP changes to reflect the fact that new data has been pushed onto the stack:

Right-click the ESP value, and select "Follow in Dump". The memory dump window now shows the values at that address:

The first four bytes are the same bytes located in the EDI register, since it was the last register to be pushed onto the stack by the PUSHAD instruction. Note also that each byte of each register has been pushed in reverse order. Now, select those first four bytes in the dump window, right click and select "Breakpoint -> Hardware, on access -> Word". Press F9 and Olly will break right after those four bytes are accessed by the POPAD instruction:

Press F8 to execute the JMP instruction (this is the jump to the OEP that we were looking for!), and the code should look much more friendly now:

Now that we have let the program un-compress itself, we will save it in its un-compressed state. The easiest way to do this is with the OllyDump plugin. Right click the code window and select "Dump debugged process". In the window that pops up, click 'Dump', and save the file as tknm3_dump.exe:

Olly will correct the entry point address, import function addresses, and anything else that needs to be fixed; run tknm3_dump.exe, and it should run normally.

If you are not planning on permanently modifying a program, it is not necessary to actually save it in its de-compressed form. However, since we will need to make modifications to this executable, this final step was required.

Self-Keygens

Self key generation is the act of patching the target application in such a way that it reveals the correct serial key to the end user. This is most often done by finding the memory address that the calculated correct key is stored at, and replacing the text in the standard "Incorrect serial number" message box with the correct serial number. And that is exactly what we will be doing with tknm3_dump.exe.

But I'm getting ahead of myself. Let's assume that we know nothing of this program (other than the original executable was packed with UPX of course); the first thing we should do is open it up in Olly and run it! We have a dialog box asking for our name and registration key:

Clicking the 'Check' button without entering any information results in a message box telling us to enter a name that is at least three characters long; this is interesting, because it means that the serial is probably generated based on the name entered. So, put in a three character name (I used 'aaa') and click the 'Check' button again. What's this? We get the same error message. In fact, we have to enter a name that is at least four characters long in order to pass this first check - obviously a programming error, and it is always good to note such errors as they may come in useful while disassembling the code (in this case, it doesn't however).

Now that we've entered a valid name, we get another message box telling use we forgot to enter a serial number. So, put in something random like '12345' and click 'Check' again. We now get a "Wrong serial! Try again" message. Now, this message box is obviously the negative result of running our entered serial number through the serial validation algorithm, so if we can find where this message box was called from we can trace back from there and find the algorithm and/or comparison in question. In Olly, press F12 to pause the program, then press Alt+K to view the call stack. Here we see recently called functions, among them, two calls to MessageBox:

The second one, called from 00401172, is the one we are looking for. We know this because anything with very high memory addresses, like 77D8054B, is usually located in a DLL file, and the second message box was called from a memory address that resides inside the target program's memory range. So back in the code window of Olly, press Ctl+G and go to address 00401172:

Interesting, no? A few instructions above the address in question, we see there is a call to GetDlgItemTextA, followed by a call to 0040120D. The return value of 0040120D is compared using a TEST operation, and if EAX is zero, the serial error information is pushed to the message box function; if it is not zero, then the "Registered" text is pushed to the message box function. The function at 0040120D definitely warrants some more investigation, but let's look at a few more things first. If you scroll up a little further, you'll see that our entered serial number is stored at 0040B420, our entered name is located in 0040B1E0, and there is an unknown number (it will be '3825205248' if you have used the name 'aaaa') stored in 0040B300. Now, let's set a breakpoint (F2) at the first argument that is supplied to the GetDlgItemTextA call ('PUSH 32' located at 0040112F), and restart the program in Olly.

Run the program again, supplying the same name and registration key, and click 'Check'. The first item that is pushed is the number 0x32 - this is the maximum size of the string, so we know that our serial can't be more than 50 characters long. The next item that is pushed is the address to store the string in, and you can see that this value is indeed  0040B420, where we found our serial number stored the last time. The other two values are the control ID and dialog box handle, neither of which are important for our purposes. Step through the code until the call to GetDlgItemTextA has been executed. The next three instructions are important: there are two values pushed onto the stack, and then a call to the mysterious function located at 0040120D. Looking at the two values that are pushed, the first is 0040B300 (remember that "strange" string we saw earlier?) and 0040B420, which is the address where our entered registration key is located. Press F7 to trace into the function call.

This is a small function, consisting of a single loop:

First, the unknown string address is moved into EDX, while the address of our serial number is moved into ECX. The value of ESI is pushed onto the stack, and ESI is then set to 1. EDX+1 is then loaded into the EAX register; this is interesting because it means that the first character of the unknown string will NOT be examined. Then, the SECOND byte of our registration key is moved into DL (again, the first character is ignored), and DL and the first character of the unknown string are compared. If they do not match, then the function jumps down to 00401231 where EAX is set to zero, the original value of ESI is restored, and the function returns. However, if they do match, then ESI is incremented, EAX is incremented, and if ESI is not greater than 4, then the function loops back to 0040121E where the next two bytes in each of the strings are are compared with each other. If ESI is greater than 4, then EAX is set to 1, ESI is restored, and the function returns.

If that seemed a little confusing, don't worry, it's just my lack of communication skills; the function is quite simple actually. The relevant pseudo code looks like this:

//EDX points to the unknown string

EDX = *unknown_string

//ECX points to the serial number we entered

ECX = *entered_serial

//ESI is initialized to one

ESI = 1

//EAX points to EDX+1, aka, the unknown string starting at the SECOND byte

EAX = EDX+1

/*this next instruction is just some math to make it easier to reference the unknown_string and the entered_serial...the unknown string is at the memory address stored in EAX, and the entered_serial is at EAX+ECX. Also, since EAX actually points to the second byte of unknown_string, EAC+ECX actually points to the second byte in entered_serial as well. */

ECX = difference between ECX and EDX

//loop four times

while ESI <=  4

            //do the bytes in unkown_string and entered_serial match?

            if (ECX+EAX) == EAX

                        //increase ESI for loop purposes

                        ESI++

                        //increase EAX, aka, look at the next byte in each string

                        EAX++

            else

                        //if they don't match, set return value to 0 and return

                        EAX = 0

                        return

            end

end

//if we've gotten here, then all comparisons were successful, so set return value to 1 and return

EAX = 1

return

To recap, we know the following:

1. If the return value of  0040120D is 0, then we get the bad serial message; else, we get a good serial message.
2. 0040120D compares our entered serial with a string that is located at  0040B300.
3. 0040120D ignores the first byte of both our serial number and the string at  0040B300.
4. Only bytes 2-5 in each string are compared (the loop only runs four times).

So, we can conclude that the valid serial number is located at 0040B300, but only bytes 2-5 are relevant. So, a valid serial has to be at least 5 bytes long; the first byte can be anything we want, but the next four must match with the respective bytes in the string at 0040B300. Note the string value at 0040B300 (I used a name of 'aaaa', so my value is '3825205248'). Restart the program, enter the same name, and for the registration key enter the first five numbers of previously noted value, replacing the first number with whatever you like (in my case I entered '08252'):

Bingo! Now we just need to patch a few instructions in order to turn this program into a handy little key generator for itself.

We know that the registration key is located at 0040B300, so all we have to do is change the memory address pushed to the MessageBox function from 0040A0A4 ("Wrong serial! Try again") to 0040B300 (the correct serial number):

This way, when an incorrect serial number is entered, you will get a message box that shows you the correct serial number:

Save your changes to the executable and the keygen is done!

  

Reversing Key Generation Algorithms - Writing a Real Key Generator

Some people consider the previous keygen project cheating because we didn't actually reverse the key generation algorithm. If our only object was to create a keygen then this is fine, but from a purely RE perspective, they are right. So in this next installment, we will be completely reversing a registration key validation algorithm, and writing a key generator in C. The target application, USP.exe, has been written in C and uses a key-validation algorithm found in the wild (i.e., this was used in an actual shareware program). I have included the source code for both USP and the USP keygen, but don't peek at them until we've disassembled the binaries...that would take all the fun out of it.

First, let's run the USP to see what we have (yes, I was lazy and made it a CLI program). We see it prompts for a user name and a registration key...let's enter some fake credentials, say, 'test' for our name and '12345' for our key. We receive an "Invalid Registration Key!" message - not entirely unexpected. Now let's open USP up in Olly and see if we can find the code that accepts the user name and password, then subsequently validates (or in our case, invalidates) them. Since this is a simple program, we'll start by finding the main function, since there probably aren't too many nested functions we'll have to follow to find what we're looking for. In a real-world application we would probably have to use the trick we learned earlier of pausing the program then examining the call stack to find the section of code we are interested in. We find the main function at 00401380:

Note that the main function uses printf() and gets() to prompt for and retrieve the user name and registration key. Also of note is the function immediately above the main function (at 0040135D) which prints the "Invalid Registration Key!" text, then exits; this is our "bad" function. The gets() function takes one argument: the address to store the retrieved text into. Examining the above code shows that the user name we enter is stored at 004040D0, and the registration key at 004040B0. Strlen() is then called to determine the length of the registration key we entered (we know this, because the address where the registraiton key is stored is passed to the strlen() function), and the value returned is compared to 0x17 (23 in decimal notation). If the value in EAX is equal to 0x17, then a jump to 004013FC is made, but if not, then the function at  0040135D (the "bad" function!) is called. This tells us the first piece of information we need to know about the registration key; it must be exactly 23 characters in length.

The purpose of the rest of the code may not be so obvious when viewed in a dead listing, so let's see what happens when we enter a key of 23 characters in length. Set a breakpoint on 004013FC since we should land here if our key is the correct length, and run the program. Enter some fake credentials again, ensuring that your key is 23 characters long (I used '12345678901234567890123'), and Olly will pause at our breakpoint:

Now, this is interesting; the code is moving one byte of data from the memory address 004040B5 into the EAX register, then comparing that byte to the byte stored at 00402025. Now, we know that the registration key we entered is stored at 004040B0, so these instructions are actually comparing the 6^th byte of our registration key with some other byte at 00402025. Taking a look at the information window just below the code window confirms that the byte pointed to is in fact the 6^th byte of our registration key:

The question is, what is this byte being compared to? Press F8 to execute the MOVZX instruction, and again we can use the information window to see what is stored at 00402025:

Our 6^th byte gets compared to a hyphen, and the following JNZ instruction shows that if they are not equal, then a jump is taken to 004014F3, which happens to be a call to the "bad" function at 0040135D. So we know that our 6^th byte must be a hyphen - but look, this same comparison is performed on bytes 004040BB (the 12^th byte in our registration string) and 004040C1 (the 18^th byte in our registration string). This tells us that every 6^th character in the string must be a hyphen. The registration key format now looks like:

12345-12345-12345-12345

Let's restart the program in Olly and enter in our new registration key ('12345-12345-12345-12345') so that we can pass this validation check as well, and we see that we do. Now we find our selves at 00401435, where two local variables, EBP-C and EBP-4 are set equal to zero before entering a loop which also contains a nested loop:

As you can see, I've added some comments in Olly (this can be done by pressing the semicolon key). We have three local variables here, all integers: var1 and var2 are used to count the number of iterations performed by the primary and nested loops respectively; var3 is incremented each time the nested loop is executed, and based upon the value of var3, the function at 00401290 is called with different arguments. Note that var3 is also incremented each time the primary loop is executed, but only after the if statements.

We can also see that the primary loop is executed 23 times, and the nested loop is executed 5 times and is doing something with the registration key we entered. This is particularly interesting, because we know that a valid registration key is 23 characters long, and that it consists of four sets of 5-character strings, each set being separated by a hyphen. We can assume then, that these loops are either performing some type of calculations on the key as a whole, or on each of the four hyphen-separated strings that compose the key, or both.

To get a better idea of what is going on, let's start single-stepping through the code and see if we can determine what type of calculations it is performing. The first few instructions in the primary loop serve only to check if var1 is greater than 22 and to set var2 equal to zero. The nested loop is rather interesting however; here is another screenshot where I have added some more notes regarding the nested loop:

There doesn't seem to be any data located at 00404090 (yet), but we know that the registration key we entered is stored at 004040B0. We also know that var2 and var3 are initialized to zero, and incremented each time the nested loop executes, and that the nested loop loops five times. Here is some pseudo code to help clear things up:

var2 = 0;

5.times do

            //move one byte from our registration key into a variable located at 00404090

            00404090[var2] = 004040B0[var3];

            //increment var2 and var3 so that the above instruction will point to the next byte in each string

            var2++;

            var3++;

end

So, the first time the nested loop executes, it places the first five characters (i.e., the first of the hyphen-separated sets) of our registration key into a variable at 00404090. Each time this loop is called var2 is set to zero, so the values stored in 00404090 from the previous loop iteration will be overwritten each time the loop is called. Remember that we previously noted how var3 was also incremented once after the nested loop finishes executing? That is because the program wants to skip the hyphens in our registration string. For example, let's say that our registration key is '12345-67890-ABCDE-FGHIJ'. The first time the nested loop executes, it will copy '12345' into the variable at 00404090, the second time it is called, it will copy '67890' into 00404090, etc.

It appears that the program examines each 5-character set in our registration key individually, so let's try and find out what it does with them. The rest of the primary loop consists of if statements, comparing the value of var3 (which indicates how many characters of our registration key have been copied into 00404090) to several hard-coded values:

Again, let's create some pseudo code to help understand what is going on:

if var3 == 5

func_at_00401290(43,string_at_00404090);

else if var3 == 11

func_at_00401290(23,string_at_00404090);

else if var3 == 17

func_at_00401290(17,string_at_00404090);

else

func_at_00401290(53,string_at_00404090);

endif

var3++;

var1++;

For each if statement, the function located at 00401290 is called, and takes two parameters: an integer value, and the address of the variable that contains one of the hyphen-separated strings that make up our registration key. However, depending on which of those hyphen-separated strings is currently located at 00404090, a different integer value is passed to the function at 00401290. For the first string set, the value 43 is pass; for the second, 23, the third, 17, and for the fourth and final set , 53.

Once this primary loop is complete, the code immediately prints the "Thank you for registering" message; but, we know that we do not get that message when we enter an invalid registration key, so something is happening in the function at 00401290 that prevents the loop from completing. Put a breakpoint on the first call to 00401290 and press F9. When Olly breaks, take a quick look at the stack values that have been pushed; you will see the value 0x2B, and the memory address 00404090, which contains the first five characters of our registration key (from here out this will be simply called "the string"). Press F7 to step into the function call:

Again I have added some notes in Olly to help follow the assembly code, however, the first thing I want to look at is the ASCII string located at 00402000:

"2YOPB3AQCVUXMNRS97WE0IZD4KLFGHJ8165T"

If you notice, this string is 36 bytes long and contains all of the alpha-numeric characters. If you examine the code in Olly, you see that we have a primary loop with a nested loop, very similar to the previous loops we examined. In fact, the loops themselves function almost identically as the previous loops, so the loop structure should be familiar enough for you to figure out on your own. I have labeled six global variables which are used throughout the loop (gvar1-6); gvar2 and gvar3 are used to count loop iterations for the primary and nested loops respectively. If you skip the examination of the loops temporarily, you will see that gvar6 must be evenly divisible by the numerical value passed to the function. This is why we never completed the previous loop: if gvar6 is not evenly divisible, then it calls our "bad" function, which prints the "Invalid registration key" text and immediately exits the program. The trick now is to find out how gvar6 is calculated.

The primary loop's only function here is to loop five times, once for each character in the string that has been passed to the function; the inner loop loops 36 times (recall how the ASCII string of alpha-numeric characters is 36 bytes long?). So we already have a pretty good idea that each character in "the string" is compared to each character in the ASCII string: this is done using the CMP instruction at 004012E2. If the characters are not equal, then the program simply jumps down to 00401236, increments gvar3 (the inner loop counter), then runs the next iteration of the loop. However, if they are equal, the values in gvar1 (which is initialized to zero before the loops) and gvar3 (the number of times the nested loop has run, aka, the position of the character in the ASCII string that matches the character in "the string") are added together, and the sum saved in gvar4. Next, gvar1 is multiplied by 8, then added to itself (i.e., gvar1+gvar1*8) and the result stored in gvar5. Finally, gvar5 is multiplied by 4 and added to gvar4; the result is saved in gvar6. Now we know how gvar6 is calculated, but there is one more detail; after gvar6 has been calculated, gvar1 is set equal to gvar6. This means that subsequent loops will be affected, because gvar6 is not re-set to zero before other characters in "the string" are calculated. In other words, if "the string" was '44444', the resulting gvar6 value for each character in "the string" will be different because one of the variables used to calculate gvar6 (gvar1 to be precise) changes each time there is a match between the character in "the string" and a character in the ASCII string.

All of this is much easier to comprehend if you single-step through the code in Olly and examine the above notes I have taken on each instruction. However, to further simplify, here's some pseudo-C code:

int key_check_function(int divisor, char the_string[])

{

//initialize gvar1 to zero

gvar1 = 0;

                        //the primary loop which iterates through each character in the_string

                        for(gvar2=0;gvar2<5;gvar2++){

                                    //nested loop that compares the current character in the_string to every character in ascii_string

                                    for(gvar3=0;gvar3<36;gvar3++){

                                                if(the_string[gvar2] == ascii_string[gvar3]){

                                                            //if the two bytes match, calculate gvar6 for that particular byte

                                                            gvar4 = gvar1+gvar3;

                                                            gvar5 = gvar1+gvar1*8;

                                                            gvar6 = gvar4+gvar5*4;

                                                            gvar1 = gvar6;

                                                }

                                    }

                        }

                        //the final gvar6 value is divided by the divisor integer passed to the function

                        mod = gvar6 % divisor;

                        //if gvar6 is not evenly divisible, then call the "bad" function; else, return 0

                        if(mod != 0) {

                                    bad_function();

                        }

            return 0;

That's a bit much, so if you're still struggling with understanding how it all fits together, don't worry (I didn't get it right away either ;)...just step through the code in Olly some more, observe what is happening with the various values, and refer back to my Olly notes and/or the above pseudo code until you do.

Get it? Good, because now we are going to write a keygen for this. Unfortunately the mathematical force is not strong with me, so I couldn't figure out a way to create a reverse algorithm for this function; the problem of course is that you have to choose a value that is divisible by the particular divisor (remember how the key_check_function is called with different values for the divisor each time), then work backwards from there. It just seemed like way to much work...so instead, I wrote a keygen that brute forces each of the four 5-character sets in the registration key (remember that they are examined individually too). To do this, I generated a random set of four alpha-numeric characters, then iterated through each character in the ASCII string, checking to see if it would create a valid key set if plugged in as the fifth character. If so, then that value was used; if not, then another four character string was calculated, and the process was done over again. The resulting code is listed in the usp_key_gen.c file in the source directory.

  

Discovering and Exploiting Buffer Overflows

Now that we have sufficient practice in reversing closed source programs, it's time to examine buffer overflows. For this final section of the tutorial, we will be exploiting weird.exe which is a crack-me program included with Security Warrior. This program, as well as others used in the book, is available for download from O'Reilly Publishing (it is also included in the apps directory in this tutorial's zipped file). It is assumed that you have a basic knowledge of buffer overflows and stack operations.

Examining the Program

As usual, before doing anything else, let's run weird.exe and see what we are working with. We are prompted for a serial number, so enter whatever you like (I used the usual '12345'), and hit enter. We are taken to a new line and nothing else happens. Hit enter again and the program quits. Well, we didn't get much information to work with there, so let's take a look at it in Olly. Looking around in the code a bit, we find the function that prompts us for our serial located at 00401108:

We see that there are several references to ASCII strings...the first three we saw when running the program, but the fourth string reference (located at 00401177) looks like what we want to see when we enter a serial. Notice that it is pushed as an argument to the function at 00404B38, which is also the function used to print the first three strings to the screen - essentially the equivalent of printf(). Furthur, we see that the function at 0040479C is called immediately after prompting for our serial, so we can assume that this function is similar to gets(). However, examining the code that is executed between the call to 0040479C and the "w00! congrats" string reference, we see that there are no jumps to 00401177. In fact, all of the jumps explicitly jump over that string reference and the subsequent call to 00404B38. This means that even if we did enter a valid serial, we would never actually validate. So it looks like we'll have to find a way to take over the EIP and redirect the program's execution to the line at 00401177.

Some Quick BOF Information

For those already familiar with buffer overflows, skip to the next part of this section. As a quick refresher for everyone else, here are some basic rules about buffer overflows:

1. The primary goal is to manipulate the value stored in the instruction pointer (EIP). Depending on the position and usage of variables in the program, there may be other ways to exploit a buffer overflow, but this is the holy grail.
2. The EIP register can not be directly manipulated. For example, you can't do something like 'pop eip', or 'mov eip,eax'. However, when a function is called, the function must know how to return to the code that called it. This is done by automatically pushing a return address (the next instruction to be executed) onto the stack whenever a function is called. When the called function returns (the RETN instruction), it automatically pops the return address off the stack and into the EIP register.
3. The above is the basis of your standard stack-based buffer overflow; when user-supplied data is copied into a location on the stack without any bounds checking, we may be able to supply a sufficiently long string of data that will overwrite the return value that was pushed onto the stack when the function was called. When the function returns, it will return to whatever memory address we overwrote the original return value with.
4. To accomplish this, remember how data is pushed onto the stack. As data is pushed onto the stack, the stack grows downwards, from high memory addresses to low memory addresses. However, space is allocated for local variables on the stack as well, and when those variables are filled with data, the data grows UP. Suppose we have a function that defines three local char variables (one byte each):

char a,b,c;

For example purposes, the program will allocate three bytes on the stack for these variables, and the stack will look like this:

Return address  (4 bytes)

Saved EBP         (4 bytes)

char a               (1 byte)

char b               (1 byte)

char c                (1 byte)

Now, if we write one byte to char c, then the byte allocated for the c variable will be filled. But if we try to write two bytes to c, then the c variable will get the first byte, and the second byte will overflow into char b's memory address. If we write three bytes, the third byte will overflow into char a's memory address. If we write seven bytes into c, then we will fill the four bytes that contain the saved EBP value; if we write 11 bytes into c, then we will also fill the four bytes that contain the return address. So you can see that while the stack grows down, data written to the stack grows up.

Locating a Buffer Overflow

Before we can try to exploit a buffer overflow, we must first find one. We can start by looking for obvious vulnerabilities, such as the use of gets(), strcpy() and the like; this can be done by right clicking the code window in Olly and selecting 'Search for -> All intermodular calls'. This reveals some known calls, but nothing like what we are looking for; judging from the fact that proprietary functions have been used in place of printf() and gets(), the programmer has probably done this throughout the application.

Now let's examine avenues of attack; in other words, what data do we control? The only data that we control in this program is the serial number, so let's take a look at what is done with that serial number after we hit the enter key. We have already identified that the function at  0040479C retrieves the text that we enter, so let's breakpoint on that and step into it when Olly breaks:

As usual, I've included some notes. This function takes one argument, which is a memory address (the argument is located at EBP+8). The address of the argument is loaded into EBX; then the program jumps down to 004047C6, where another function at 0040408A4 is called; it is supplied with the memory address 0040D19C. This is the actual function that retrieves our registration text, and it places it in 0040D19C. But, we needn't examine this function, because there is something interesting happening immediately in the current function code. Note how the loop starts copying the retrieved text one byte at a time onto the stack? While the function at 0040408A4 placed the string in a memory address, this loop is copying it into the address that was passed to the function as its one and only argument. Taking a look at the stack, we see that the address that our string is being copied into is 0012FF40, and the return address for this function (ideally the one we want to overwrite) is located at 0012FF38:

As you step through the loop however, you will notice that the string text is growing away from the return address at 0012FF38. Why? Recall that the stack grows down, but data grows up...the function was given an argument that contained the memory address to copy the string into, but that memory address (0012FF40) is located above the return address of the current function. However, not all is lost; the stack also contains return addresses for other functions, and these are located above 0012FF40. Let's trace through this current function until we return. We are now back in the first function that we examined. Let's trace through until the end of that function, and stop when we get to the RETN instruction at 0040118C. Take a look at the stack window:

Located at 0012FF90 is the return address for this function. We need the return address to read 00401177 in order for the program to jump back up to the instructions that print the "w00!" text. Some quick math tells us that 0012FF90 is 80 bytes above 0012FF40, where our registration text begins to be copied into. So, the 81^st byte would overwrite the first byte of the saved return address, the 82^nd would overwrite the second byte, and the 83^rd would overwrite the third, etc. We can test this by supplying 84 bytes of text as a registration key:

Now let's look at the stack when we reach the RETN instruction for the first function:

0x41 is the hex value for the ASCII letter 'A' - now that we know we can control the EIP through this return instruction, it's time to code an exploit.

We don't want the function to return to 0x41414141, we want it to return to 0x00401177, so the last four bytes will need to be changed so that when they overwrite the saved return address with this value. For this, we will write a simple perl script:

#print 'A' 80 times to fill up the space between 0012FF40 and 0012FF90

print "A"x80;

#print the last three bytes of our desired return address in little-endian order

print "\x77\x11\x40";

What's going on with that last line you ask? Why are there only three bytes, and why are they in reverse order? The x86 architecture uses what is called little-endian byte order; in other words, data is written to the least-significant bytes first. So, as the loop writes each byte of our string into the stack, the data is written in this order (assume that the string 'ABCD' has been entered):

00000000         No bytes copied

00000041         First byte (A) copied

00004241         Second byte (B) copied

00434241         Third byte (C) copied

44434241         Fourth byte (D) copied

As you can see, 'A', the first byte in our string, is copied into the lowest byte in the buffer. The second byte, 'B' is copied into the second-lowest byte, and so on. So, in order for our return address to read '00401177', we need to enter a string that supplies 0x77 first, 0x11 second, and 0x40 third. Which brings us to our second question, why are we ignoring the highest-order byte, 0x00? Well, all text strings in a program must be null terminated (i.e., they must end with 0x00); user-supplied strings are no different, so when you supply your registration key, the 0x00 is automatically added on to the end of the string for us!

OK, now, the test. Run the perl program:

And copy/paste the output into the input of weird.exe. Press enter twice, and:

Whew!! That's a lot of information for a beginner. So let's let that sink in for a while, and we'd be more than happy to continue the conversation in the forums. Be sure to use that little cartoon bubble at the top of this article to get there.

Hope you're enjoying this continuing series on programming for the non-coding security professional. As always, send me your feedback on what we've already done as well as topics you'd like to see covered in future articles.