A leader should be selected by randomly choosing one of three parties A, B and C. The parties use the following protocol:

$A → B: N_A$ (where $N_A$ is a nonce)

$B → C:$ $N_{AB}$ $= N_A$ ^ $N_B$ (where $N_B$ is a nonce, and ^ is the ex-or operation}

$C → A:$ $N_{ABC}$ $= N_{AB}$ ^ $N_C$ (where $N_C$ is a nonce) ( Now both A and C know $N_{ABC}$)

$A → B$: $N_{ABC}$ (Now B knows $N_{ABC}$, too)

( Each of the three parties can now compute $p = N_{ABC} mod 3$, where $p = 0$ denotes A, $p = 1$ denotes B, and $p = 2$ denotes C ).

Discuss the security of the protocol and establish if and how is it possible for some of the parties to deterministically choose the leader, being the others not aware of the fraud.

Then fix the protocol too.

I am training with security exercises, but I don't know how to approach to this. Can you give me some help?

  • 1
    $\begingroup$ I'll give you a clue - Whenever you have a protocol where parties do not commit to their votes, but see them in the clear, the last actor has an un-fair advantage over the others. Why? $\endgroup$ – yacovm Jan 12 at 9:38
  • $\begingroup$ Well hence I suppose that, in this case, C can choose a nonce $N_C$ in a way that $N_{ABC}$ will output himself as leader, since he is the first to compute the final nonce. Am I right? $\endgroup$ – bruce_springsteen Jan 12 at 10:14
  • $\begingroup$ Yes. Now what can we do to prevent this? Hint: read about commitment schemes $\endgroup$ – yacovm Jan 12 at 11:17
  • 1
    $\begingroup$ Could this be a fix? Using crypto hashing function, A sends to B and C the hash of his nonce, B and C do the same. Then all of them send to the others own nonce in clear, so now they can check the truth of the previous messages. But in this case do the XOR operations affect in some way my fix? Should I change something more? I mean, can I "ignore" the XOR until all the parties have all nonces in clear, so then they apply the XOR? $\endgroup$ – bruce_springsteen Jan 12 at 11:40
  • 1
    $\begingroup$ yes but you need the nonces to be big enough, say - 32 bytes. $\endgroup$ – yacovm Jan 12 at 13:50

Browse other questions tagged or ask your own question.