Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

So, I am conceptualizing a P2P trading card game. The issue is the network: knowing the identity of a card is giving a major advantage, so both clients need enough information about a card that they know it exists, but not so much that the "value" or "specialties" of a card can be determinated.

The basic approach to that is simple: each client has a public and a private key for each card, and to decrypt the card you need all private keys associated to that card.
Whenever a card is played the appropriate key is send over, whenever a card is drawn the other players send the needed keys over.

However there is a issue: the start state is known and from it you could determine which card is which, what makes the whole thing a bit pointless.
How do I shuffle cards over the network so that the client doesn't know the actual end state (without knowing the keys)?

share|improve this question
    
Could you describe your current approach a bit more? What determines the "specialties" of a card? Which key is sent to whom, and when? And how could clients extrapolate the current state from the start state? –  Benjamin Kloster Jul 19 '13 at 12:30
    
Have you tried just sending the random seed used for shuffling instead? Then each client can randomly choose the next card to draw as soon as its needed. This prevents players from being able to "see" the shuffled deck and you don't need all this really complex crypto stuff. Since all clients have the same seed, they will all always generate the same next random number (assuming they all stay in sync, of course). –  kurtzbot Jul 19 '13 at 20:16
1  
I don't think this is possible without a remote server that handles the actual card/deck data. The clients should be dumb terminals in this kind of game. –  Boreal Jul 20 '13 at 12:50
    
Related question, though more general. –  Anko Aug 15 '13 at 12:22

1 Answer 1

You can do this by making the secret starting state verifiable and guesses difficult:

  • Have all players generate a new private/public key pair, send the public keys
  • Let them shuffle their own decks
  • Choose and/or exchange salts (see below)
  • Generate signatures for the information you want to check:

    • Either a player's full deck if that can become known after the game or
    • the individual cards if you want to check after each card is revealed and not make the deck known if not all cards are played

    and send them over

  • Have players choose a seed each to shuffle the opposing decks only. This ensures shuffling takes place with no knowledge (because the key pair was newly created and the cards have not been revealed, but have been "locked in place" by the signature(s))

After this you can use the same methods as a normal card game would use, for example addressing cards by their starting position in the deck or their current position. You need to keep track of the starting position in the hidden (signed) deck for each card, at least until it's revealed.

Depending on what you sign, verification takes place at different times:

  • If you signed the deck, transmit the full deck after the game is over. A cheater will be revealed because of mismatched cards or the signature.
  • If you signed the cards, check whenever one is revealed. The signature won't match if a player tries to cheat.

The strength of this algorithm depends on two assumptions:

  1. Players can't choose a card that matches the transmitted signature.

    This should be inherent in correctly used modern cryptographic algorithms unless the key is chosen maliciously, with known collisions. You can protect against it by letting the opposing player(s) choose salts, which should prevent using known collisions.

  2. Players can't verify the signatures without knowing the cards.

    This part is trickier, as the amount of plain texts is very limited if you sign individual cards only.

    Possible solutions:

    • Add a secret salt for each signature:

      This should not allow players to choose cards unless there is a collision weakness in the signing algorithm. Adding a salt to each card also prevents revealing cards that are the same.

      The salt is stored and revealed when the signature has to be checked.

    • Make guesses more expensive:

      (Checking the signature should already be somewhat expensive, this adds even more computations.)

      This can be done by using a (possibly known) salt and hashing the plain-text multiple times, but is possibly not as secure as the first option when used alone and is not as efficient. It can greatly increase the security together with a secret salt though, as the difficulty is multiplied.

      A side-effect is that it makes finding collisions much more difficult.

    If you want to future-proof the game while making it as fast as possible let the players choose minimums for the secret salt length and hash repetitions that are enforced for all players. You need to cap these when running a verification/leaderboard server though, to avoid a potential DoS.

    You can run verifications in the background to avoid delays, as a failure should terminate the game independently of its current state. (Make sure the transmissions can't be faulty though!)

share|improve this answer
    
+1 Very well thought-out. –  Nathan Reed Jul 24 '13 at 21:30
    
Side note: "verifiable + difficult to guess" can be applied to all situations where secrets have to be "locked in place", so in theory it's possible to create a strategy game with fog of war similarly, signing the partially secret actions as the game goes on and revealing them after it ends, when no unfair advantage can be gained. –  Tamschi Jul 24 '13 at 22:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.