A secure dice protocol for JGammon

There are to parties in this game, that might not trust each other. So if it comes to throwing the dice, it is not sufficient for the rolling party to say "I got 6 and 6" for the other party will not believe this. And the sceptic does have a point here, as the opponent may announce any value that he or she likes.

In order to solve this problem, a symetric protocol has been designed to negotiate the values of the dice.

Representation of the dice

A pair of dice, each ranging from 1 to 6, has got 36 possibilites of appearance. (1,2) is not the same as (2,1). So all possible throws can be enumerated from 0 to 35. It thus suffices to negotiate an integer number N, 0 ≤ N < 36.

Cryptographic Hash Functions

In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. A hash function takes a long string (or message) of any length as input and produces a fixed length string as output, sometimes termed a message digest or a digital fingerprint.

from Wikipedia on cryptographic hash functions. See there for more information.

The protocol

The used hash function is called SHA. SHA(x) denotes the fingerprint produced by SHA for the message x. 

PARTY ONE                       PARTY TWO

r1:=random 64bit value          r2:=random 64bit value

send SHA(r1)     ---->          <----   send SHA(r2)
s2:=receive SHA(r2)<--          -->     s2:=receive SHA(r1)

send r1          ---->          <----   send r2
r2:=receive r2     <--          -->     r1:=receive r1

verify s2=SHA(r2)               verify s1=SHA(r1)

      for both:
        DICE :=  (first_byte(r1) + first_byte(r2)) mod 36
  1. First each party choses a arbitrary 64bit value
  2. Each party creates the fingerprint of this random message
  3. and sends it to the opponent and receives the opponent's message (symetric protocol!)
  4. After having received the fingerprint, each party unveils its secret random number
  5. Each party can verify that the fingerprint belongs to the secret.
  6. from both secrets that are now known to both players they can easily deduce a dice value by adding and modulo-calculation

After they have sent the fingerprint, no player can change his secret any longer, but the other cannot unveil it, too. So provided that SHA is safe, this protocol negotiates an equally distributed value between 0 and 35.

And if one or both parties want to betray, they will not be able to influence the result.

Details

The random value is not completely random: The first byte should (but doesn't have to) be between 0 and 35 to have equal probabilities for all throws.

Adding a value to an equally distributed random-number generates an equally distributed random number (convolution)