Sunday 13 May 2018

Reverse engineering the Path of Exile game protocol - Part 1: Obtaining the plaintext

Part 2: Decoding the protocol

Part 3: Introducing exileSniffer


As I've just bought a shiny new Binary Ninja licence I thought I'd document trying it out on a target I have a passing familiarity with and how the experience differs from using IDA.

Update: Binary Ninja has been updated a lot since this was written, adding some functionality that I wanted (such as unicode string support!).

The target


Please excuse the Virtual Machine graphics
Path of Exile (POE) is a Diablo-like looting/trading/number increasing game which, aside from being free to play, also has a rather permissive EULA regarding reverse engineering clauses. Modifying the client is banned, as is scraping data from the website, but reversing and extracting data from the client isn't mentioned - so here we go.

I haven't really played the game seriously (eg: never levelled a skill gem to 20) but back in the days before builtin item filtering I wanted a way to figure out what items dropped and ping an alert, so you didn't miss valuable things in the mess of loot during fast placed gameplay. Shortly after starting work on it the developers added some really rich item filtering functionality, so after a bit of work decoding the protocol I shelved the project. A couple of years on and I bought a shiny new Binary Ninja licence and wanted some experience reversing a big production-quality C++ application with it - POE seemed like a good choice.


The game is funded through microtransactions like these, which are everything I've ever wanted in life.

POE offers a standalone client and one bundled with Steam - we can use the standalone one to avoid having to worry about any Valve-Anti-Cheat shenanigans.

Initial traffic analysis

While playing the game, Sysinternals TCPView tells us that PathOfExile_x64.exe has a TCP connection established to a remote server on port 6112.

Capturing a bit of traffic in Wireshark, we can see lots of packets with 2 byte payloads coming to and from this port and a few bigger payloads too but nothing with any readable strings in. We can assume the stream is encrypted, because that's the fashion these days, but as a further check we can do a quick entropy test.

Viewing the TCP stream in Wireshark

Exporting the packets in this stream from Wireshark to a pcapng file and use these runes (in Linux) to extract the payload bytes:
tshark -T fields -e data.data -r poecapture.pcapng | tr -d ':\n' | xxd -r -p > payloads.bin

This uses tshark to extract the data bytes as a hexdump, pipes them to tr which removes the formatting from the hexdump, pipes those to xxd to reverse the hex into a continuous blob of binary data and finally writes it to payloads.bin.

We can then use the handy ent tool (from an 'apt-get install ent' near you) to get a rough idea of how random the data inside is.
Entropy = 7.991133 bits per byte.
Optimum compression would reduce the size of this 19761 byte file by 0 percent.
Chi square distribution for 19761 samples is 242.41, and randomly would exceed this value 70.45 percent of the times.
Arithmetic mean value of data bytes is 126.4821 (127.5 = random).
Monte Carlo value for Pi is 3.205587610 (error 2.04 percent).
Serial correlation coefficient is -0.004831 (totally uncorrelated = 0.0).
The stream is indistinguishable from random noise - encrypted, rather than encoded, so we are going to have to go back to the start to see how we got here.


Logging in - the livestream



Fig 1: The PoE client login screen

Open up wireshark and press login with valid creds to see an exchange like this:

Fig 2: Example login packet capture


The client looks up the nearest login server, performs the 3 way TCP handshake and starts the stream with a 134 byte payload

Message 1. Client to Server
Fig 3: 2 Separately captured 134 byte initial payloads highlighted by Wireshark, with constants annotated
If we compare two of these payloads side by side, 6 constant bytes immediately jump out, with the rest being apparently unpredictable. If we look at the next payload in the sequence it has the same 4 byte prefix but without null bytes at the end, suggesting that they might be padding.

The 0x80 part of the constant bytes is particularly interesting because it's 128 in decimal. 128 + 6 constant bytes -> 134 bytes, the size of the payload, so a first guess for the message meaning is something like:
       
0001 : [Message ID or Counter]
0080 : [Length field]
xxxx : [Unknown data of length 0x80]
0000 : [Padding]

Message 2. Server to Client

Fig 3: 2 Separately captured 190 byte "response" payloads
This reply message is longer but has the same 0x80 field. Either the length guess is wrong or something comes after the initial data. Adding 0x80 to the offset of our mystery data (0x39) gives us 0xB9, which is the start of the green box highlighed. Another 2 byte value here - 0x38 (56) is exactly the length of the remaining bytes in the payload so it's a length field too.

Message 3. Client to Server

Fig 4: Payload 3, Client to Server, 147 bytes
Hmm. This isn't helpful - no predictable bytes. 147 bytes is a pretty weird size too, is the stream encrypted already? Payload 4 is 359 bytes of similarly unpredictable data, and the rest of the packets are no more useful.

We can now make the following assumptions/observations about the login sequence

Client --> Server: [128 byte blob A]
Server --> Client: [128 byte blob] + [56 byte blob]
Client --> Server: [147 bytes of ??]
Rest of the stream: [Unintelligible nonsense]

The 128 byte blobs could be challenges with a 56 byte response, but that's unlikely without some other identifying data. They could also be public keys, which makes more sense for opening an authentication exchange.

From here i'm tempted to try using a bad password to see if the stream changes (and possibly tell us something about the Client->Server blob (A) but it's a good habit to keep suspicious interactions with the server to a minimum. Instead, lets use the awesome free DNS spoofing tool ApateDNS to trick the client into interacting with our own server.

ApateDNS responding to all queries with a local IP
Now we write a python script to spoof the login server using the format we have just seen, but with a constant value for the mystery data since we don't know how to generate that yet. I'm not going to publish the script because releasing a framework for creating a private server significantly increases the chances of me getting in trouble for this blog.

When we press login we are greeted with an error message followed by immediate client termination.

The error our bad response caused

Rhoa.jpg (320×240)
A Rhoa. Also bad.

Unsurprisingly generating the data in these initial packets properly is quite important. This error string also gives us to something to look for in the binary to help narrow down where the login code is.

Another interesting thing to try is varying the metadata that the server responds with. Changing the first 2 bytes to 0x41 (65) results in this illuminating error message:
Unable To Deserialise Packet

Now we have confirmed that the first byte is a packet ID and we have a string to look for in the binary to find the packet deserialising code, awesome! Lets prepare the ground for some disassembly.


Initial Binary Recon- Libraries


First thing to understand is what external code the game uses. If it incorporates libraries with a documented API or open source code then that can save us a huge amount of work.

Sadly Binja doesn't have an import/export feature at the time of writing, but there are plenty of good free PE file analysis tools that do the job. I used pestudio, but it didn't find any imports other than standard windows libraries and the DLLs in the game directory. These are:
  • fmod.dll and fmodstudio.dll (v0.1.9.4): A game sound engine by Firelight Studios with an accessible API
  • d3dcomp_47.dll and d3dcompiler_47.dll: Signed Microsoft Direct3D shader compiler libraries which are probably well documented. If we are disassembling graphics routines then we are wasting our time.
  • bink2w32.dll: Video processing tool called bink from RAD game tools. Again, don't care about this.
Either the rest of the 25MB client is original or we have to go fishing for statically linked code, which is a bit trickier. The first way of dealing with this is FLIRT signatures, which Binary Ninja supports through a plugin. These only support a very limited number of libraries and would require restarting the program which means losing hours of single-threaded linear sweep analysis because the personal addition doesn't cache it.

Another route is to examine the strings. Binary ninja is really weak tool for this ($600 for the commercial version and no Unicode support? Come on.) because Path of Exile uses a Unicode all over the place. Since we already have pestudio open (Sysinternals strings is also great) we can export its strings list into Notepad++ to search.

Useful search strings include 'lib', 'copyright', 'crypt'. '::', 'error' (for descriptive error messages), and the names of common libraries like Boost and Rapidjson.

Highlights of the results include:
  • a handful of Boost references - No useful X-refs in the code but it's open source and often used all over a target binary so worth looking out for because we don't want to waste time reversing open source code.
  • "CLIENT libcurl 7.47.0" - An exact version of an open source networking library, awesome. This version has 27 disclosed vulnerabilities though, which is somewhat less good. It would be interesting to see if there is any unauthenticated attack surface - maybe in the patchserver or message of the day handling.
  • Lots of references to CryptoPP, which is the open source crypto++ library and very promising for our initial goal of 'decrypt stuff'.
  • "inflate 1.2.8"/"deflate 1.2.8" - zlib. More horrible arithmetic-heavy assembly that we can now understand from the source code or avoid entirely.
Another interesting result is found when sorting strings by length. There are multiple long strings of the form: 

"0x66c7ea5ba0aef7301b3621bee45a1e7d80f1aaa066ebcd917b05b6356a63bab8f7e220d44619f45d65535e651f284ceac5420ad9a90bd288cda759c49f8a395cf68b411861e54c179910132c7c44acc40e0deecc211d7bce5652ea[continued]"

If you find huge numbers built into a binary: it's often crypt related, and Crypto++ uses numbers in that format. 

Navigating the disassembly


With the potential access to the source code of some important chunks of the binary, it's time to start clicking graphs to get a feel for the target.

Loading PathOfExile_x64.exe into Binary Ninja and waiting 11 minutes for the standard single threaded analysis to finish yields less than 7000 identified functions. As IDA finds around 55,000 I would probably have given up at this point if that was the best it could do. Fortunately there is Linear Sweep option with a big (BETA) label next to it, which displayed over 50000 functions detected during the analysis but 33550 when counting through the console using len(bv.functions). Either way it's enough to work with.

What we want to find is a send or sendto with 134 bytes of data. Navigating to the Import Address Table section of the disassembly we see ordinals for many of the imports instead of names.


Switching to the imports section of pestudio tells us that sendto is ordinal 20 and and send is 19, so we can rename them and then look for the XRefs to see where the data sending routines are.

The packet deserialiser function


Searching for our "unable to deserialise packet" string gives us a result in a single function

Binary Ninja graph of the code which raises an error if the sequence number is bad

It's got a loop which either runs until its internal function returns 0 or exits out with the above error.

As we can see by the Xref window (a really pleasant quality of life improvement over IDA), this is called from two other known locations. An error string in the first suggests that it won't be executed if the client can't connect to the patch server, so we will ignore that. Lets look at the second candidate packet handler.

Just out of frame above is a loop which calls 'deserialisePacket?'

Whatever it does with the deserialised data is hidden in a C++ vtable, but we will worry about that later.

A more immediate problem is that going backwards is a dead end because the fancy new linear sweep algorithm has found no Xrefs to this function and I know from looking at the IDA results that there are multiple. Normally in this situation with IDA I would either hunt for suspicious non-disassembled blobs near the graph or fall back to dynamic analysis. Since computers were made to run code and I happen to have a computer, lets do that.

Getting the callstack


An easy way to find out how this data is being sent is to use API Monitor, a fantastic tool that hooks DLL functions and logs their arguments, the contents of buffers, return values and a limited call stack too. Here is what the login looks like:

The send() call of the clients 134 byte first payload
The tool shows send happening at offset 0x519380. Typing 'bv' for BinaryView in the Binary Ninja console tells us that the start address of the binary is 0x140000000, so adding the call stack offset and navigating ('G') to it gives us the location of the WinSock send() call used in the login.

Function at the top of the callstack, where send() is called

It has loads of Xrefs, so we follow the next offset in the call stack to find the right one:


Next function down on the callstack
Looking promising now. The call to htons suggests data is being prepared for sending. Before we delve into the other functions lets continue going down the call stack to find out how we got here.


3rd entry in the call stack - the login function
Now we know exactly where we are, shortly after the 134 byte send call is the candidatePacketHandler function that handles the response from our server. 

Putting it together

I don't think there is much value in further documenting the step by step reversing of the key agreement scheme, but I pieced it together by examining this area of code, the rest of the call stack and the CryptoPP source as it appears in the binary. It turns out that those huge hex-number strings from earlier are that the first payload are the p,q and g Diffie Hellman domain parameters for creating static and ephemeral client keys.

The clients ephemeral public key is sent to the server in the first packet and receives the servers ephemeral public key in response. A new addition since I looked at this protocol a while ago is that this key is now accompanied by a 56 byte DSA signature  - failure to verify it causes the 'Rhoa Exception #3' seen above.

These client keys, server static public key (embedded in the binary), and the server ephemeral public key (from the network) are used to agree a shared secret value, which is converted into a truncated 64 byte SHA-512 hash (or shared digest).

This hash is split into a 32 byte Salsa stream key and two 8 byte IV's, which both parties use to encrypt the connection.

What now?


Unfortunately for us (but good for security), the magic of public key crypto means we can't produce a matching key from what we know and what we can intercept. Instead we have to engage in some digital thievery by stealing the key data we need for stream decryption from the game clients memory.

The usual way to do this is to figure out the chain of pointers and memory offsets to work out where the key resides so we can extract it, but this is a huge pain in the neck because it breaks almost every time the developer updates the client (which happens a lot).

There is a way round that however: Salsa uses a special constant that is hardcoded into the Salsa20 key structure, so we can easily find all the Salsa keys in memory simply by scanning for this constant.

Crypto++ disassembly from the game client showing the Salsa20 Key structure being filled out with 32 bytes from the shared digest and the "expand-32byte k" constant.

Building a plaintext sniffer

Now we know how to find the key, here is what we need our to do once the player has logged in (and the key exists in memory):
  • Sniff the login and game server connections
  • Scan memory for the Salsa key constant
  • Extract the key and IV
  • Decrypt the intercepted login data and pass the plaintext to the decoder
The implementation isn't particularly interesting to read or write about - the source code is coming, but at a high level we use
  • The windows API with VirtualQueryEx and ReadProcessMemory to get the keydata
  • libtins to read packets via WinPCAP and provide a convenient ciphertext stream for us to decrypt
  • Crypto++ to do the decryption
Next up is the fun part: Decoding the protocol stream!

Nb: I should point out that the Binary Ninja disassembly has improved quite a lot in the months since this was first drafted... but still no unicode. The binary modification is an absolute joy but we won't talk about that here.

5 comments:

  1. Great post man, things like that make me want to learn assembly and all of this low level stuff, truly fascinating

    ReplyDelete
  2. AutoSeededRandomPool rng;
    byte privateKey[0x80], publicKey[0x80];

    Integer p("0x87F6C8BB28FEC7E6A82CA72BB6042521B242A63355C19E93E5926EF5D5EEF25EF7D27F3E446B8062D790E85709F08291D768B81F9A3A76EC9BA2BA77CBCCA60832DFCB9627706C40D8AA7F1E20DA596862E7A1202F80E6321BC9581C9C2479BC331603286342054B0D3C05242748C7594D504F9A360A22A4B5B5E0E1F6FFD1C5", LITTLE_ENDIAN_ORDER);
    Integer q("0x437BE45D14FF63735496D3155B8292105921D399AA60CFC97249B7FA6A7779AF7BE93F1FA23540B16B48F4AB0478C1C86B34DC0F4D1D3BF64D51DDBB6566530499EF65CB133836206CD53F0F10ED2C34B1F35090174073998D642C0E4E923CDE198B019431A182A5069E029213A4E3AC26A8274D1B0511D2DA5AF070FBFFE862", LITTLE_ENDIAN_ORDER);
    Integer g = 2;

    DH dh(p, q, g);
    dh.GenerateKeyPair(rng, privateKey, publicKey);

    ReplyDelete
  3. Hello, I am a Chinese, I want to communicate with you. I know that communication may be an obstacle, please let me know your contact information.

    ReplyDelete
  4. Thank you for your help and let my work progress.

    ReplyDelete
  5. Thanks Nia, for this well-written blog entry. Even though I only understand the basics of ASM, it was really fun to read.

    ReplyDelete