This publication was part of my research project at Stanford University about applying fuzz testing to vulnerability detection. This particular application was about studying the protocols used for communicating between a client and a server of an online video game, build a prototype to perform automated reverse-engineering (like extracting fixed/variable fields) and finally perform fuzz testing.
Thanks to the SecLab, we were able to get a copy of Star Wars Galaxy, Diablo 3 and we also used a free-to-play game League of Legends. We started by defining a scripting API that would be implemented in Python for the prototype and would then be added to the existing code base. The Diablo 3 game communicates with two different servers on the same port. On one of them the client opens an SSL connection using the Secure Remote Password (SRP-6) protocol for the TLS authentication and on the other one, a non-encrypted connection. Typically, the secure connection is used for transaction with virtual money or virtual goods, mostly because they can be bought with real money. The rest is various game information such as players, locations, graphical effects, actions, ...
After a few weeks, the prototype was working on Diablo 3, performing interception and injection of packets using the WFP NT driver developed for the previous project on smartphones. WFP, Windows Filtering Platform is a kernel network API, recent successor of the deprecated Layer Service Provider API (LSP). It has been implemented in the NT kernel and shipped with Windows operating systems since the Vista distribution of Microsoft and allow many filtering operations on any layer of the kernel network stack with an almost complete abstraction of the underlying protocols when it makes sense. For instance, the WFP stream layer operates before the transport layer in the stack (in our case before the TCP layer) which was a perfect match for our purpose because we were able to avoid the pain of updating the TCP and IP checksums and more importantly avoid maintaining the sequence and acknowledge numbers in the TCP headers of each packet to keep the synchronization mechanism working. Please note that not being able to work at this level of the stack would have required us to re-implement a part of the TCP state machine logic in our software and for that this option would probably not have been the best choice. The driver has been implemented and offers a pretty straightforward user-mode interface with the IO controls encapsulated in our API to expose a layer of access to the raw packets similar to the FreeBSD Divert socket API to receive and send data. But the difficulty was on an higher-level protocol: the SSL connection needed to be decrypted mostly because the game had a anti-cheating module that needed to be disabled called Warden and that is able to detect almost any change in the region of the memory containing the code and the gameplay sensitive values. In the end, we had spent a few days trying to break encryption using different methods and our best shot was to build a gateway that behaves like the authentication server and redirects the packets to the actual server acting like the game client. We know the user's password which is the heart of the SRP-6 [1,2] key exchange protocol so we can setup our own secured connections.
After finding some minor bugs in the gameplay protocol, we started working on another game: League of Legends. It uses a Blowfish encryption scheme but the key is passed to the game binary as a command line argument and it has not protection against code injection or IAT hooking.
IAT  stands for Import Address Table and is the address resolution mechanism used by the Windows Portable Executable (PE) binary loader to implement dynamic linking of shared libraries. The idea is that the shared libraries can hypothetically reside at a different address (see ASLR) between two execution so the kernel loader needs a way to dynamically link the functions used by a PE binary to their runtime memory location. Microsoft solved this by creating a table that contains an entry for each function from a shared library that is used by the program and each call is made at the address of the entry in the table. Then each entry in the table contains a JMP instruction to an offset that is changed by the loader when loading the shared library as a DLL file. IAT hooking is the exploitation of this mechanism to replace a shared-library function by your own function. To perform this, we load our DLL which contains the replacement functions and an entry point that the kernel executes upon loading. In our entry point function we search for the IAT addresses or use the static one that we can get by disassembling the binary and replace them by changing the jump offset to our own DLL replacement functions. That's how, we were able to intercept every packet and also inject our forged ones into the game easily.
In order to reverse the protocols more efficiently, the idea was to match a game action or key input with a sequence of packets or a trace and repeat the action a few times, then use the set of traces and perform a differential analysis to extract the variable fields and generate the fuzzing rules. Then a more automated solution as Discoverer  would also be implemented in another module by providing a generic protocol description sharing some ideas with Binpac  the fuzzer would be able to automatically generate testing targets. The problem with this technique is that the number of packets grows exponentially over time. We had to start by filtering the interesting packets in order to concentrate on a few of them which have the most potential in terms of potential bugs. The first idea was to use frequency analysis and extract statistical information about each message in the protocol and using their frequency we could focus on the low-end and high-end peaks to optimize our chances to identify issues. The least used ones would probably corresponds to packets that appear only a very few amount of times per session (like the connection handshake) and therefore they most likely haven't been stress-tested as much as the ones with an higher frequency. But we also needed not per-packet based information to be able to correlate some game events with sequences of packets. By doing an N-gram analysis, which is a type of probabilistic language model used in many different areas of computer science and biology to compare sequences of data, we were able to assign a score to a tuple of messages and compute statistics for every packet type that we had encountered. Every window of messages has a score that is incremented when they are find one after the other in a network trace, that way extracted highly-correlated packets is easier and allowed us to focus the tests on even fewer packets.
The presentation at DEFCON 20 took place in Las Vegas during the last week of July 2012. DEFCON is a well-known conference in the security industry and the work that was presented over the 4 days was very interesting. Our presentation was a success and a lot of people were interested in our work. Indeed, by the end of the week after the conference 4 major companies of the gaming industry contacted us and were interested in participating to the research with our team to use it in Kartograph on their products. The research work ideas were implemented as Kartograph was re-written from scratch in C++ with a scripting interface for Python that allows you to replace and customize modules that performs a specific task for your own testing requirements.
SRP-6: Stanford SRP Homepage and Documentation,
SRP Attack: On Small Subgroup Non-confinement Attack,
Thales E-Security, Cambridge, UK
IAT Hooking explained,
Discoverer: Automatic Protocol Reverse Engineering from Network Traces
USENIX Security Symposium, August 2007.
Binpac: A yacc for Writing Application Protocol Parsers,
Internet Measurement Conference 2006 (IMC 2006), Rio de Janeiro, Brazil.