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!
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
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."
participants (5)
-
ebrandt＠muddcs.cs.hmc.edu -
hughes＠ah.com -
kentborg＠world.std.com -
rarachel＠prism.poly.edu -
tcmay＠netcom.com