Card Playing Protocol?

Something that frustrates me in fighting about crypto issues is the
amazing quantities of ignorance available on the subject.  I wish
people knew more.  Yes, if they understood how a meet-in-the-middle
attack works that would be nice, but I would settle with something far
simpler:
 
It would be really nice if people had practical experiance *using*
cryptography in a friendly, innocent, and non-threatening way.
 
Familiarity breeds comfort.
 
How to do this?  What about a multi-player game which requires
cryptography to implement the play?  One possiblity would be a
cryptographic implementation of playing cards.
 
This has very obvious and easy to understand graphical
implementations.  So simple a small child can easily understand the
product--which means possibly even the ITAR police would get the
concept.
 
This "digital deck of cards" would be flexible enough to allow the
playing of most card games with the addition of the same manual
book-keeping as is needed with physical cards.  For assistance in
keeping score, bidding--or God forbid--betting, there would be a
journaled, low-bandwidth communication channel which would be--very
important here--in the clear.
 
The digital cards would be cryptographically strong.  
 
Players would appreciate that cheating could be accomplished by
cracking the codes, and yet no one seems to be able to cheat.  (Note,
cheating through collusion in a game like bridge would still be
possible.)
 
The cards would not be suitable for distributing porn, bomb making
secrets, or drugs, yet would drive the ITAR police *crazy*.  What if a
deck of the these cards were to be illegally exported from the
country?!?!?  Try telling all those Regular Citizens who are getting
on the net and discover they can play cards that the cards are
dangerous munitions.  What a wonderful way to make the ITAR police
look completely silly.  Oh, and to be sure they *do* get upset, make
the cards just open enough that they *do* constitute something more
general-purpose.  (Make calls to PGP, or let others make calls to the
crypto functions in the digital cards--something like that.)
 
 
Comments?  Suggestions for a game other than cards that would be
better or more suitable?  

Is anyone already working on a Card Playing Protocol?
 
 
-kb, the Kent who tries to cause trouble


--
Kent Borg                                                  +1 (617) 776-6899
kentborg@world.std.com                                
kentborg@aol.com                                      
          Proud to claim 32:00 hours of TV viewing so far in 1994!

Kent Borg writes:

> It would be really nice if people had practical experiance *using*
> cryptography in a friendly, innocent, and non-threatening way.
>  
> Familiarity breeds comfort.
>  
> How to do this?  What about a multi-player game which requires
> cryptography to implement the play?  One possiblity would be a
> cryptographic implementation of playing cards.

By the way, someone was proposing a crypto game some months back. I
don't recall who it was (speak up!), but the notion was floated.

An obvious problem with crypto card games is this: what does it
provide that is worth the extra effort of doing encryption?

This simple question of benefits vs. costs is often the showstopper in
deployment of crypto. The nonuse of Magic Money/Tacky Tokens lies, I
think, in the hassles of using it not providing tangible benefits over
ordinary cash.

When I play cards--which I admit has not been for many years--I play
to play, not to do crypto. I suspect most ardent card-players would be
even more adamant about this.

Find a _reason_ to use crypto in games, and you may have something.
(What might this be? Illegal gambling is an obvious possibility that
could "incentivize" folks. A lot of infrastructure would be
needed...digital money, much better remailer security than anything we
now have, etc.)

Until a reason exists, few people will jump through hoops imposed by
someone else. Give them a reason to use crypto, not just an excuse.

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."

What I suggest you do is you build something that can be telnetted into.

Say, something that would sit on a specific telnet port that people can telnet
into.  When they do, another copy of the poker (or whatever game) process is
forked into existence, and all of these processes can talk to each other
to pass on the deck encrypted in some form or other.

From what I remember off the top of my head:

  You have to use a cypher which allows each card to be doubly encrypted and
decrypted without decrypting both encryptions:

  1.  Card encrypted by player 1:   E1(Card,eK1)
  2.  Card encrypted by player 2:   E2(Card,eK2)
  3.  Card encrypted by player 1, then encrypted by player 2:
                                    E2(E1(Card,eK1),eK2)

Now, whatever you do, player one must be able to decrypt his encryption from
step 3 above.  That is he should be able to take: E2(E1(Card,eK1),eK2) and
decrypt it with his key giving E2(Card,eK2) as follows:

      D1(E2(E1(Card,eK1),eK2),dK1) = E2(Card,eK2)

Where E1(card,key1) means encrypted by Player 1 with his key, and eK1 means
Player 1's encryption key; D1() means decrypt by player 1 with his decryption
key dK1, etc.

You can take any cypher you like and make it into a random number generator
by putting it in a feedback mode which doesn't encrypt, but rather just
generates numbers (I forgot the name of this mode, but it's one of the DES
modes that's commonly used for communications which is immune to noise.) This
mode is built so that both sides use this sort of generator and simply XOR
the plaintext with the generated data to produce the cyphertext, and the
receiver XOR's the generated code of his generator with the received
cyphertext.

Anyway, what I'm getting to here is that XOR (exclusive OR, the ^ operator in
C) will allow you to meet the above requirement:
D1(E2(E1(Card,eK1),eK2),dK1) = E2(Card,eK2) so as to be able to implement the
card playing protocol.

An analogy to this is a box that has two pad locks on it put in such a way so
that the owner of one lock can remove that lock without having the other owner
remove his first.

Basically the two players pass an encrypted deck to each other.  Off the top
of my head (please check this!) both players encrypt the deck of cards.  
Alice and Bob are our players.  So Alice picks her hand, but since they are
still encrypted with Bob's key, she can't see what she's picked.  She passes
her picked hand to Bob.  He decrypts the hard with his key and returns it to
Alice.  Since this had was encrypted by Alice, Bob can't reveal it by decryption

Then Alice decrypts her hand and holds on to it.  She then passes the whole
deck (except for her hand) to Bob.  He picks his hand, sends it back to Alice,
she decrypts his hand and returns it to Bob.  He decrypts his hand and keeps
it, then passes the deck back to Alice.

When Alice needs to pick a card, she has to pass it to Bob to decrypt, etc.
And that in a nutshell is how the protocol works.  Since both sides see that
all the cards are there, they can verify that no one has cheated.  Since
neither side can see the other's cards, the game is safe.

I don't recall what you do with discarded cards... maybe mark them as such?

Also here's something else out to help you:

// shuffle the deck routine:
cardtype   cards[4*13+2]; // four suites of 13 cards + 2 jokers.

//initialize the deck:
for (i=0; i<=4*13+2; i++) cards[i].cardnumber=i;

//shuffle the deck:
for (i=0; i<=10000; i++)
 {
  c1=rand() % (4*13+2);
  c2=rand() % (4*13+2);
  swapcards(&cards[c1],&cards[c2]);
 }


You still have to define what the cards structure is, but I suggest you put
in plenty of information in them such as a discarded flag, maybe a player's
ID in which hand this card lives (if you pass the whole deck instead of the
unused cards), flags to indicate which players encrypted this card, etc.

The two for loops above work to build a deck for you in the best possible way.
The 1st, initializes the deck in order..   The second shuffles the cards
by swapping two at a time.  These functions are far more efficient for
shuffling/building a deck of cards than by picking a random number for a card
ID and checking to see if we've already seen it.


Also, I would add functions in to automate the game, be it Poker, or 21, or
whatever....  Ie: allowing the players to decide what's wild, automatically
checking each player's hand and telling them their hand, allowing for a card
split in Blakc Jack, etc.

If you like I can see if I can find some sources to card games for you...

A deck shuffling method was presented:

   //shuffle the deck:
   for (i=0; i<=10000; i++)
    {
     c1=rand() % (4*13+2);
     c2=rand() % (4*13+2);
     swapcards(&cards[c1],&cards[c2]);
    }


I continue to be amazed at how few people know an algorithm to
generate a truly random permutation efficiently.  There's one (due to
Parnas, if I remember correctly) which generates each of the 52!
possible permutations with equal probability, runs with exactly 52
loop iterations (i.e. a 200 time speed up over the above), and is
provably correct by a simple induction.

Assume random(x) returns a random integer between 0 and x.

a[ 0 ] = 0 ;
for ( x = 1 ; x < N ; ++ x ) {
    i = random( x ) ;
    if ( i == x ) {
	a[ i ] = i ;
    } else {
	a[ x ] = a[ i ] ;
        a[ i ] = x ;
    }
}

Proof is left to the reader.  (Hint: use induction on N.)

Eric

Eric Hughes said:
> I continue to be amazed at how few people know an algorithm to
> generate a truly random permutation efficiently.

The slowest one I've seen in code is "pick at random until you
get an unchecked element; select it and check it off."  What's
worse is how many people know algorithms that they *think*
generate true-random permutations, but which don't.  They are
sometimes good approximations in practice, but it irks me.

1. Assign a random tag to each element.  Sort on these.
2. The one you responded to: do a large number of swaps.
3. Sort, using a random bit generator as a comparator function.
   (This one is actually in Schneier.)

Why?
1. Tag collisions.
2. Asymptotic at best.
3. Counting argument.

Elaboration is left as an exercise, etc. etc.

   Eli   ebrandt@hmc.edu