Introduction
The idea behind Socialist Millionaire Protocol is to provide definite answer to the question whether two communicating parties possess the same secret or not in a secure (zero-knowledge) manner. However, given a problem like this, one still has to take care of many implementation details which contribute to the protocol's security properties.
After releasing Secure Comparator paper / PoC code, we've received significant amount of critical feedback: in our github issues #85 and #83 and a number of reddit posts. We would like to specifically thank Mathias Svensson (github user Idolf) and Steve Thomas (github user Sc00bz) and reddit user Scott Contini for pointing out the errors and providing some ideas on to fix it.
The Problem
Zero-knowledge proofs are a particular type of algorithms whose threat model considers not only man-in-the-middle attacks, but cheating participants as well. This was overseen in the initial implementation of our ECC-based socialist millionaire: while the math worked great for honest peers, a cheating peer could trick his counterpart to assuming incorrect protocol outcome, namely that they possess the same secret when in fact they do not. This goes down to the formula described here, p.5:
Rab = (Pa - Pb) + (a3 * b3 * (x - y)) * G2If both parties possess the same secret, then the second term of the equation will be 0 and the resulting check will succeed. However, cheating peers have other means of making that term 0 or even to make Rab == 0 (a known value to them) and faking the protocol outcome. This scenario is possible, if the cheating peer will not behave according to the protocol (that is having some altered malicious implementation), which can produce malicious intermediate parameters exploiting the math behind SMP and changing appropriate values to 0. For example, in terms of our ECC SMP protocol description, suppose Bob is cheating, thus he can subvert the protocol in several ways:
he may choose one of his random values b2 or b3 as zero (or equal to ECC base point order which has the same effect) thus turning one of the resulting shared secrets G2 or G3 to zero. Based on the formula above this will produce the same protocol output, as if x == y even if it is not.
the same effect can be achieved if Bob instead of doing "honest" computations of G2b sends a special weak ECC point (low order point that is). It is not possible with honest computations, because multiplying a "good" point will always result in a "good" point. But here Bob may wish not to do that.
more complex scenario: Bob sends Rb = G and Pb = Pa - G3a and the final check for Alice succeeds, thus tricking her.
We will not present all low-level details here, instead, interested readers may refer to Github repository, where issues were pointed out and discussed (issue #85 and #83), but the point is that malicious peer does not play by the rules (doing incorrect computations).
Solving the problem
So, to be confident in the protocol outcome, we need a way to force our peer to strictly follow the protocol (which prohibits bad parameters by design). Fortunately, original SMP paper and non-ECC based SMP in OTR protocol already have a solution to this: they enforce the protocol by requiring that each exchanged intermediate public value would be complemented by a zero-knowledge proof that it was generated according to protocol (aka zero-knowledge proofs in zero-knowledge proof), for example:
the peer generates a secret parameter (random big number) x
the peer generates public parameter from the above secret to share with her counterpart: P = x * G, where G is our ECC base point, and sends P over the wire
the peer proves to his counterpart that he indeed generated P in the above way and he indeed knows x by generating a random Schnorr signature using x as a private key and sending it over the wire
the counterpart can verify the proof by checking above signature and using P as the public key
The original SMP paper provides description of more complex proofs, where one can prove two or more random secrets in one shot. Apart from the proof described above (which is a base case for proving you know x and P was generated according to protocol) two more proof types are used:
Prover knows some secret x and y and generates a proof that provided intermediate public parameter was generated in the following way: P = x * Q1 + y * Q2, where Q1 and Q2 are some valid ECC points. That is Q1 and Q2 are either known fixed public parameters or previously verified intermediate public parameters. This case allows to prove knowing two secret values at once which are used in a more complex computation scenario.
the prover knows some secret x and generates a proof that provided intermediate public parameters were generated in the following way: P1 = x * Q1 and P2 = x * Q2, where Q1 and Q2 are some valid ECC points as described in the previous case. The point of this case is to prove that the same secret value was used to compute two different intermediate public values (probably, at different protocol stages).
Adapting the solution for Secure Comparator
The only thing left to do is to make those zero-knowledge proofs ECC-aware the same way we did for the original protocol. Luckily, since those proofs are based on a modified version of Schnorr signature scheme and our chosen ECC domain is ed25519 which is an ECC variant of Schnorr signature, we just have to move the operations to ECC domain taking specific ed25519 recommendations into account:
all random numbers should be 32 bytes long with three last bits cleared in the first byte, first bit cleared and second bit set in the last byte
instead of shorter hash functions we use SHA-512
whole output of hash function is used
signatures should be 64 bytes long with first three bits cleared in the last byte
More details?
For specifics, we refer to check a more detailed description in our paper and secure_comparator.c in Themis.
