Armchair Cryptography
Conversations with a co-worker and recent news got me thinking about writing a peer-to-peer poker program, with no central server. I've already got a rough model for the card game itself written out in Ruby, which I was going to use to practice writing different poker AIs, so "all I need" is an interface, a little networking code, and some crypto to keep things secure.
Cryptography is, of course, Real Hard Stuff (tm), so I'm probably going to mess that part up - smarter people than I have written badly broken crypto algorithms. On the other hand, this is just for fun and noodling around, and I'd like to bone up a little on the math end of security anyway, so I'm going to try to roll my own. Here are my initial noodlings, and if you guys have any thoughts ("OH HAI YOU'RE DOING IT WRONG!"), feedback would be great.
Distributed Random Number Generator
My first thought was that I would need a way for the group of players to agree on random numbers. Ideally, even if all the players but one were in cahoots, as long as at least one player was honest, then no other player or group of players should be able to control or predict the final numbers. (Of course, if nine out of ten players are conspiring against the lone tenth, that guy's screwed anyway, but at least we can make sure his numbers are random!) It turns out I didn't actually need this after all, but it was fun, so I wrote it anyway.
Anyway, my first pass at the RNG is that the number generation occurs in two phases. In the first phase, all players secretly select a number and broadcast a cryptographic hash of that number. Once all the hashes have been broadcast, everybody reveals their secret number, broadcasting those. All the numbers are then XORed against each other, and the result is the random number. Players can verify that hashing the secret number results in the previously broadcast hash.
For hashing, I'm using a base and a large prime that are kept throughout the game (and are, in fact, built in to the algorithm in my implementation). The hash is equal to the base raised to the power of the secret number modulo the prime, or ...
(b ** n) mod p
...where b is the base (5 in this case), n is the secret number, and p is the large prime. This is based on the first part of a Diffie-Hellman key exchange, and in order for the D-H exchange to be secure, this operation must also be secure (in the sense that given the hash, it is difficult to determine the secret number). Since lots of really smart people have not been able to break the D-H exchange, I'm fairly confident in it.
Unfortunately, though, there is a potential problem: if you were able to find a collision in the hashing routine, you would have a hash value with two (or more, I suppose, though that's unlikely) valid secret numbers. This would allow you to submit the "trick hash" in phase 1, then in phase 2 you could wait until everybody had broadcast their secret numbers, and then broadcast whichever of yours resulted in the more favorable random number.
This might be solvable in several ways:
- Choose a different prime each game, since finding collisions is computationally hard and probably not feasible within the context of a single game. How would you choose a random prime before the Random Number Generator had been established, though?
- Find all the "trick hashes" and specifically disallow them. This is probably computationally infeasible for reasonably large primes, though.
- Choose a better hashing algorithm with no collisions, or with inherent random elements like in the first option. This seems like the most promising possibility to me.
Speaking of the other problem with p2p poker...
Face Down Cards
I had initially imagined that any un-dealt cards would simply be in an unordered set, sort of a Schrodinger's Deck, in which the top card would only be determined when somebody actually needed to draw a card. Then, so I thought, you could just keep a public deck of cards and use the RNG to pick a card out of it at random when dealing.
But, that won't work, because players have face down cards - they can see these cards from the moment they get them, but nobody else can know what they are, or draw the same cards later. That means we can't keep an un-encrypted deck. If we did, you could tell what somebody drew just by looking at the deck before and after they drew the card (this seems pretty obvious in retrospect... dur). On the other hand, if you can't see what's in the deck, how do you draw a card from it?
I haven't implemented a solution to this one yet, but I have a general idea that you could assign each card a string (say, "Three of Clubs"), and then pass a list of those strings around the table. Everybody encrypts each card/string with a private key, shuffles the deck/list, and passes it to the next player. At the end of this process, nobody knows what order the deck is in, and each card is encrypted with all ten keys (assuming you have ten players). The deck is now made public. To draw a card, you take one off the deck and pass it to the player in front of the player who's drawing it. The card is then passed around the table, and each player decrypts the card in turn. When the drawing player receives it, the only key left on the card is that player's, so they decrypt it with their key and then have the original text ("Is this your card?"). If a player were voluntarily dropping out of a game, they could just decrypt each card in the deck with their key. New keys would need to be chosen each hand, and the deck would need to be re-shuffled and re-encrypted.
I still need to pick an encryption algorithm. It needs to be commutative, so that the keys can be applied and removed in any order. Also, there's a problem where any player can render a hand unplayable by dropping out of the game without decrypting the deck. That's a fairly serious vulnerability, even if they forfeit the hand by doing so. Several players working together could play very aggressively, safe in the knowledge that one of their compatriots could kill any hand they stood to lose too much on. I'm not sure what the solution to this problem is, yet (which is most of why I haven't coded anything up yet).