Many years ago the the role-playing game Diablo suffered terribly from cheaters. People would play in groups on the Internet only to find themselves up against players who were invulnerable to damage or who had the ability to kill their characters without even touching them. Many players simply stopped playing because of all the cheating going on online. Although it was available at the same time and operated on the same hardware and operating system, the first person shooting game Quake had no such problems. The best cheats that crackers were able to come up with involved seeing through walls or helping them aim when they shot, hardly on the same scale as an unkillable enemy who can murder you with a glance.
The reason Diablo suffered so badly while Quake had very few incidents was simple, it was written as a peer-to-peer game and Quake was client-server oriented. In a peer-to-peer model, lots of important data was on the player's machine where it could be changed and that was just too much temptation for some people with enough technical knowledge to be dangerous. With Quake, the server made decisions about who shot who and how much damage was done so a user couldn't alter data to heal him/herself instantly or kill another player without striking him. Any attempt to do so would automatically be corrected by the server which kept track of how much damage everyone had really taken.
So what can we do to prevent cheating in our game? That is, what would prevent someone from peeking at all the cards in memory to see which ones will be dealt next or even changing the identity of cards, sending an ace of hearts back into the deck and taking a king of clubs in order to complete a straight flush? How would the other player even know? One solution would be to make the game client-server but that has major drawbacks. Who is going to run servers for the game and why? Can the third party running the servers be trusted too? So what we want is a way to have peer-to-peer play but also have security that prevents cheating.
It may surprise you, but playing a fair game of "mental poker" (two parties using a virtual deck of cards) is actually a well-known problem in modern cryptography. It shows up in books like Applied Cryptography and has been tackled by no less than Rivest, Shamir, and Adleman (perhaps RSA rings a bell when you think of encryption).
Their method for a fair mental poker is best explained with a physical analogy. Imagine that Helga takes 52 cards and puts each one in a separate opaque box. Then she puts 52 padlocks (which all use a single key she possesses) on the 52 boxes before mixing them up and sending them to Franz. Franz now remixes the boxes and selects five for himself and five for Helga. Before sending the ten selected boxes back to Helga he adds his own padlocks to the five boxes intended for him. When Helga gets the boxes she removes her padlock from all ten and ships back the five which still have Franz's lock on them. She can now open her own five boxes to find out what her hand is and Franz can unlock the five boxes he just received which now only have his lock on them. The cards are now shuffled and hands have been dealt without anyone knowing the contents of anyone else's hand. Because the cards he has are locked up and their identities are unknown to him Franz will act as dealer for the remainder of the game.
Since I already mentioned cryptography I'm sure you have figured out that the boxes are the data structures for each card and the locks are implemented with encryption. However, one thing you might not have noticed is that at one point in the protocol Helga has locked (encrypted) a card and then Franz re-encrypted it before sending it back to Helga and she was able to remove her layer of encryption without affecting Franz's! This requires the encryption system to be commutative (i.e. Encryption1(Encryption2(X)) = Encryption2(Encryption1(X))), a property which RSA's public key encryption happens to possess.
Unfortunately, RSA is kind of overkill for what we want to do so we'll go with the much simpler RC4 encryption which also supposedly has the property of being commutative and see if we can make it work instead.
We've already talked about Model-View-Controller as a design choice for our game. And the model is what UberCard is really all about. It has cards, card groups, coins, dice, counters, etc. that describe a typical card game. Keeping track of those objects and their state would be pretty easy using just the collection classes that Java provides except that we want a high level of security in the model to prevent cheating. Because of that and because I was convinced fairly early in my design process that the security requirements would require a lot of changes to the model I decided I would design those requirements in from the very start.
For every object that exists in the model, like a coin or card group, there is a corresponding object in the model on the opponent's machine. However, that does not imply that the two objects are simply a clone of one another. For example, Franz may have a card group which consists of a list of cards. Helga's card group will not have the same list but will instead have only a count of the cards in the group.
Each card in Franz's list is an object that contains a reference to a "master" card from the list of all cards that the model keeps. All of the card references in the list have been encrypted using a key known only to Helga to ensure that Franz cannot "peek" at the cards in the list. If we are playing a game where there can be multiple copies of the same card in a card group (e.g. the card shoe for Blackjack often contains multiple decks shuffled together to make card counting difficult) then a random salt value will be prepended to the reference number. In most encryption systems those random bytes will alter the bytes that come out of the encryption for the trailing reference (the example later in this chapter will make this clearer). This is important so that two encrypted references in the list cannot be compared to discern if they refer to the same card.
when taking a card off of the deck there are four different ways to treat that card:
The card on Franz's machine is encrypted using Franz's key and transmitted to Helga. Helga's card group uses Helga's key to remove Helga's encryption from the card and it transmits the result back to Franz. Note that Franz's encryption is still on the card so Helga still has no idea what the card is a reference to. Once Franz's card group receives the card back it can remove its layer of encryption from the card and an unencrypted card is available through the model on Franz's machine.
Should Franz ever transmit the unencrypted card to Helga to "reveal" it, the unencrypted card and the encrypted card that Helga has can be stored off and compared later when Franz reveals the key that he used througout the game.
Same scenario as above except that the card is automatically transferred over to Helga after Franz removes the last layer of encryption. Helga will need to store off information to compare the encrypted and unencrypted cards later to ensure no shenanigans took place on Franz's side (e.g. Franz decrypts a two of hearts but has hacked his copy of the program so he can show a king of diamonds to Helga).
This is the same as simply moving the card from one card group to another. No encryption or decryption is necessary.
The card on Franz's machine is sent directly to Helga where it is then decrypted with Helga's key. If cheat checking is going to be done at the end of the game then Franz should store off a copy of the encrypted card for later comparison because he's just trusting Helga when she shows it to him.
Let's look at some source code that tests the RC4 in the Cryptix library for compatability with our algorithms. In order to determine if you could encrypt something with key K and then key H followed by decryption by key K and then key H in that order I added the following additional function to the Cryptix library's TestRC4.java file:
private void test3() throws Exception {
String key1 = "0123456789ABCDEF";
RawSecretKey raw1 = new RawSecretKey("RC4", Hex.fromString(key1));
String key2 = "7820902398479ACA";
RawSecretKey raw2 = new RawSecretKey("RC4", Hex.fromString(key2));
String plaintext = "7494C2E7104B0879";
out.println("plaintext: " + Hex.dumpString(plaintext));
// Encrypt using first key 1 and then key 2.
alg.initEncrypt(raw1);
byte[] output1 = alg.crypt(Hex.fromString(plaintext));
out.println("output1: " + Hex.dumpString(output1));
alg.initEncrypt(raw2);
byte[] output2 = alg.crypt(output1);
out.println("output2: " + Hex.dumpString(output2));
// Decrypt using first key 1 and then key 2.
alg.initDecrypt(raw1);
byte[] output3 = alg.crypt(output2);
out.println("output3: " + Hex.dumpString(output3));
alg.initDecrypt(raw2);
byte[] output4 = alg.crypt(output3);
out.println("output4: " + Hex.dumpString(output4));
out.println("\nTest vector 6:\n");
compareIt(output4, Hex.fromString(plaintext));
}
Here's the output from that function:
plaintext: 7494C2E7104B0879 output1: 0000000000000000 output2: 3C1C6FA598539F10 output3: 4888AD4288189769 output4: 7494C2E7104B0879
Sure enough, everything worked perfectly. The output showed that the output is different after each of the encryption/decryption steps and the output of the last decryption is exactly the same as the input to the first encryption. That tells us that we will be able to use the RC4 to handle our fair card dealing algorithms.
Another test will tell us if we can simply prepend a random "salt" value in front of the data we want to encrypt in order to mask it or if we need to actually alter every byte of the data using the salt value before encryption to keep it from being identical to other data with the same value.
private void test4() throws Exception {
String key1 = "0123456789ABCDEF";
RawSecretKey raw1 = new RawSecretKey("RC4", Hex.fromString(key1));
// Encrypt using key 1. Note that both strings are the same except for
// the salt value in the first byte.
alg.initEncrypt(raw1);
byte[] output1 = alg.crypt(Hex.fromString("257494C2E7104B0879"));
out.println("output1: " + Hex.dumpString(output1));
byte[] output2 = alg.crypt(Hex.fromString("447494C2E7104B0879"));
out.println("output2: " + Hex.dumpString(output2));
}
And some output from this test:
output1: 51E05625F75B4371 74 output2: 0FA1C7F0680EB793 63
As you can see, the results are completely different for the same two values even if only one byte at the beginning is different. So before encrypting two references to the same card we can simply add a short random salt value to the beginning of the reference and the results will be completely different. After decryption we will always strip off the salt value and be back to our reference.
A fair coin flip is executed millions of times worldwide every day. One player tosses a coin in the air and covers the result immediately. If the second player can guess the result of the toss he "wins". In our case we are going to alter this just a little bit to say that the results of the toss is heads if the second player guessed correctly and tails if she guessed incorrectly.
Franz will generate a random encryption key and a single random number that is either zero or one. That number will be transmitted to Helga who will make a guess as to whether the number is zero or one. After that Franz reveals his key and both sides can compare the number to the guess to determine whether the coin was in fact heads or tails.
Here's a UML sequence diagram showing the order of things:
We will implement a fair die roll using the same basic technique as the fair coin flip. One side will put our choices in order and the other will pick one at random. Then the result will be confirmed immediately.
In our example we can imagine that we are trying to simulate a common six-sided die roll. The model on Franz's machine will randomly order the numbers one through six, create a random encryption key which is stored, and then used encrypt the ordered numbers. The encrypted set of numbers will be sent to Helga's die where a random value between one and six will be created and sent back to Franz. After that Franz can reveal the one time use key and both Franz and Helga can see which one of the six randomly ordered items was chosen.
Franz cannot cheat and attempt to order the results in any particular fashion because Helga is going to pick randomly from the set of items presented to her. He also cannot reorder the list of numbers after the fact because Helga will check the result using the encryption key after he reveals it. Helga cannot cheat because the numbers available to pick from could be in any order and the order cannot be discerned because of Franz's encryption.
Here's a UML sequence diagram showing the order of things:
Cryptix gives us a wide variety of encryption/decription/authentication algorithms.
The number one site for game development.
Home of the author's weblog and all his projects (including this one).
Bruce Schneier's book is a great overview of encryption and its applications. He mentions protocols that can be used for all sorts of situations and includes the ones mentioned above.