Merth
06-30-2003, 06:46 AM
This is a brief walkthrough of a recent session I did - it's simply too much to try to explain every detail. Sorry if I accidentally skip over something important!
I've spent a good deal of time lurking in the reverse engineering community, but I've never really seen anyone disclose how it's actually done. So if you are really familiar with low level programming and just need a nudge in this area, this may interest you.
The problem:
A packet being sent across the network had some sort of CRC algorithm applied to it. But I didn't know what the algorithm was. I only had the executable that performs the algorithm.
The solution:
The first thing I did was make a list of known facts:
* Packets are being sent via UDP/IP
* Each packet has a unique identifier, and the identifier I want is 0x0254
* The size of the packet I want is known: 0x18C with CRC, 0x188 without CRC
* The CRC is the first 4 bytes of the payload
* Remaining payload was data the CRC applied to
* No symbols exist for exectuable
* I know packet contents both from packet sniffing and from having the ability to generate fake packets.
* CRC value of packet is observed to be 0x12345678 (let's say)
Right away, I can see an easy way to attack this problem: attach a debugger to the executable, and create a breakpoint for each time a packet is received. Once we find our packet (via the identifier), we can start stepping through the assembly language to figure out what they are doing with the packet.
The debugger of choice for me is windbg for this type of problem. This debugger is incredibly powerful, and is COMPLETELY FREE. Go to Microsoft Debugging Tools (http://www.microsoft.com/whdc/ddk/debugging/default.mspx) to download the debugger. It is also necessary to download the windows symbols, which is a hefty 176mb download.
Goal #1: Determine when packet arrives
Once windbg was installed and had its symbols path set, I cranked up the executable. Right away, the debugger breaks to allow me to enter any commands or breakpoints prior program entry. I know that we need to break each time a packet is received, so I had to figure out how the executable is receiving packets. With UDP/IP, winsock is the most likely candidate. Using VS.NET's dumpbin.exe, I determined the following functions to be candidates for receiving packets:
WSOCK32!recv
WSOCK32!recvfrom
WS2_32!WSARecv
WS2_32!WSARecvFrom
WS2_32!recv
WS2_32!recvfrom
So, with winsock symbols loaded, I was able to put a breakpoint on each of these functions. Here's the breakpoints I did:
bp wsock32!recv "g@$ra; r eax; g"
bp wsock32!recvfrom "g@$ra; r eax; g"
bp ws2_32!wsarecv "g@$ra; r eax; g"
bp ws2_32!wsarecvfrom "g@$ra; r eax; g"
bp ws2_32!recv "g@$ra; r eax; g"
bp ws2_32!recvfrom "g@$ra; r eax; g"
Each breakpoint behaves the same: once the program steps into any of these 6 functions, the following 3 commands will be executed: g@$ra (step OUT of the function), r eax (display the value of the EAX register), and g (continue program execution).
Why display EAX after stepping out? Winsock functions are standard DLL exports, so I know they use the standard calling convention. That means the return value of the function is stored in the EAX register upon completion. Since the command g@$ra steps out of the function, r eax will display the return value each time the function executes. For these winsock functions, the return value shows how much data was received. Since we know the packet size, we can just watch program execution to verify which function is the one used to process our data.
After program execution, it was determined that the wsock32!recvfrom function was the culprit. On to the next breakpoint!
In a game like there, there are thousands of packets that are sent. We cannot possibly break and analyze each of them until we find the packet we want - there's just too much manual work.
The trick is to set a breakpoint that triggers only when our packet arrives. There are many ways to do this, and I see a better way to figure it out in hindsight... Nonetheless, here's how I did it: I put a breakpoint on recvfrom() that displays the first 48 bytes of each packet received, and look for the one that identifies our packet:
bp wsock32!recvfrom "g@$ra; db poi(esp-4) L30; g"
This breapoint does 3 things: Step out of the recvfrom() function, displays in byte format the first 0x30 (48) bytes found at address (esp-4), and then continues program execution.
ESP is the stack pointer. I won't explain what a stack pointer is here, so assuming you know: After stepping out, the char* param to recvfrom() is found at (esp-4). This is not something I knew beforehand; I played around with the memory window, looking at all values around ESP until I figured this out.
When I saw the contents of our packet flow across the debug window, I determined that the CRC was at a 22 byte offset from the beginning of this buffer, and the packet was at a 26 byte offset.
Knowing this CRC value and its position, I was able to set a breakpoint that *only* triggered when our packet arrives. Here's the conditional breakpoint:
bp wsock32!recvfrom "g@$ra; j (dwo(poi(esp-4) + 22) == 0x78563412) 'db poi(esp-4)' ; 'g'"
Program exection stopped when our packet was found, and displayed a sampling of the packet for convenience. Notice I arranged the CRC to compensate for network byte order. I didn't know this beforehand, I just saw the memory and made the arrangement as I saw fit.
I've now accomplished goal #1: Stop execution at exactly the point when my packet arrives. Goal #2: Determine what they are doing with the packet!
Goal #2: What are they doing with packet?
Using the memory window, I saw that our packet was being stored at address 0x01d0fc14. I found that windbg allows you to break when a section of memory is accessed. This is perfect for what I want. So I put a memory access breakpoint onto our packet:
ba r4 0x01d0fc14
Here's the tricky part.. How do I determine when they start applying the CRC? I decided to just step through the code without getting too much into assembly, just to have a general idea of what is being done to the packet. I made a list of all commands that accessed my packet, keeping a watchful eye on the packet in the memory window to see when it disappeared:
#1 0050c3d3 8a19 mov bl,[ecx]
#2 0050c3f3 8a19 mov bl,[ecx]
#3 0050c3ff 8a5901 mov bl,[ecx+0x1]
#4 0050c41a 8a5901 mov bl,[ecx+0x1]
0050c41d 8b04853cff5c00 mov eax,[image00400000+0x1cff3c (005cff3c)+eax*4] ds:0023:005d00a8=fcb9887c
#5 0050abb1 c1e902 shr ecx,0x2
0050abb4 f3a5 rep movsd ds:0203fc18=57007474 es:003fabe8=6556096d
After the fifth memory access breakpoint was hit, the packet was destroyed. One of these five commands does something important with the packet!
The culprit was the rep movsd command. This makes a copy of our packet to another memory location. The location is specified by the edi register, according to windbg documentation. So I put a breakpoint on that memory access location, and created another list:
ba r4 003fabe4
#1 004f7752 668b03 mov ax,[ebx]
#2 00570851 7229 jb image00400000+0x17087c (0057087c)
00570853 f3a5 rep movsd ds:003fa9e0=00000000 es:006b0fa0=614a0000
I noticed that they were making a third copy of our packet! So let's do it again:
ba r4 006b0f5c
#1 004d6691 0fb703 movzx eax,word ptr [ebx]
004d6694 50 push eax
004d6695 ff75f8 push dword ptr [ebp-0x8]
004d6698 e881d9fbff call image00400000+0x9401e (0049401e)
I didn't need to go any further. The code was pushing our packet onto the stack and was invoking some function. The thing that REALLY caught my eye here was the other value pushed onto the stack - it was the packet identification 0x0254!
Finally! I had found the function that processes the packet. Somewhere in here was code to calculate the CRC.
But where do I go from here? There was waaaaaay too much assembly inside of this function for me to make any sense of it. My breakpoint was being hit too many times. I was stuck.
Until something dawned on me ...
...
If you generate a packet with a CRC that is deliberately invalid, this function fails and everything gets rejected. A common tactic by programmers for signalling failure is to have a function return a bool. If they are using the standard calling convention, a function that returns a bool would put the bool into the EAX register upon function completion...
So I generated a fake packet with an intentionally invalid CRC and stepped out of the function, and I was welcomed with a EAX=0! My guess was correct - they are returning a bool from this function. Somewhere in there, a failure was being encountered. I figured this must be a generic function of some sort that handles all packet functions - and one of the functions calculates the CRC. And, assuming this also uses the bool convention, I just needed to figure out which function within this function was causing it to return false!
It was a guess, but it turned out to be the winner. Single stepping through this function and ONLY watching for the assembly instruction call, I determined which function call was causing the main function to abort:
004935f1 e8cc120600 call image00400000+0xf48c2 (004f48c2)
004935f6 3b06 cmp eax,[esi]
004935f8 59 pop ecx
004935f9 59 pop ecx
The really interesting part here was the two "pop" instructions: They pop the values 0x006b0f62 and 0x0188. The first address points to our packet just beyond the CRC and the second value is the length of our packet without the CRC! We all know a CRC algorithm needs access to the memory, and it needs to know how many bytes should be analyzed - coincidence?
This function was doing something with our packet, and that something was failing. Stepping into this function, I put a memory access breakpoint on our packet so I could stop at the exact point that it is messing around with our data:
ba r4 006b0f62
The very first breakpoint hit was incredible to see: Some sort of loop, iterating over each byte of our packet. It was 10 simple instructions:
004f48cd 8b4c2404 mov ecx,[esp+0x4]
004f48d1 0fbe0c0a movsx ecx,byte ptr [edx+ecx]
004f48d5 33c8 xor ecx,eax
004f48d7 42 inc edx
004f48d8 81e1ff000000 and ecx,0xff
004f48de c1e808 shr eax,0x8
004f48e1 8b0c8d804b5c00 mov ecx,[image00400000+0x1c4b80 (005c4b80)+ecx*4]
004f48e8 33c1 xor eax,ecx
004f48ea 3b542408 cmp edx,[esp+0x8]
004f48ee 7cdd jl image00400000+0xf48cd (004f48cd)
What does this assembly mean? I read C++ better, so I wrote up pseudo C++ code:
(1) ecx = esp+4
(2) ecx = *(ecx + edx)
(3) ecx ^= eax
(4) edx++
(5) ecx &= 0xff
(6) eax >>= 8
(7) ecx = *(0x005c4b80 + ecx*4)
(8) eax ^= ecx
(9) if *(edx) < *(esp+8), goto (1)
(10) else, done
After stepping through a couple of times, I determined the following:
eax = current crc
esp+4 = beginning of packet, past crc
esp+8 = length of packet (0x188=392 bytes)
edx = counter, like in a for(;;) loop
005c4b80= address for some sort of table w/32 bit values... i'm guessing 256 of them
After sending a valid packet, I determined these 10 lines of code to be the exact CRC algorithm we were looking for.
Quod Erat Demonstrandum
I was happy, and there was much rejoicing. (yay!)
Conclusion
Reverse engineering is not necessarily about stepping through millions of lines of assembly code and figuring out what each line is doing... It can be as simple as setting up clever breakpoints!
I've spent a good deal of time lurking in the reverse engineering community, but I've never really seen anyone disclose how it's actually done. So if you are really familiar with low level programming and just need a nudge in this area, this may interest you.
The problem:
A packet being sent across the network had some sort of CRC algorithm applied to it. But I didn't know what the algorithm was. I only had the executable that performs the algorithm.
The solution:
The first thing I did was make a list of known facts:
* Packets are being sent via UDP/IP
* Each packet has a unique identifier, and the identifier I want is 0x0254
* The size of the packet I want is known: 0x18C with CRC, 0x188 without CRC
* The CRC is the first 4 bytes of the payload
* Remaining payload was data the CRC applied to
* No symbols exist for exectuable
* I know packet contents both from packet sniffing and from having the ability to generate fake packets.
* CRC value of packet is observed to be 0x12345678 (let's say)
Right away, I can see an easy way to attack this problem: attach a debugger to the executable, and create a breakpoint for each time a packet is received. Once we find our packet (via the identifier), we can start stepping through the assembly language to figure out what they are doing with the packet.
The debugger of choice for me is windbg for this type of problem. This debugger is incredibly powerful, and is COMPLETELY FREE. Go to Microsoft Debugging Tools (http://www.microsoft.com/whdc/ddk/debugging/default.mspx) to download the debugger. It is also necessary to download the windows symbols, which is a hefty 176mb download.
Goal #1: Determine when packet arrives
Once windbg was installed and had its symbols path set, I cranked up the executable. Right away, the debugger breaks to allow me to enter any commands or breakpoints prior program entry. I know that we need to break each time a packet is received, so I had to figure out how the executable is receiving packets. With UDP/IP, winsock is the most likely candidate. Using VS.NET's dumpbin.exe, I determined the following functions to be candidates for receiving packets:
WSOCK32!recv
WSOCK32!recvfrom
WS2_32!WSARecv
WS2_32!WSARecvFrom
WS2_32!recv
WS2_32!recvfrom
So, with winsock symbols loaded, I was able to put a breakpoint on each of these functions. Here's the breakpoints I did:
bp wsock32!recv "g@$ra; r eax; g"
bp wsock32!recvfrom "g@$ra; r eax; g"
bp ws2_32!wsarecv "g@$ra; r eax; g"
bp ws2_32!wsarecvfrom "g@$ra; r eax; g"
bp ws2_32!recv "g@$ra; r eax; g"
bp ws2_32!recvfrom "g@$ra; r eax; g"
Each breakpoint behaves the same: once the program steps into any of these 6 functions, the following 3 commands will be executed: g@$ra (step OUT of the function), r eax (display the value of the EAX register), and g (continue program execution).
Why display EAX after stepping out? Winsock functions are standard DLL exports, so I know they use the standard calling convention. That means the return value of the function is stored in the EAX register upon completion. Since the command g@$ra steps out of the function, r eax will display the return value each time the function executes. For these winsock functions, the return value shows how much data was received. Since we know the packet size, we can just watch program execution to verify which function is the one used to process our data.
After program execution, it was determined that the wsock32!recvfrom function was the culprit. On to the next breakpoint!
In a game like there, there are thousands of packets that are sent. We cannot possibly break and analyze each of them until we find the packet we want - there's just too much manual work.
The trick is to set a breakpoint that triggers only when our packet arrives. There are many ways to do this, and I see a better way to figure it out in hindsight... Nonetheless, here's how I did it: I put a breakpoint on recvfrom() that displays the first 48 bytes of each packet received, and look for the one that identifies our packet:
bp wsock32!recvfrom "g@$ra; db poi(esp-4) L30; g"
This breapoint does 3 things: Step out of the recvfrom() function, displays in byte format the first 0x30 (48) bytes found at address (esp-4), and then continues program execution.
ESP is the stack pointer. I won't explain what a stack pointer is here, so assuming you know: After stepping out, the char* param to recvfrom() is found at (esp-4). This is not something I knew beforehand; I played around with the memory window, looking at all values around ESP until I figured this out.
When I saw the contents of our packet flow across the debug window, I determined that the CRC was at a 22 byte offset from the beginning of this buffer, and the packet was at a 26 byte offset.
Knowing this CRC value and its position, I was able to set a breakpoint that *only* triggered when our packet arrives. Here's the conditional breakpoint:
bp wsock32!recvfrom "g@$ra; j (dwo(poi(esp-4) + 22) == 0x78563412) 'db poi(esp-4)' ; 'g'"
Program exection stopped when our packet was found, and displayed a sampling of the packet for convenience. Notice I arranged the CRC to compensate for network byte order. I didn't know this beforehand, I just saw the memory and made the arrangement as I saw fit.
I've now accomplished goal #1: Stop execution at exactly the point when my packet arrives. Goal #2: Determine what they are doing with the packet!
Goal #2: What are they doing with packet?
Using the memory window, I saw that our packet was being stored at address 0x01d0fc14. I found that windbg allows you to break when a section of memory is accessed. This is perfect for what I want. So I put a memory access breakpoint onto our packet:
ba r4 0x01d0fc14
Here's the tricky part.. How do I determine when they start applying the CRC? I decided to just step through the code without getting too much into assembly, just to have a general idea of what is being done to the packet. I made a list of all commands that accessed my packet, keeping a watchful eye on the packet in the memory window to see when it disappeared:
#1 0050c3d3 8a19 mov bl,[ecx]
#2 0050c3f3 8a19 mov bl,[ecx]
#3 0050c3ff 8a5901 mov bl,[ecx+0x1]
#4 0050c41a 8a5901 mov bl,[ecx+0x1]
0050c41d 8b04853cff5c00 mov eax,[image00400000+0x1cff3c (005cff3c)+eax*4] ds:0023:005d00a8=fcb9887c
#5 0050abb1 c1e902 shr ecx,0x2
0050abb4 f3a5 rep movsd ds:0203fc18=57007474 es:003fabe8=6556096d
After the fifth memory access breakpoint was hit, the packet was destroyed. One of these five commands does something important with the packet!
The culprit was the rep movsd command. This makes a copy of our packet to another memory location. The location is specified by the edi register, according to windbg documentation. So I put a breakpoint on that memory access location, and created another list:
ba r4 003fabe4
#1 004f7752 668b03 mov ax,[ebx]
#2 00570851 7229 jb image00400000+0x17087c (0057087c)
00570853 f3a5 rep movsd ds:003fa9e0=00000000 es:006b0fa0=614a0000
I noticed that they were making a third copy of our packet! So let's do it again:
ba r4 006b0f5c
#1 004d6691 0fb703 movzx eax,word ptr [ebx]
004d6694 50 push eax
004d6695 ff75f8 push dword ptr [ebp-0x8]
004d6698 e881d9fbff call image00400000+0x9401e (0049401e)
I didn't need to go any further. The code was pushing our packet onto the stack and was invoking some function. The thing that REALLY caught my eye here was the other value pushed onto the stack - it was the packet identification 0x0254!
Finally! I had found the function that processes the packet. Somewhere in here was code to calculate the CRC.
But where do I go from here? There was waaaaaay too much assembly inside of this function for me to make any sense of it. My breakpoint was being hit too many times. I was stuck.
Until something dawned on me ...
...
If you generate a packet with a CRC that is deliberately invalid, this function fails and everything gets rejected. A common tactic by programmers for signalling failure is to have a function return a bool. If they are using the standard calling convention, a function that returns a bool would put the bool into the EAX register upon function completion...
So I generated a fake packet with an intentionally invalid CRC and stepped out of the function, and I was welcomed with a EAX=0! My guess was correct - they are returning a bool from this function. Somewhere in there, a failure was being encountered. I figured this must be a generic function of some sort that handles all packet functions - and one of the functions calculates the CRC. And, assuming this also uses the bool convention, I just needed to figure out which function within this function was causing it to return false!
It was a guess, but it turned out to be the winner. Single stepping through this function and ONLY watching for the assembly instruction call, I determined which function call was causing the main function to abort:
004935f1 e8cc120600 call image00400000+0xf48c2 (004f48c2)
004935f6 3b06 cmp eax,[esi]
004935f8 59 pop ecx
004935f9 59 pop ecx
The really interesting part here was the two "pop" instructions: They pop the values 0x006b0f62 and 0x0188. The first address points to our packet just beyond the CRC and the second value is the length of our packet without the CRC! We all know a CRC algorithm needs access to the memory, and it needs to know how many bytes should be analyzed - coincidence?
This function was doing something with our packet, and that something was failing. Stepping into this function, I put a memory access breakpoint on our packet so I could stop at the exact point that it is messing around with our data:
ba r4 006b0f62
The very first breakpoint hit was incredible to see: Some sort of loop, iterating over each byte of our packet. It was 10 simple instructions:
004f48cd 8b4c2404 mov ecx,[esp+0x4]
004f48d1 0fbe0c0a movsx ecx,byte ptr [edx+ecx]
004f48d5 33c8 xor ecx,eax
004f48d7 42 inc edx
004f48d8 81e1ff000000 and ecx,0xff
004f48de c1e808 shr eax,0x8
004f48e1 8b0c8d804b5c00 mov ecx,[image00400000+0x1c4b80 (005c4b80)+ecx*4]
004f48e8 33c1 xor eax,ecx
004f48ea 3b542408 cmp edx,[esp+0x8]
004f48ee 7cdd jl image00400000+0xf48cd (004f48cd)
What does this assembly mean? I read C++ better, so I wrote up pseudo C++ code:
(1) ecx = esp+4
(2) ecx = *(ecx + edx)
(3) ecx ^= eax
(4) edx++
(5) ecx &= 0xff
(6) eax >>= 8
(7) ecx = *(0x005c4b80 + ecx*4)
(8) eax ^= ecx
(9) if *(edx) < *(esp+8), goto (1)
(10) else, done
After stepping through a couple of times, I determined the following:
eax = current crc
esp+4 = beginning of packet, past crc
esp+8 = length of packet (0x188=392 bytes)
edx = counter, like in a for(;;) loop
005c4b80= address for some sort of table w/32 bit values... i'm guessing 256 of them
After sending a valid packet, I determined these 10 lines of code to be the exact CRC algorithm we were looking for.
Quod Erat Demonstrandum
I was happy, and there was much rejoicing. (yay!)
Conclusion
Reverse engineering is not necessarily about stepping through millions of lines of assembly code and figuring out what each line is doing... It can be as simple as setting up clever breakpoints!