Thursday, December 9, 2010

Rock, Paper, Scissors over email

This is just to get this off my chest. During the AI contest, I wanted to create a P2P way for two players to play a match, and keep it fair. The Planetwars game had simultaneous moves, so I wanted a way that the players could each make a move at the same time without requiring one player to send a move in the clear to the other first.

This was mostly an exercise for fun, but I thought it may be useful for people to play each other online for testing. Since then, several players, McLeopold in particular, have worked on making it easier for people to host a game server of their own. Hosting a server to play against a friend would be far easier than fully implementing my idea.

The method I wanted to use was based on commitment schemes, where each player could commit to their choice before sending it in the clear. I learned about this idea in Bruce Schneier's Applied Cryptography.

The idea would be that the players could negotiate a map choice, then play out the game. On each turn, the players would

  • pick their move
  • create and send a commitment string based on the move
  • wait to receive the opponents string
  • send the cleartext move
  • verify the commitment string
  • repeat

Implementing this might be fun, but I have other projects I want to do first. But, I have talked about this too much to just drop it. So, here is some code to demonstrate.

There are plenty of security problems with this code. Someone could cheat this with enough effort. There are some simple things that would make this more cheat resistant... but lets get to the details.

Rock, Paper, Scissors

I won't explain the rules here. For a given move, the player will send "rock", "paper", or "scissors".

Creating the commitment string

First, the player picks their move. Then, they pick some sort of random key to use to create a hash of their move using HMAC and SHA-1. (Again, this was for fun. Don't assume anything about the suitability of this idea for any purpose.) The player must also pick a new key every turn, and the key must be something that is unique and unpredictable.

Here is some Python code to create the commitment string.

import hashlib
import hmac

def run_hash(key, message):
    return hmac.new(key, message, hashlib.sha1).hexdigest()

Then, to create the string, we could do something like this:

>>> move = "rock"
>>> key = "different random key every move"
>>> hash = run_hash(key, move)
>>> print hash
84c90d7bec92c41502e1b47b981cb62f74b043ac

Transmit strings

Nex the players trade commitment strings. After each is received, they then trade the cleartext moves and secret keys. Then, each player can verify that the commitment string matches the secret key and move.

Even more

The same idea could be used to pick the maps to use. Given a set of possible maps that both players agree on, one of them could create a commitment string for each map using a secret key. Then, the player could shuffle this list of strings, and send it to the other player. The other player would pick one of the strings, and by doing so randomly chooses a map. Given the secret key, the second player can verify that nothing funny was going on.

Scheier's book has a short section on "telephone poker" that goes even further. The players can deal out cards randomly without knowing what the other got.

So, I am not pursuing this any more at the moment. I wanted to write a client to play one on one matches, but I think the easy to install tcp server is a more practical idea.

No comments: