Insufficient checks in secure_comparator.c

[TethysSvensson]

As far as I can tell, there are too few checks in secure_comparator.c.

Unless I have misunderstood some assumption about ed25519, then if either Alice or Bob chose rand == rand2 == rand3 == 0, then they would always be authenticated correctly. (I know that generate_random_32 won't choose these values, but an attacker easily could).

According to wikipedia, there is also a possible attack by choosen P or Q based on they other persons P and Q. I do not think the implementation is vulnerable to this based on the order in which you exchange the messages, but I am not completely certain.

[ignatk]

Thank you for your concerns. Could you, please, give a link to the wikipedia page about chosen P or Q? We will examine it more thoroughly.

[TethysSvensson]

https://en.wikipedia.org/wiki/Socialist_millionaire

Specifically lines 4 and 8 in the table.

EDIT: Line 4 and 8, not 3 and 8.

[ignatk]

I do think that above applies to ed25519 as well. Also, we should not rely our security on the order of the message exchange, as it may change in different applications. Thank you for pointing this out.

[ignatk]

Fixed with #84

[TethysSvensson]

I am not sure the patch is enough. For curve25519 there are at least 5 different bad public keys when contributory behavior is needed. It might be as many as 12 though, depending on the implementation.

See http://cr.yp.to/ecdh.html#validate (especially the part about contributory behavior) or https://crypto.stackexchange.com/questions/17704/curve25519-weak-points-for-contributory-behaviour

Note that many implementations ignore the most significant bit in the public key, so the bad keys above 2*255 might not *actually be bad in a given implementation, though an honest implementation would not generate them either.

I am not familiar enough with ed25519 or how it differs from curve25519 to know if the above is also applicable to your use-case. I would however assume that it is, since you can convert ed25519 public keys to curve25519 public keys.

[ignatk]

Since SMP is DH-based, it should be protected from such keys when at least one party is honest (this aligns with statement in http://cr.yp.to/ecdh.html#validate). When both parties are cheating, it makes the protocol useless anyway.

However, since SMP targets zero-knowledge outcome, I will double-check whether weak keys can leak additional bits of information.

[TethysSvensson]

The problem is not leaking additional bits of information, that can never happen in SMP if you follow the protocol correctly. The problem is a malicious attacker authenticating without knowing the secret.

In curve25519, then the attacker can force n * P to 0 against an honest party by choosing P to be any of those values. In the case of SMP this allows authentication, while in DH there is no real additional risk associated with this.

[TethysSvensson]

Doesn't this line also permit a timing attack?

ge_double_scalarmult_vartime((ge_p2 *)&(comp_ctx->Q), comp_ctx->secret, &(comp_ctx->g2), comp_ctx->rand);

[ignatk]

It does. We did not find a good approach to do the above in constant time reasonably fast and without much pre-computations. So far, we hope that even if the attack will be performed, the attacker can measure some combined bits of secret and rand (which is random each time), so he won't get clear information on the secret.