Cryptography for P2P card game

Question

I'm considering writing a computer adaptation of a semi-popular card game. I'd like to make it function without a central server, and I'm trying to come up with a scheme that will make cheating impossible without having to trust the client.

The basic problem as I see it is that each player has a several piles of cards (draw deck, current hand and discard deck). It must be impossible for either player to alter the composition of these piles except when allowed by the game rules (ie drawing or discarding cards), nor should players be able to know what is in their or their oppponent's piles.

I feel like there should be some way to use something like public-key cryptography to accomplish this, but I keep finding holes in my schemes. Can anyone suggest a protocol or point me to some resources on this topic?

[Edit] Ok, so I've been thinking about this a bit more, and here's an idea I've come up with. If you can poke any holes in it please let me know.

At shuffle time, a player has a stack of cards whose value is known to them. They take these values, concatenate a random salt to each, then hash them. They record the salts, and pass the hashes to their opponent.

The opponent concatenates a salt of their own, hashes again, then shuffles the hashes and passes the deck back to the original player.

I believe at this point, the deck has been randomized and neither player can have any knowledge of the values. However, when a card is drawn, the opponent can reveal their salt, allowing the first player to determine what the original value is, and when the card is played the player reveals their own salt, allowing the opponent to verify the card value.

Adagietto

would you settle for difficult rather than impossible? – Markitamarkka

I'm sure this is complete overkill - the chances of anyone reverse-engineering the protocol or client in order to cheat are likely miniscule, still I feel like there ought to be a cryptographically secure solution, and I'd like to know what it is. – Adagietto

right, well for sure the source and protocol would have to be kept secret, or someone could easily write a cheat-enabled client. you could use TLS for communication to avoid sniffing the protocol. beyond that, whatever is in RAM or on disk is open to inspection, including any keys to the encrypted data. – Markitamarkka

Have each client sign a contract that legally obligates them to kill themselves if they cheat. Problem solved. – Tetravalent

I don't think this is possible. As with every kind of DRM, security, validation, etc.: The client runs it, the client can change it. If you really want security without depending on a single server, create a server that takes care of everything critical but encourage people to host their own servers. – Leandroleaning

@delnan - I don't think it is impossible although obviously I am unable to offer a stronger proof than my gut feeling. As an analogy, consider giving the client a message signed using PGP - although they can alter the message data, it is computationally infeasible to alter it in such a way that the signature will still pass validation. This is the sort of system I want to implement. – Adagietto

@zephyr: Well, perhaps not impossible. But it would propably add quite some overhead, you'd have lots of headache with searching for (and accommodating to) loopholes, etc. - is P2P and absolute cheating prevention really that important? Also, from my limited knowledge on the topic it seems that, with e.g. PGP, the attacker is not the person taking part in the communication, while in your case an attacker (cheater) controls pretty much half of the data in the game - dunno if this makes a difference. – Leandroleaning

You might get some inspiration from en.wikipedia.org/wiki/Mental_poker – Apicella

@Brian - thanks! This looks like exactly the sort of thing I'm looking for. – Adagietto

@Brian - if you repost as an answer I will accept. – Adagietto

Ah, just had a look at the link @Brian posted and it seems to talk about the same kind of thing that I just added to my answer.. the idea of dynamically selecting the next card each move. – Adrenaline

The scheme in your edit seems workable, clever, and relatively straightforward. Of course, just because I can't see a flaw doesn't mean there isn't one. One nitpick: The random values used in a scheme like yours are called 'nonces', not 'salts'. – Ichor

Answer 1

Your problem is the famous Mental Poker Problem in cryptography (this was one of my favorite parts of crypto-class in college). It is possible, and it has been solved (in part, like all things crypto, by Ron Rivest), as long as you don't mind a huge performance hit.

Check the wiki page for more details.

Internationalist

thanks - this was suggested by Brian earlier but since he only posted a comment, I will accept this answer. One thing I'm curious if you know - how huge is this performance hit? I read that so far this does not give real-time performance for e.g. poker, but it's hard for me to imagine it could possibly be too slow for something so human-input bound as a card game. – Adagietto

@zephyr: The main thing is the bandwidth and latency; where you were once transmitting a few dozen bytes from one server to a few clients, you now have to transfer many kilobytes back and forth several times. Also, the decryption is pretty slow in RSA - a single 1024-bit decryption can take upwards of several ms. Doesn't sound like much, but multiply that by 52 cards, then by several clients, and add latency, and it can start to add up. The best advice I can give is: try it out on a slow network with slow computers, and see if it fits your needs. – Internationalist

I didn't post it as an answer because Mental Poker doesn't exactly match your situation. I've added one now. – Apicella

Answer 2

I want to describe one idea which came into my mind rather quickly. I don't know if it serves all your needs, so please feel free to comment on this.

Assume player A has cards A1, A2, A3, ... from a set represented by numbers 0, 1, ... N-1. These cards might be also separated into piles but this does not change the following.

Instead of handling these cards with a single list [A1, A2, A3, ...] you can instead use two of them [A1_a, A2_a, A3_a, ...] and [A1_b, A2_b, A3_b, ...] where one is with player A and the other with player B. They are generated in such a way, that each one is random (in range 0...N-1) but both are correlated such that A1_a + A1_b = A1, A2_a + A2_b = A2, ... (all operations modulo N).

• Thus no player actually knows the cards without access to the complementary pile (i.e. he cannot reasonably change his cards)
• Whenever you need to know a card both players show their corrresponding value and you add those modulo N
• you can implement things like "draw a card" quite easily, both piles just have to be treated the same way

Sit

@Sit - that is clever, I think you are on to something. It seems to me that there is a possible attack though. If player 2 know what the values of A1 and A2 are (say one card is in their hand and the other they just discarded), then they can alter their values such that A1_b_prime = A2+A1_b-A1, and A2_p_prime = A1+A2_b-A2. I believe this will allow them to swap these two cards? – Adagietto

@zephyr Although I don't have an complete answer at hand it should be possible to handle this with a hash value. Thus any cheating like the one you proposed will be revealed latest after all cards are played. – Sit

@Sit - that sounds feasible, one more question - how would I go about creating the correlated lists in the first place, such that neither player has knowledge of the other list? – Adagietto

Answer 3

The traditional Mental Poker scheme is overkill. Your situation is actually much easier since there is no shared deck. You could do something like this:

Player A takes his cards and encrypts them with key Ka. He sends them to B who shuffles them, encrypts them with key Kb. Each time A wants to play a card, he asks B for the (Kb) decryption of the next one. A decrypts this to find what card he drew. At the end, A and B reveal Ka and Kb and compares them with the game log, which should prevent cheating.

Updated: On reflection, here's a simpler solution: As above, player A encrypts his cards and sends them to B. B shuffles them. Whenever A wants a card, he tells B which deck he's drawing from. B returns the (encrypted) card from the appropriate pile.

Apicella

Answer 4

Maybe the players could exchange hashes of their piles at the start of the game.

Then when the game is complete, the players exchange the actual composition that their piles had at the beginning of the game. Now the player's client can check that it matches the hash they got before and then check that all the moves that were made would work with those decks.

The only problem is how the decks are shuffled initially. You would need to make sure the player cannot just start his deck in any order he chooses.

Maybe have the players generate their initial deck order by getting randomness from some specific source.. but in a way that the other player cannot work out what the other player's deck orders are until the end of the game, but can still check that the player didn't fiddle their decks. Not sure how you could accomplish that.

Edit:

Another idea. Maybe instead of generating the random decks at the beginning of the game, they could be generated as the game goes on.

Each time a player needs to take a new card from the pile, their opponent sends them some random seed that is used to choose what the next card will be.

That way the user has no way of knowing in what order the cards will follow in their decks.

I'm not sure how you would stop the other player from being able to tell what card they would be picking for their opponent. If the seed was used to select a card from some kind of randomly ordered list of the cards that the opponent had a hash of to verify.. they could check all the possible combinations of cards and find out which one matched the hash, thereby being able to dictate which card they wanted the other player to draw by sending them a seed that would cause that card to be selected.

Adrenaline

This would solve the altering problem, but I think it still leaves open the problem that players could inspect their own decks to see what cards they will draw. – Adagietto

Ah, forgot about that vital part of the problem! – Adrenaline

Answer 5

While a central server would probably be the easiest way, if you want to avoid it you could use a distributed system, wherein everybody playing the game is a storage host for other players' decks (not for himself or his opponent, but anybody else). I believe Limewire and Bittorrent both work this way, so you might gain some ideas by studying those sources.

Markitamarkka

This is an interesting idea, although it raises some worries about collusion for me. – Adagietto

sure it's still possible, but less likely since it's not easily apparent whose data you have, and you have no immediate interest in anybody else's game but your own. – Markitamarkka

Answer 6

this is an adaption of Acorns approach:

setup:

each player has their deck (totally ordered set(s) of cards) ... those decks are public and are in natural order

each player needs a asymetric (signing) keypair, public keys exchanged

now to the randomness problem:

since a player may not be able to see in advance what cards they will draw, the opponent will be the source of our randomness:

when we need some random value, we ask our opponent ... random values are stored along with the moves to be checked later

since our opponent may not be able to manipulate the order of our cards, we take that received random value and sign it with our private key ... the value of that signature will be our RNG seed (unpredictable for the opponent), and later the opponent may verify the signature against the random number he/she generated (so we store the signatures too, and exchange them after the game)

since we can do this random number exchange every round, the random values are not known to the player in advance -> no peeking at the order of our stack

and since we now have a seeded RNG we can get random values derived from that "shared" random value ... that way we can draw "random" (completely deterministic, with repeateable verifiable results) cards from our deck ... the deck/pile won't need to be shuffled, since we can get random positions from our RNG

since we have all exchanged random values, the signatures, the initial decks (in total order), and all moves, we can replay the whole game afterwards and check for irregularities

Convexoconvex