Re: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE, CPACE, J-PAKE)

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

From: Watson Ladd <[e-mail]>
hhhhhhhh
On Fri, Sep 6, 2019, 8:03 AM Scott Fluhrer (sfluhrer) <[e-mail]<mailto:[e-mail]>> wrote:
SPAKE2
Documents reviewed:
Original SPAKE2 paper: www.di.ens.fr/~pointche/Documents/Papers/2005_rsa.pdf<http://www.di.ens.fr/~pointche/Documents/Papers/2005_rsa.pdf>
SPAKE2 draft: https://tools.ietf.org/html/draft-irtf-cfrg-spake2-08
The first issue with SPAKE2 is that it is backdoorable (in the same sense that the DUAL-EC DRBG is backdoorable).  That is, SPAKE2 incorporates internal constants (N and M) that, if they are generated in a secret manner, would allow the creators of N, M special access (in this case, allow a server to check the entire contents of their dictionary as the result of a single exchange).
Now, it appears that the SPAKE2 draft avoids such suspicion; that draft includes values of N and M for all supported curves, and a procedure that was used to generate them.  This procedure would create values without anyone knowing the secret relationship between P and N or M (and thus preventing anyone from knowing the backdoor).  I have able to only partially verify that these N, M values were generated by this procedure.  It would appear necessary that someone fully validate them.
On the other hand, if the CFRG does endorse SPAKE2, it needs to recognize that it is endorsing a standard with a potential backdoor (even if the designers prove that they did not attempt to insert anything).  In addition, this potential backdoor may become a high value target for an early Quantum Computer (as solving one discrete log problem would give them the back door to everyone using SPAKE2 with that specific parameter set; such a back door exists, all the public generation procedure shows is that the initial authors do not know it).  None of the proposed candidates are fully resistant to a Quantum Computer, however none of the others have this ‘solve one discrete log, weaken everyone’ property.

How much harder are many logs then one on a quantum computer? Not very.

I believe that it is about one million times harder to do one million discrete logs than it is to do one (given that Shor’s algorithm doesn’t generate any side information from one run that would help you with the next; I also can’t think of any way to combine N points, and solve fewer than N discrete logs in a way that would allow you to recover the DLogs of the original N points).

Looking at the likely progression of Quantum Computers, it appears probable that, once someone creates a real one (as opposed to the toys that exist now), they could break a ECDLog problem, but it may take weeks to do so (and there are not likely to be a number of them available).  Hence, one a TLA gets one, it might gain the capability to solve dozens of ECDlog problems a year, but no more than that; hence this vulnerability of SPAKE2 might be relevant.  Now, this is entirely speculation, and also it would be reasonable to suspect that the speed/cost of QCs would rise/drop fairly rapidly, and so a few years after that it might be feasible to attack the other schemes as well (at least for their high-value targets).  This scenario did seem plausible enough for me to mention it.

In addition, for most other methods, it may be that a single discrete log might not be sufficient to break a single instance of the other schemes; however that really is currently speculation, as I have not seriously studied the issue, nor do I know anyone else who has
The second big issue: the security proof.  The proof given in the paper (Theorem 12) would appear to be invalid; one error appears to be in Exp3 (which appears in Theorem 8 but is used essentially unchanged in Theorem 12); here, they replace the public oracle H (which converts the transcript and the computed point into the shared secret) with a secret one (that is, one the adversary does not have access to).  However, they have not ruled out active attacks at this point, and hence they do not consider the possibility that an active attacker (addressed in Exp4) may access the H function multiple times after a single exchange (without necessarily solving the CDH problem, as that applies only to passive attackers that can’t influence either input; in this case, the attacker can provide a value that influences one of the inputs to the DH).
The draft lists the protocol in a fair amount of detail (which is good; the CFRG will need to publish a detailed specification of the approved protocol, and this draft is a decent start).  However, there are an issue with the protocol they give.
The issue is that they do not specify the input checking properly.  They specify only that the received S, T values are not the neutral element when multiplied by h (the cofactor).  This is insufficient; it is important that the protocol verifies that S and T are members of the group (that is, are solutions to the elliptic curve equation).  If the point is received as an  (x, y) pair, then they must be verified as solutions to the equation; if they are in compressed form, then the application must fail if given an x value which x^3+ax+b does not have the appropriate square root; if given a single x value (e.g. Curve25519), you must verify that the x value is on the curve and not on the twist.  This received S or T value is added to a point which is on the curve, and I don’t know of any guarantees you can give if you add a point on the curve to a point which is not (and then multiply the sum by something).  The security considerations in the draft does mention this; however, it is missing from the actual specified protocol.
This protocol relies on standard operations (ECC point addition and multiplication), without using any password to point mapping, and thus is easy to make constant time with standard methods.
While the SPAKE2 paper makes no reference to a key confirmation pass, the draft insists on it.  It is not clear if the draft requires the key confirmation to be an extra round before you use the actual shared secret (Ke), or if you can use Ke to encrypt the message which also includes the key confirmation.
Further notes:
One difference between the draft and the original SPAKE2 paper is that the original paper specifically assumed that each user would have their own M value; the draft has a global M value for all users.  It is not clear that security is reduced by using a single M value for everyone; however, that is a difference.
Typographical error: the draft often says P-512 when it means P-521.

Thanks for the review. We will of course specify point validation explicitly in the next version.

Thank you.

There is also an issue with composite order groups we will fix in the next draft. (Perhaps with Ristretto?)

Were you worried about the share from the other side not being a member of the subgroup?  I don’t believe that’s a problem; on the other hand, it would be fairly easy to cover anyways (by applying the cofactor in appropriate places).

I will look at the paper in more detail to understand the comment. Thank you for doing this very thorough review.

Sincerely,
Watson