Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  rath Feb 4 at 19:06
2  
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. –  D.W. Feb 4 at 19:19
    
If you want to do some research in this area, look for "cryptographical commitment". –  poncho Feb 4 at 19:33
    
@rath The second A is a label, the name of the sender. –  user11818 Feb 4 at 20:36
1  
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? –  user11818 Feb 4 at 20:41
show 5 more comments

2 Answers 2

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(m,k)$ 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.

share|improve this answer
1  
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. –  user11818 Feb 4 at 20:46
    
@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. –  mikeazo Feb 5 at 13:47
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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