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

[Watson Ladd <[e-mail]>]

On Fri, Sep 6, 2019, 8:03 AM Scott Fluhrer (sfluhrer) <[e-mail]>
wrote:

> Review of Balanced PAKEs:
>
> Summary: I have reviewed the security of the four balanced PAKEs, and
> other than potential vulnerabilities due to lack of input validation (which
> I have highlighted in the detailed reviews), I could not find any issues
> with the protocols as presented.
>
> In addition, I have reviewed the security proofs; the J-PAKE proof appears
> to be valid, while the proofs provided with the other protocols (SPAKE2,
> SPEKE, CPACE) appear to be flawed.  These flaws all stem from the same
> basic source; these proofs are based on simulations, where the proof starts
> with the actual protocol, and constructs a series of increasingly idealized
> versions of the protocol, running each version on a simulator, and attempt
> to prove that each version of the protocol is indistinguishable (or has a
> small quantifiable delta in security) to the next version, and the last
> version is trivially secure.  The problem is that these simulations have a
> model of what the adversary is allowed to do, and I managed to find
> potential actions that an adversary might try to accomplish that is not
> accounted for by the simulator’s adversary model (and hence the security
> proof would not be valid when facing such an adversary).
>
> As such, J-PAKE is the only one that appears to have a valid security
> proof – however, it is considerably more costly in practical terms.  The
> CFRG will need to decide whether the existence of a security proof (and
> generally more conservative design) outweighs the practical considerations.
>
> Now, the detailed reviews:
>
>
>
> 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
> <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.

> 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.

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

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

Sincerely,
Watson