A friend and I recently began work on a simple web game prototype. My friend has been creating some really exciting web apps with javascript lately, and seeing these introduced me to the rich capabilities of that platform. Add to that the recent discussion of WebGL here at #AltDev, and we started to seriously consider using the browser as a multiplayer game client.

We like C++ too, so we are building our server on top of the Mongoose HTTP server, which I highly recommend if you’re looking for a dead simple way to build a custom HTTP server in C++.

Since HTTP is a stateless, connectionless protocol, we needed a way to uniquely identify the client associated with an HTTP request. Upon authentication, we want to issue an identifier to the client which can be used to associate that client with gameplay data on the server. Subsequent game-related requests from an authenticated client will include the issued identifier.

Ideally, we want to issue an identifier that:

  1. is simple and compact
  2. can be generated quickly and easily
  3. supports rapid gameplay data retrieval
  4. is easy to validate and difficult to falsify

The GUID, The 0xBAAD, and The Ugly

The simplest possible form of identification I could think of was using the gameplay data pointer as an integer. This perfectly satisfies requirements 1, 2, and 3, but fails dramatically at 4. A buggy or malicious client could easily crash the server by supplying an invalid identifier that did not point to actual gameplay data, or with some experimentation, reliably spoof other clients by supplying a pointer at an appropriate offset from their own.

If we instead issued an array index as an identifier, we could defend against crashing the server when identifiers were invalid or out of range. In cases where the array is sparsely populated, this also provides some defense against spoofing, but in cases where the array is well populated, it becomes even easier to successfully spoof another user’s identifier.

An simple alternative that satisfies requirement 4 is to issue a GUID. This makes it virtually impossible for a buggy or malicious client to provide an alternative identifier that is actually valid. If we were building our server in C# this solution would probably be very tempting, as both the generation of GUIDs, and the necessary dictionary lookup would be implemented by the platform. But at what cost? How well would this satisfy requirements 1-3? Possibly well enough, but it is hard to say without profiling.

A Token Gesture

My solution was to issue a 32-bit integer identifier, or ‘token’, that is composed of two 16-bit values:

struct TokenFields {
 
      uint16 saltId;
 
      uint16 dataId;
 
  };

The saltId is essentially an index into a table of random salt values. The dataId is a value that, once XORed with the salt value, produces an index into a table of gameplay data pointers. So, the algorithm to recover the gameplay data associated with a token looks like this:

Data* GetData (uint32 token) {
 
      const TokenFields& fields(*(TokenFields*)&token);
 
      const uint16 saltValue = SaltTable[fields.saltId];
 
      if (!saltValue)
 
          return 0; // invalid token
 
      const uint16 dataIndex = fields.dataId ^ saltValue;
 
      if (dataIndex > Capacity)
 
          return 0; // invalid token
 
      return DataTable[dataIndex];
 
  }

Creating a new token is a very simple process:

uint32 GetToken (Data* data) {
 
      const uint16 saltIndex = GetRandomUnusedIndex(SaltTable);
 
      const uint16 saltValue = GetRandomSaltValue(); // [1..65535]
 
      const uint16 dataIndex = GetRandomUnusedIndex(DataTable);
 
   
 
      SaltTable[saltIndex] = saltValue;
 
      DataTable[dataIndex] = data;
 
   
 
      TokenFields fields;
 
      fields.saltId = saltIndex;
 
      fields.dataId = saltValue ^ dataIndex;
 
      return *(uint32*)&fields;
 
  }

This effectively provides a sparsely populated 48-bit address space, 16-bits from each half of the token, and 16-bits from the salt table.

Additional Security Measures

We may want to detect and defend against attempts to spoof other users’ tokens by brute force generation of all 2^48 possible values. Such attempts could be significantly delayed if we were to temporarily decline further requests from any IP that made a request with an invalid token. Most invalid tokens will cause GetData() to return zero, however the right combination of bits could still produce a valid dataIndex without being a valid token. To detect this case, we can check the token submitted by the client against the token that was issued for that data. This is trivial if we store the issued token alongside the data.

The Code

I’ve provided a first draft of my YMMV. Please leave a comment below if you love it, hate it, or would like to point out some major design flaws!

Until next time, happy coding!