It's easy to play the classic "Let's Make a Deal" puzzle by email. The host chooses the door that has the prize. Then the player sends a first guess, the host responds, et cetera.
Of course, the problem is that both the player and host can cheat. Either can claim messages were forged, or lost. How can the player prove the host really chose a particular door before the game started?
The answer is to use encryption and authentication. With it, they can eliminate the possibility of cheating.
Both the player and the host must agree on another person to act as a neutral third party (or NTP). This person stores and forwards messages from player to host and vice versa. In addition, this person will perform one more service described later.
All participants (host, player, and NTP) must have an email address and a previously agreed upon public/private encryption program such as Pretty Good Privacy. Each participant must distribute his or her email address and public key to the other participants.
Both player and host must agree on a pseudorandom number generator (PRNG). (One such algorithm is found in Java's java.util.Random class.) The NTP must be able to use this algorithm.
Before the games begin, the host and player must each choose a random number, sign it, and send it to the NTP. The NTP adds these two numbers together and uses the result as a seed for the PRNG.
One game consists of the following steps.
The host chooses a number from 1 to 3 inclusive and creates a message with a first character of 1, 2, or 3. To this he appends some random text*. He encrypts this message with his and the player's public key, and signs it with his private key. He then generates a hash of the message. He signs the hash with his private key, and sends the signed hash to the player and the NTP.
The player chooses a number from 1 to 3 inclusive, appends some random text, encrypts it with her and the host's public keys, signs it with her private key, and sends copies to the NTP and the host.
The host decrypts the player's number, chooses another number, appends some random text, encrypts it with his and the player's public keys, and signs it with his private key. He sends copies of this to the NTP and the player.
The NTP randomly decides whether to switch or stay. It gets the next number from the pseudorandom number generator and takes the lowest bit. If the bit is 0, the message is "stay"; if it's 1, the message is "switch". Random text is appended to the message. The message is then encrypted with everyone's public keys, signed with the NTP's private key, and is sent to the player and the host.
The host sends the message created in step 1 to the player to the player and the NTP. The player decrypts the message to find out which door holds the prize.
At this point, the game is over. The winner is determined by these rules:
If the numbers in steps 2 and 5 match and the message in step 4 was "stay", the player wins.
If the numbers in steps 2 and 5 match and the message in step 4 was "switch", the host wins.
If the numbers in steps 2 and 5 differ and the message in step 4 was "switch", the player wins.
If the numbers in step 2 and 5 differ and the message in step 4 was "stay", the host wins.
The NTP sends copies of all messages to both the player and the host so they can verify the results.
After all games are over (if a series is being played), the player and host send their signed random numbers to each other.
No protocol that uses encryption is complete without an analysis of its vulnerabilities.
The last step (random number exchange) lets the host and player verify the flips generated by the NTP. Each can combine their number with the other to find the seed used by the NTP, and then verify the sequence of bits the NTP sent out.
The NTP can reveal the PRNG seed to either the player or the host, but that can't help either one. If the player knows the sequence of coin flips in advance it won't make a difference, since she still won't know if she's staying with or switching away from the door with the prize. Likewise, this knowledge doesn't help the host, since he has no influence over the door selected by the player in step 2.
The first three messages aren't encrypted with the NTP's public key. Because of this, the NTP can't even tell what doors have been chosen in any step. This keeps the neutral third party completely neutral.
Collusion between the player and the NTP is impossible because neither know which door holds the prize. The host knows, and in step 1 creates the equivalent of a message in a sealed envelope. The hash value of this message is sent to the player in advance so that the player can verify that the door wasn't changed during game play.
Since both the NTP and host have copies of the player's signed messages, the player can't repudiate them.
Collusion between the host and the NTP is impossible because there's nothing to collude about. The only secret that needs to be hidden is which door has the prize, and that's taken care of in step 1. That information is not shared with the NTP until the end of the game.
Since the messages are signed, they can't be repudiated.
In steps 1-4 random text is appended to each message before encryption to defeat replay attacks. Imagine you're the player. At the beginning of the first game you receive a hash value of Tj8U. Later you find out that the prize was behind door 2, and the hashed message was "2". Two games later you receive the hash Tj8U again. This indicates an identical message, hence door 2 holds the prize. Adding random text - "2 wherefore Artivac-6?" - defeats this problem. As long as no unencrypted messages are identical, hash values will be different. Plus, the host and player can send taunting messages to each other.
* PGP's use of different session keys automatically protects against replay attacks. The same plaintext encrypted twice to the same recipient does not produce the same encrypted output, so PGP users can omit appending random text in steps 1-4.
Okay, maybe it's not exactly easy to play this. But it isn't difficult. It just takes some time and effort.
The fair coin flip scheme is from Bruce Schneier's Applied Cryptography, section 4.10.
Last updated 3 June 2000
http://www.rdrop.com/~half/Creations/Puzzles/LetsMakeADeal/PlayByEmail.html
All contents ©1998-2002 Mark L. Irons