Telegnosis Cryptography

Usually, a programming project needs to have problems that require clever or interesting solutions in order to keep my interest. That’s one of the reasons I have mostly lost interest in the Ichor codebase (though progress also sparks my interest, so I could regain it for a little while). The reason I have been interested in telegnosis for so long is because I have added a design constraint to the project which creates interesting problems where there would otherwise be none.

In all popular multiplayer online games there has been a problem with cheating, especially in open source ones. I’m not saying Telegnosis will be popular (I’d like it to be, but board games usually don’t catch on). Nonetheless, I want cheating to be impossible in Telegnosis. The exact design constraint: it is impossible to write a client or server for the game which is capable of cheating without being caught by another player using the standard client.

The telengosis client currently enforces this in all but one area: time. I haven’t come up with a way to securely record times yet, assuming one is possible at all. I am planning on refactoring the crypto logic out from the rest of the game into a “crypto gaming” module. So, to concretify my ideas, I’ll jot down what I’m doing and what I plan to do in this entry. I hope a cryptologist reads this, so that any flaws in my algorithms can be pointed out.

To enable this kind of cheating checking, I have each player keep a copy of the board and what every other player is doing. This way, the player can replay the game and make sure all moves were legal. In my refactor, I plan on encoding the rules of the game in a class and having this checking happen in the library.

Move Commitment

The game is transactional, so you must be able to enter a move into your transaction without others being able to tell what it is. However, you must not be able to change the moves already in your transaction, say, if another player moves and you decide your queued moves were not so great. This screams a commitment scheme. Every move structure has a string-describe function which generates a string guaranteed to be identical to another if and only if it represents the exact same move. For example, a move for player 1 from node 6 to node 7 is represented by “M1:6:7″. Then, ten characters of random salt is appended to this string and stored in the structure. Finally, it’s MD5 hash is taken and echoed to all other players through the server. When a transaction is committed, all moves along with their salts are echoed to all other players, which verify that the hashes match the actual moves. To break this scheme, you would need to find a short collision (on the order of 16 bytes, for a 16 byte hash, there might not even exist a collision) in MD5 or you would need to search 6410 = 1018 hashes per possible move. Adding more salt would make it harder to decode sent hashes, but easier to find hash collisions and change your move after-the-fact.

Alliances

I don’t have alliances implemented yet. In order to ally, you want to share your current transaction with your allies but not your enemies. It should be fairly obvious how to do this: RSA.

Random Numbers

I’m thinking of adding a random element to the game. We need a secure way to generate random numbers, such that no player knows in advance what the random number will be, and no player has control over what random number is generated when it is generated, even if the player is colluding with the server. The solution is again fairly obvious. Say you want to generate a random integer mod m. You ask each player to generate a random integer mod m and publish a salted hash as above. After all hashes are recieved, you ask each player to reveal his number. The hashes are checked, then all of the numbers are added mod m and that is the resulting number. I worry that while you cannot affect the exact number generated, you might be able to affect the distribution by assuming that other players will generate uniformly-distributed numbers. I’m not sure that that is actually possible, however.

Standard Crypto Stuff

And, as anything, the game is susceptible to man-in-the-middle attacks, especially if the server is not trusted. I don’t really feel that it is necessary to solve this problem for a game like this, unless, of course, there are rated tournaments and such. The solution is obvious, of course. Sign every transmission with a known public key (or sign a digest of all transmissions after the game, if bandwidth is an issue).

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s