1
$\begingroup$

Alice and Bob are playing Rock-paper-scissors.

Alice chooses $a \leftarrow\{stone, paper, scissors\}$ and a nonce $R_A$ used as symmetric key for encryption

$$A → B : A, R_A(a)$$

Bob chooses $b \leftarrow\{stone,paper, scissors\}$ and nonce $R_B$

$$B → A : B, R_B(b)$$

$$A → B : A, R_A$$

Now Bob decodes $R_A(a)$ and knows a and so he knows who is the winner

$$B → A : B, R_B$$

Now Alice decodes $R_B(b)$ and knows $b$ and so he knows who is the winner

What are the possible fraudulent behaviours the players could engage in?

$\endgroup$
10
  • 2
    $\begingroup$ What do you mean by the second $A$ in A -> B : **A**,R_A? (actually I'm not sure I got the entire notation right, so please add a note explaining that) Also take a look at commitment schemes. $\endgroup$
    – rath
    Feb 4, 2014 at 19:06
  • 2
    $\begingroup$ What do you think? What have you tried? We prefer you to make an effort on your own before asking. This is a nice exercise, but we're not here to solve your exercises for you -- on the other hand, if you have a specific question about a specific aspect of your attempt at a solution, that might be more suitable for this site. $\endgroup$
    – D.W.
    Feb 4, 2014 at 19:19
  • $\begingroup$ If you want to do some research in this area, look for "cryptographical commitment". $\endgroup$
    – poncho
    Feb 4, 2014 at 19:33
  • $\begingroup$ @rath The second A is a label, the name of the sender. $\endgroup$
    – user11818
    Feb 4, 2014 at 20:36
  • 1
    $\begingroup$ Let's assume that the lengths of the 3 option are the same. When Bob receives the encrypted value of Alice, could he send a value b such that he always wins? $\endgroup$
    – user11818
    Feb 4, 2014 at 20:41

2 Answers 2

1
$\begingroup$

If Alice and Bob use XOR, then Bob can win in every game. For example, Bob select "paper", Alice select "sciss" (let length will be same). After decryption, Bob realize he lost. Then he send to Alice as a key "paper"^Rb^"stone". After XORing Alice finds "stone", so she will think, she lost.

$\endgroup$
1
$\begingroup$

You don't specify your encryption method. To show you why that is important, I'm going to pick a really bad one. Let's say we use a stream cipher to encrypt. "stone" and "paper" have the same length, so we are good there, but "scissors" is longer. So, if Alice chooses "scissors", Bob can see the ciphertext length and know what she picked and choose "stone". Therefore, if Alice chooses "scissors", Bob always wins.

If you pick your encryption method so that the ciphertext lengths are always the same, this attack is mitigated.

Bob, once he knows whether or not he wins, could refuse to send $R_B$.

The major flaw, however, is, even if you pick a really good encryption method (say AES-CBC with a fixed length size), you are doing nothing for integrity checking when integrity is really the primary concern here.

The proper way to do this would be to have Alice and Bob each publish a commitment to their choice. Then they open the commitment publicly. This could be done, for example, with HMAC. Choose a random key $k$ and publish $HMAC(k,m)$ where $m$ is the choice. Once both have done this, they can each publish $m,k$. That way they can verify that the choice hasn't changed.

$\endgroup$
2
  • 1
    $\begingroup$ Ok, I understand why it is important to specify the encryption method but maybe the question is more general because later there is another question that asks how to improve the reliability without asking the help of a trusted third party. $\endgroup$
    – user11818
    Feb 4, 2014 at 20:46
  • $\begingroup$ @user11818 updated. You have got to remember, we have no idea who you are. For all I know you know nothing about encryption, which is why I pointed out the obvious problem of using a really bad encryption method. $\endgroup$
    – mikeazo
    Feb 5, 2014 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.