Project Fairdice
[Home] [Docs] [Users] [Gaming] [Crypto] [Devel] [Download] [Help]

Cryptography : Concepts

One way to reach understanding of why the protocol does things the way it does is to consider a series of increasingly complex protocols, each one fixing a flaw in the last.

The astronomers Dr. Peter Bloggs of Oxford, England and Dr. Harry Fituright of MIT, USA have just jointly discovered an asteroid. Both want to name it after themselves, and neither can agree on a compromise. So they decide to flip a coin. Heads and Harry gets to name it, Tails and Pete gets to choose the name. Unfortunately they don't have time to meet up in person to flip the coin, so they decide to do it over the internet.

Asteroid A

Step 1
Harry, in his office in America, writes down on a piece of paper either the number 1 or the number 0.
Step 2
Harry sends Pete an email to say he has done so.
Step 3
Pete sends Harry an email containing Pete's guess of either 1 or 0.
Step 4
Harry combines the two inputs as follows:
toss = ( Harry's Input + Pete's Input ) modulo 2
interpreting a 0 as a Tail and a 1 as a Head
Harry's InputPete's Input Output
00 0
01 1
10 1
11 0
Step 5
Harry sends Pete an email saying whether Pete has won or lost.
Pete is feeling lucky and agrees to this protocol. Here's what happened: Pete is devastated. And is now not quite sure he trusts Harry. How does he know Harry didn't change what he had written down, after he received Pete's input? So for their next discovery they agree to an improved protocol.

Asteroid B

Step 1
Harry generates his input (0 or 1) as before. This time, though, as well as writing it down, he also calculates a cryptographic message digest of his input using a one way hash algorithm called "Tiger".

Hashes have the property that if message M1 has a digest D then it is very difficult to find a different message M2 that shares the same digest D (called a collision).

Step 2
Harry sends Pete a message saying he is ready for Pete's input, and that the digest of Harry's input is D.
Step 3
Pete sends Harry an email containing Pete's input.
Step 4
Harry combines the inputs in the same way as last time.
Step 5
Harry sends Pete an email saying what Harry's original input was.
Step 6
Pete verifies that the digest of the input that Harry claimed in step 5 matches the digest that Harry provided in step 2.
digest(harry) == hash( input(harry) )
Step 7
Now both Pete and Harry have all the inputs, and can each work out what the outcome is.
This time Pete is delighted to discover that he wins, and the asteroid enters the star catalogs as *** PeteBloggs1 ***

The following month things get a little more complex. Harry's research assistant, Richard Jones, also gets involved in the hunt, and when a new asteroid is found, asks for a say in the naming. Emails go back and forwards, and a shortlist of 6 names is generated.

  1. PeteBloggs2
  2. HarryFituright2
  3. RichardJones1
  4. Asgard
  5. Vanaheim
  6. Muspelheim
They agree that they will, between them, select one of the six outcomes.

Asteroid C

Step 1
Harry, Pete and Richard all generate their inputs (now one of six numbers: 0,1,2,3,4 or 5) and write them down: I(harry), I(pete), I(richard)
Step 2
Harry, Pete and Richard then all calculate the digest of their own input: D(harry), D(pete), D(richard)
Step 3
Harry, who as the middleman who knows the email addresses of both Pete and Richard, has agreed to be the host, and he sends an email to the others saying he is ready for them to send him their digests.
Step 4
P --> H : D(pete)
R --> H : D(richard)
Step 5
H --> P : D(harry)
H --> P : D(richard)
H --> R : D(harry)
H --> R : D(pete)
Step 6
Now that everyone has everyone else's digests, they can all reveal their actual inputs:
P --> H : I(pete)
R --> H : I(richard)
Step 7
H --> P : I(harry)
H --> P : I(richard)
H --> R : I(harry)
H --> R : I(pete)
Step 8
Now all three of them have all the inputs, they can each work out the outcome:
outcome = ( I(harry) + I(pete) + I(richard) ) modulo 6
Things proceed, and it turns out that: 0 + 4 + 3 = 7
7 modulo 6 = 1
thus the new asteroid was named *** HarryFituright2 ***.

Pete however gets a little suspicious. He agreed to provide a digest of his guess, because otherwise Richard would have been in the same situation as Pete had been with Harry over the Asteroid A. But how does he know the hash is secure? He trusts that once Harry has produced his digest, Harry can't change his input. But what if Harry could work out Pete's input from Pete's digest? If he could do that, he could fix the result because Harry doesn't supply his digest (and so isn't forced to choose his input) until after he gets Pete's.

The security of a digest depends on the size of the plaintext (the message) that is fed to it. If there are only 6 possible plaintexts then there are only 6 possible digests, and you can easily create a lookup table to map from digest to plaintext.

However a balance is needed. You don't want to have to generate too many random bits each time, as it is an expensive operation. They agreed on changing from:

plaintext = input
plaintext = sharedtext + usertext
sharedtext = hostid : gameid : timeid :
( usertext ) modulo numberOfOutcomes = input
0 <= usertext <= ( ( 2 ^ 64 ) - 1 )

Asteroid D



Step 1
P0 --> Px : sharedtext
This signifies the game is open
Step 2
Px --> P0 : Dx
This signifies a user wishes to join the game
Step 3
P0 --> Px : You are player X
This signifies the digest was accepted
Step 4
P0 --> Px : N
This signifies the game is now closed to additional users
Step 5
Px --> P0 : request D0..N
This can be repeated to allow for failed transmisisons
Step 6
P0 --> Px : D0
P0 --> Px : D1
P0 --> Px : D2
Response to the previous stage
Step 7
Px --> P0 : Ux
The user is happy they have enough digests
Step 8
P0 --> Px : outcome
Step 9
Px --> P0 : request U0..N
This can be repeated to allow for failed transmisisons
Step 10
P0 --> Px : U0
P0 --> Px : U1
P0 --> Px : U2
Response to the previous stage
Step 11
Px --> P0 : no more requests
Game is over / outcome verified.



TIGER/192 was chosen over MD5 as the message digest algorithm as doubts have been raised about MD5's collision resistance.
The Tiger home page is:
For further information on hash functions see: