Basically, you have three requirements:
- it should not be easy to use the same key for multiple client instances,
- it should not be easy to generate new valid keys, and
- it should not be easy to steal the key of a legitimate client.
The first part should be pretty straightforward: just don't let two players log into the same server with the same key at the same time. You can also have the servers exchange information about logged-in users, or contact a shared authetication server, so that even using the same key for different players on different servers at the same time will fail. You will also probably want to look for suspicious patterns of key use and, if you determine that a key has been leaked, add it to a list of banned keys.
For the second part, one way is to simply maintain a database of all valid issued keys. As long as the keys are long enough (say, 128 bits or more) and chosen randomly (using a secure RNG), the odds of anyone managing to guess a valid key are essentially zero. (Even much shorter keys can be safe if you use some kind of rate limiting on failed login attempts to stop attempts to find valid keys by brute force.)
Alternatively, you can generate keys by taking any unique identifier and adding a message authentication code (such as HMAC), calculated using a secret master key, to it. Again, as long as the MAC is long enough, the odds of anyone who doesn't know the master key being able to guess a valid MAC for any ID is negligible. One advantage of this method, besides removing the need for a key database, is that the identifier can be any unique string, and can encode information about the client the key was issued for.
One problem with using MACs is that the official game servers (or at least the authentication server) need to know the master key in order to verify the MAC, which means that, if the servers are hacked, the master key might be leaked. One way to mitigate this risk could be to compute several MACs for each ID, using different master keys, but only store one of the master keys on the game servers. That way, if that master key is ever leaked and used to generate fake IDs, you can revoke it and switch to another master key. Alternatively, you could replace the MACs with digital signatures, which can be verified using only the public half of the master key.
For the third part, one approach is to make sure that the client won't send its key to anyone without verifying that the recipient really is a legitimate official server. For example, you could use SSL/TLS (or DTLS) for the login process, issue custom certificates for your game servers and only have the client trust certificates issued by you. Conveniently, using TLS will also protect the client keys (and any other authetication data) from eavesdroppers e.g. on public WLANs.
Unfortunately, this approach won't let third-party servers verify client keys even if they want to. You could work around this by setting up an official authentication server that third-party game servers can make use of, e.g. by having the client log in to the authentication server and receive a random one-time token which they can use to log into the game server (which then submits the token to the authentication server to verify it).
Alternatively, you could issue actual client certificates, or something like them, to your clients. You could either use an existing protocol (like TLS) that supports client certificate authentication (recommended) or implement your own, e.g. like this:
- The client certificate consists of an arbitrary ID string, a public/private key pair and a digital signature of the ID and the public key using the master key.
- To log in, the client sends their ID, public key and signature. The server replies with a unique challenge string (preferably including a server ID and a timestamp, which the client should verify), which the client signs with the private key (to prove that they know the key) and sends the signature to the server.
- The server checks both signatures, proving that the ID + public key form a legitimate client key (since they were signed with the master key) and that the client key actually belongs to the client (since the client could sign the server's challenge with the private key).
(This protocol could be further simplified by having the client generate the "challenge", consisting of a server ID and a timestamp, and sign it. Of course, then the server needs to verify that the ID and timestamp are valid. Also note that this simple protocol, on its own, won't stop a middleman attacker from being able to hijack the client's session, although it will prevent them from obtaining the client's private key needed for future logins.)
