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

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 5 Sep 2019 18:33:00 +0000

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

SPEKE
Documents reviewed:
Initial SPEKE paper: https://eprint.iacr.org/2001/057
Updated SPEKE paper: https://eprint.iacr.org/2014/585.pdf
The submission cites the Updated SPEKE paper (and in particular, the "Patched SPEKE" in Figure 3) as the actual submission; the initial SPEKE paper is there mostly for the security proof.
The first thing to note is that the cited "Patched SPEKE" protocol (as well as other versions listed in the papers) are specific to finite field groups (specifically, multiplication modulo a large safe prime), and neither paper mentions the possibility of performing the operations over an elliptic curve.  The protocol could be translated into an elliptic curve group (and that was the submitter's explicit intent); however, that would make this protocol very similar to the CPACE protocol (reviewed below), as they are both essentially "Diffie-Hellman with a secret generator derived from the password", with only minor differences in how the secrets are derived.  Because of this, I have decided, for the purposes of this review, to treat the SPEKE proposal as solely the finite field version (and so not make unspecified changes to the SPEKE protocol; CPACE already addresses those changes).
One large issue is with the security proof; it doesn't work.
The initial SPEKE paper lists a proof; however, the updated paper shows a weakness in the protocol without solving the underlying hard problem, which implies the proof had a hole; specifically, the proof is a simulation proof, and the updated paper weakness involves an attacker which performs operations not accounted for by the simulation.  And, while updated paper did suggest a fix, they did not provide a proof of the revised protocol; they only showed that it addressed the specific weakness they found.
And, if we restrict SPEKE to finite field groups, it becomes the most bandwidth intensive proposal listed (even more than J-PAKE), as well as one of the more computationally expensive ones.  On the other hand, it also straight-forward to implement and relies only on standard operations (modular exponentiation, and modular squaring), which can be run in constant time using standard techniques. It does not require a special password to elliptic curve mapping function; it uses modular squaring to achieve the same effect (because of the safe prime MODP group it is in).  It also makes the required validating checking straight-forward (given that the protocol is safe even if the adversary passes a quadratic nonresidue); this validity checking is already in the proposed protocol.
The other issue is that the protocol is defined only at a fairly high level; any real definition will need to specify a number of things (the prime p that we work in, the actual method to convert the password into the value g, the format of the exchanged values N, M, the format of the identifiers Ahat, Bhat, the H function used to derive the shared secret); while these are mostly fairly straight-forward, these will have to be done.

CPACE
Document reviewed:
CPACE paper: https://eprint.iacr.org/2018/286 (note: during the review, we received an updated version of the paper; nothing critical for this review was changed in that update)
The major issue is the security proof, which would appear to be invalid.  It's a simulation-based proof; but I don't see how they cover cases where the adversary doesn't play by the rules the simulator assumes.  For example, in G2, they switch the standard hash/mapping function with one where they know the discrete log (and note that this does not change the observed distribution), and so later assume that the simulator knows the discrete logs.  However, the adversary is not bound to using the standard hash/mapping function with his accesses, and so the simulator might not know the discrete log.  It is not clear how the simulator is supposed to proceed in such a case, and hence the indistinguishability results from the various simulators may be invalid.
The specified CPACE protocol involves a Verify() function to validate points received from the other side; however I believe that function is underspecified.  They try to be more general (see the last paragraph in section 3.4); however, it would appear unlikely that an average implementor would be able to cover all cases.  I believe that it would be cleaner if we mandated that we support only curves with twist security (e.g. Curve25519 and Curve448), and that we exchange only the X coordinate (and that the Verify(X) function is precisely the check that hX is not the neutral element (where h is the cofactor - specifically, the lcm of the cofactors of the curve and the twist).  Note that, unlike SPAKE-2, the validity checking does not have to check whether points are on the twist, as twisted points cannot yield any additional information to the attacker.  The paper does mention the possibility of using other curves (such as short Weierstrass curves), I would suggest that we disallow those curves, as they would require alternative validity checking (such as checking the received x, y coordinates into the curve equation), and while this is not difficult, it is a change, without (as far as I can see) any compensating benefit.
CPACE involves a string to elliptic point mapping function (where the resulting point does not have any known relationship to any preexisting points).  While primitives that implement such a mapping to Elliptic Curve points are known, they are not commonly implemented, and so this is something else that needs to be implemented (and made constant time; a leakage there would allow an attacker the ability to gain information about which dictionary entries are more or less likely).
In addition, it is also not clear whether an explicit mutual authentication step is a required part of CPACE.  That step is shown in Figure 4; however, that lists the AuCPace protocol (which is not reviewed here) which does the mutual authentication step as a pass after the "CPace substep"); figure 5 (which is specific to CPace) does not list it at all (on the other hand, it doesn't actually list any exchanged messages).
On the other hand, except for the string to elliptic point mapping, CPACE is one of the cheapest alternatives; it has the lowest total bandwidth and the lowest computation.
In addition, the protocol is defined only at a fairly high level; any real definition will need to specify a number of things (the curves that we work in, the format of the identifiers sid, Pi, Pj, the actual hash and method to convert these identifiers and the password into the value G, the format of the exchanged messages (Figure 4 implies that they're only the values Ya, Yb, while the more detailed Figure 5 doesn't specify it at all).

J-PAKE
Documents reviewed:
Overall description: https://eprint.iacr.org/2010/190.pdf
Proof: https://www.normalesup.org/~fbenhamo/files/publications/SP_AbdBenMac15.pdf
Draft: https://tools.ietf.org/html/rfc8236
See also: https://tools.ietf.org/html/rfc8235 <https://tools.ietf.org/html/rfc8235%206>
Terminology note: NIZKP = "Noninteractive Zero Knowledge Proof"; in this context, a message that you can generate if you know the value x for a public g^x (and which someone receiving the message can verify), and which gives no more information.  This primitive is fundamental to how J-PAKE works.
As for the security proof, it would appear to be valid; I have not found a flaw in it.  Now, both the protocol and the proof are more complex than the alternatives, and so there are more places for an invalid assumption to occur.  On the other hand, the NIZKPs significantly reduce the flexibility available to the attacker (unlike other proposals, the adversary now cannot submit an arbitrary group element during his attack; he either has to know the discrete log, or copy the group element (and the NIZKP) from a previous exchange), and hence there are fewer assumptions that need to be made in the simulator's model of the adversary.  In addition, the NIZKPs turn out to be useful in making the simulator rather more robust.
One drawback with J-PAKE is that it is defined as a two round protocol; the draft notes (see section 4) that it could be implemented as a 1.5 round protocol (and this transformation is safe).  However, even with that optimization, it may be more difficult to fit within existing protocols.  For example, TLS 1.3 assumes that cryptographical keys are available to encrypt the server hello; with J-PAKE, the shared secret would not be available until the second message from the client.
J-PAKE (even over an elliptic curve) uses rather more bandwidth and more computation than other proposals that use elliptic curves (not as much as SPEKE, but that's because for this review we limited SPEKE to MODP groups).  Using a MODP group, the bandwidth usage becomes excessive; even if we use a 2048 bit Schnorr group (with a 256 bit subgroup; this reduces the size of the NIZKPs), the response from the server in 1.5 round mode would be over 1600 bytes, causing either fragmentation or segmentation, which is likely to be considered unacceptable (compared to the existing alternatives).
In addition, while the J-PAKE draft is a start, something that actually defines everything (the elliptic curve, the method of converting the password (and other information) into the 's' value, the format of the messages and the details of the above validity checking, the details of the NIZKP, including the hash used) would eventually be needed.
In addition, the draft refers to RFC8235 as a method to perform the NIZPKs; the requirement to validate that all the points are actually on the curve need to be high-lighted (and the actual procedure needs to be spelled out; the comment 'the public key validation incurs almost negligible cost due to the cofactor being small' indicates a possible misunderstanding of the issue, because we also need to protect against points that are not on the curve at all).
J-PAKE relies on only standard operations (group operations, and simple math modulo the group order), hence standard techniques for achieving constant time suffice.  The only conditional branches are those based on whether NIZKPs succeed or fail, and those do not need to be masked.
Also, not formally a part of this review, but as I went through the RFCs (8236 and 8235), a potential improvement occurred to me.  The NIZKP in 8235 allows the proof to reference an OtherInfo field; this is a value used to specify the context (so that the proof is not valid in any other context).  OtherInfo is currently unused in J-PAKE, however suppose we were to insert (for example) all the currently seen points in each proof as OtherInfo.  For example, the initial client pass might have the values of (x1, x2) as the extra info in both of its NIZKPs; the server response (assuming the 1.5 pass version) might have (x1, x2, x3, x4, B) as its extra info, and the final client response might use (x1, x2, x3, x4, A, B).  What this would mean is that the adversary has even less flexibility in his attack; he now cannot extract values from previous exchanges and reuse them in new ones (with the exception that he can exactly duplicate the initial client pass); he could (for example) modify the server response from an honest server, however he would have to select entirely fresh x3, x4, B values for which he knows the appropriate discrete logs.  Because the adversary has fewer options, this means that the proof could potentially be simplified (as there are fewer things that the proof has to prove can't happen), as well as giving a potentially better end security bound (everything the proof disallows does cause a small reduction in the provable security bound.  In fact, we might be able to limit the possible adversary strategies sufficiently that it would be practical to do a case analysis covering everything an attacker can attempt (which would be less rigorous, but considerably easier to understand).  In addition, this suggestion cannot hurt security (the existing proof is still valid, as the NIZPKs still meet the security assumptions), it would not increase bandwidth at all (the data inserted into the OtherInfo field is already present in the messages), and would only cause a tiny increase in the computation time (the extra info is just included in a hash).  Just a thought...

---

From: Watson Ladd <[email-masked]>
Date: Fri, 6 Sep 2019 08:47:05 -0700

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

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

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

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 6 Sep 2019 16:41:44 +0000

From: Watson Ladd <[email-masked]>
hhhhhhhh
On Fri, Sep 6, 2019, 8:03 AM Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[email-masked]>> 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.

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

---

From: Björn Haase <[email-masked]>
Date: Fri, 6 Sep 2019 20:34:45 +0200

Dear Scott,

I would like to thank you for your review. In you came up with some
questions
regarding CPace which I would like to answer. Secondly in a subsequent
section, I would like to
respond to your analysis.

You pointed out a weak point that you identified in the security proof.
You will not be astonished
to hear, that we believe that our proof holds. Still, in fact, we
actually might agree on all essential
aspects of your analysis!
In our opinion, the essence of your result might actually point to the
problems
might come with the strongly idealizing assumptions regarding the
concept of the random oracle that we
did use in the proof.

I would appreciate your feedback regarding the point, wether our
re-phrased version of your
feedback that you will find below correctly captures your reasoning or not.

Yours,

Björn

1) Answers to the questions raised regarding CPace:

 > Scott Fluhrer wrote:
 >In addition, it is also not clear whether an explicit mutual
authentication step is a
 >required part of CPACE.  That step is shown in Figure 4; however, that
lists the AuCPace protocol
 >(which is not reviewed here) which does the mutual authentication step
as a pass after the
 >“CPace substep”); figure 5 (which is specific to CPace) does not list
it at all
 >(on the other hand, it doesn’t actually list any exchanged messages).

It is common for simulation-based proofs in the UC framework to specify
the protocol in form of an
algorithm running on interactive Turing machines which exchange messages
by "send" operations.
As such, the two protocol messages show up in figure 5 as "CPace initiator"
and "CPace responder". As you see there, CPace is defined solely for
implicit authentication.
I.e. explicit key confirmation is out of the scope of both F_{pwKE} and
CPace.

As a consequence figure 5 does not include any authenticator message and
the ideal functionality does not provide any guarantees that might
parties abort further communication
in case that the authentication failed.

The AuCPace paper mainly focuses on presenting the augmented protocol
and CPace was actually only a
side-aspect. As such the "protocol boundaries" might benefit from some
additional text.

2) Replies regarding your analysis.

First let me again thank you for your review. My perception is that we
actually might have
consensus regarding the most relevant points.

 > Scott Fluhrer wrote:
 >The problem is that [in the proofs of SPAKE2, SPEKE and CPace] 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).

 > [...]

 >The major issue is the security proof [of CPace], which would appear
to be invalid.
 >It’s a simulation-based proof; but I don’t see how they cover cases
where the adversary
 >doesn’t play by the rules the simulator assumes.

Actually in the proof we did not make any assumption regarding the
adversary's strategy. In the wording
of the UC framework we show "simulability when facing dummy adversaries".
Note that properly handling the UC dummy adversary was at the core of
the "proof update" that you did mention.
(BTW: Thank you Björn Tackmann, for your careful reading and advice and
for providing your preliminary
review of AuCPace that allowed us to fix this topic.).
Note that the example that you gave also does not refer to a specific
attack strategy of the adversary but to the
properties of the hash function that she uses.

What we, however actually do is that we base our proof on strong
assumptions regarding the properties of
the *cryptographic primitives* that we use as a building block in our
protocol.
Specifically we had to model the hash function as a programable random
oracle.

 >For example, in G2, they switch the standard hash/mapping function
with one where they
 >know the discrete log (and note that this does not change the observed
distribution),
 >and so later assume that the simulator knows the discrete logs.

 >However, the adversary is not bound to using the standard hash/mapping
function with his accesses,
 >and so the simulator might not know the discrete log.  It is not clear
how the simulator is
 >supposed to proceed in such a case, and hence the indistinguishability
results from the
 >various simulators may be invalid.

What we indeed do in G2 is that we replace the real-world hash function
with a programable random oracle.

This is true and we agree that this could be a problem.
We program the hash value to chosen values that are indistinguishable
from random values
for the observing environment Z.

So regarding this part of your analysis we disagree in that we think
that we did not actually
make any assumption on "how the adverary is playing the game". Your main
point, however, might
rather an aspect on which we will agree.

Possibly your objection could be re-phrased using the wording

"The issue of the security proof of CPace is that the authors did base
the analysis on the
idealized assumption of availability of a programable random oracle
(PRO). The proof requires the
simulator to be given the power to program the output of the hash
function to chosen values that
could not be distinguished from random values. The simulator makes
specific choices that give it
access to secret exponents. This cannot happen in the real-world,
because the hash-functions
don't behave like random oracles. Without the RO-assumption it cannot be
proven that real-world
adversaries are given no more capabilities than what they were permitted
in the ideal-world
protocol."?

If this re-phrased sentence captures the essence of your review, we have
consensus.

Note that the awareness with respect to the many problems related to
random oracles as
idealization of hash functions is one of the two aspects which made us
choose the
256-bit-security-level hash SHA512 in conjunction with the
128-bit-security-level
primitives used elsewhere in our reference implementation AuCPace25519.
We thought that it might be wise to be particularly conservative with
respect to the
choice of the hash, specifically due to the risks associated with the RO
idealization.
(The second reason was: "When using Curve25519, it is likely that
Ed25519 is interresting
and then SHA512 might be required anyway.")

I also agree with you on your assessment that J-PAKE does not rely on
comparably strong
assumptions of a *programable* random oracle. Specifically regarding the
RO programability,
J-PAKE seems to make significantly weaker assumptions. In this context,
I would like to
refer to the paper of Jan Camenisch, Manu Drijvers, Tommaso Gagliardoni,
Anja Lehmann and
Gregory Neven "The wonderful world of global random oracles".
(https://link.springer.com/chapter/10.1007/978-3-319-78381-9_11).

In my opinion also the game-based proofs of SPAKE2 and VTBPEKE make
somewhat weaker assumptions
regarding the RO. I believe that, e.g. in contrast to the UC proofs of
AuCPace CPace and OPAQUE
the random oracle does not to be *programable* for the former two protocols.
This is an advantage that I see for VTBPEKE and SPAKE2, however I agree
with your reasoning regarding
the "nothing-upon-my-sleeves" problem regarding the special points used
in these constructions
and the risks that will show up when facing quantum computers.

Note also, that I fear that the *programable* random oracle might be the
weakest assumption required
for proving security of any securely composable (i.e. secure in a
simulation-based approach) PAKE
protocol that comes with augmentation :-(. In my opinion for any
approach making weaker assumptions
regarding the RO possible, we might be loosing the valuable
composability feature.

 > Scott Fluhrer wrote
 > The specified CPACE protocol involves a Verify() function to validate
points received from the
 > other side; however I believe that function is underspecified.
 > They try to be more general (see the last paragraph in section 3.4);
however, it would
 > appear unlikely that an average implementor would be able to cover
all cases.

I agree on this. We did fully specify how to run Verify() for
x-coordinate-only implementations
on curves with a secure twist. For any other case we only have defined
the requirements
for the Verify() primitive. As such, the paper is not sufficient for an
implementation spec. but
"only" a scientific paper presenting a proof with one specific reference
implementation example.

 > I believe that it would be cleaner if we mandated that we support
only curves with twist
 > security (e.g. Curve25519 and Curve448), and that we exchange only
the X coordinate
 > (and that the Verify(X) function is precisely the check that hX is
not the neutral element
 > (where h is the cofactor – specifically, the lcm of the cofactors of
the curve and the twist).

I agree that it would have been cleaner and simpler. Still, there might
be use-cases where
implementers might be forced to using other curves. Imagine for instance
the case of
american/french/german/chinese government applications which require
their own favorite choice of
curves. Also there might be legacy hardware-accellerators or
CC/FIPS-certified software libraries
which only cover some short-weierstrass curves. You might be loosing
FIPS/CC approvals :-(.

For this reason, we see the use-case and need for dealing also with the
somehwat more complex case
of Short-Weierstrass curves. (Note that I also see the need for this
requirement from a
crypto-agility point of view).

 > Note that, unlike SPAKE-2, the validity checking does not have to
check whether points are on the twist,
 > as twisted points cannot yield any additional information to the
attacker.
Yes. In my opinion, this is one of the advantages of CPace.

 > The paper does mention the possibility of using other curves (such as
short Weierstrass curves),
 > I would suggest that we disallow those curves, as they would require
alternative validity checking
 > (such as checking the received x, y coordinates into the curve
equation),
 > and while this is not difficult, it is a change, without (as far as I
can see) any
 > compensating benefit.

Again I agree. Security-wise adding support for short-weierstrass might
actually even increase the
risk of implementation pitfalls. Still, I strongly believe that we
should not strictly disallow this
choice, specifically when considering secure element chips designed for
specific short-weierstrass,
curves only.

As you noted for short-weierstrass curves, Verify() would boil down to
what we do at various places
today ("Verify that the point is on the right curve.") and doing this
might be easily merged with a
point decompression. So, for short-weierstrass, there might actually be
no benefit of using
the x-coordinate-only approach.

 > CPACE involves a string to elliptic point mapping function (where the
resulting point does not
 > have any known relationship to any preexisting points).  While
primitives that implement such a
 > mapping to Elliptic Curve points are known, they are not commonly
implemented, and so this is
 > something else that needs to be implemented (and made constant time;
a leakage there would allow
 > an attacker the ability to gain information about which dictionary
entries are more or less likely).

Again we agree here. But I believe that this is a small issue in
comparison with the performance and
problems that come with the alternatives as used in SPAKE2 and TBPEKE
(as sketched in Appendix A
of our paper).

 > In addition, the protocol is defined only at a fairly high level; any
real definition will need to
 > specify a number of things (the curves that we work in, the format of
the identifiers sid, Pi, Pj,
 > the actual hash and method to convert these identifiers and the
password into the value G, the
 > format of the exchanged messages [...].

Yes. As mentioned. The AuCPace paper was meant to be a scientific paper
discussing the need of PAKE
in real-world settings together with the proof and an optimized
reference implementation example.
As such it is yet not sufficiently specific as to allow for writing
inter-operable implementations.
However we believe that this step would be somewhat straight-forward.

Thank you again for your review.

Yours,

Björn

---

From: Björn Haase <[email-masked]>
Date: Fri, 6 Sep 2019 22:33:17 +0200

As mentioned by Scott Fluhrer in his review of the four balanced PAKE
schemes, I have provided the panel members with a revised security proof
last week. In this revision I did consider a list of topics that were
brought up by Björn Tackmann during his review of AuCPace and CPace.

This revision is now also publicly available at
https://eprint.iacr.org/2018/286.

Björn

---

From: "Hao, Feng" <[email-masked]>
Date: Sun, 8 Sep 2019 16:13:02 +0000

IMHO, the threat is not so much a quantum computer, but a state actor (a three-letter agency) who breaks one instance of DL simply by brute-force, which will be justified if this single attack allows the adversary to break everywhere.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 8 Sep 2019 09:35:52 -0700

> IMHO, the threat is not so much a quantum computer, but a state actor (a three-letter agency) who breaks one instance of DL simply by brute-force, which will be justified if this single attack allo…

Maybe you shouldn't use brute-forceable parameters? Making a DLOG
instance in the prequantum world a billion times harder is simple: add
32 bytes.

>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

--
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Dan Harkins <[email-masked]>
Date: Sat, 07 Sep 2019 19:27:48 -0700

Hi Scott,

   Thank you very much for your detailed review of these balanced PAKEs.

   I am disappointed in your decision to focus on the MODP-only mode of
SPEKE and not the ECC mode but that is your decision and I won't try to
dispute it. I think your entire review of all proposals is eminently fair.

   Thank you very much. Regards,

   Dan.

On 9/5/19 11:33 AM, Scott Fluhrer (sfluhrer) wrote:
> 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).
>
> 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.
>
> Original SPAKE2 paper: 
> _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.
>
> (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.
>
> 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.
>
> <https://eprint.iacr.org/2001/057>
>
> Updated SPEKE paper: _https://eprint.iacr.org/2014/585.pdf_
>
> The submission cites the Updated SPEKE paper (and in particular, the 
> “Patched SPEKE” in Figure 3) as the actual submission; the initial 
> SPEKE paper is there mostly for the security proof.
>
> The first thing to note is that the cited “Patched SPEKE” protocol (as 
> well as other versions listed in the papers) are specific to finite 
> field groups (specifically, multiplication modulo a large safe prime), 
> and neither paper mentions the possibility of performing the 
> operations over an elliptic curve.  The protocol could be translated 
> into an elliptic curve group (and that was the submitter’s explicit 
> intent); however, that would make this protocol very similar to the 
> CPACE protocol (reviewed below), as they are both essentially 
> “Diffie-Hellman with a secret generator derived from the password”, 
> with only minor differences in how the secrets are derived.  Because 
> of this, I have decided, for the purposes of this review, to treat the 
> SPEKE proposal as solely the finite field version (and so not make 
> unspecified changes to the SPEKE protocol; CPACE already addresses 
> those changes).
>
> One large issue is with the security proof; it doesn’t work.
>
> The initial SPEKE paper lists a proof; however, the updated paper 
> shows a weakness in the protocol without solving the underlying hard 
> problem, which implies the proof had a hole; specifically, the proof 
> is a simulation proof, and the updated paper weakness involves an 
> attacker which performs operations not accounted for by the 
> simulation.  And, while updated paper did suggest a fix, they did not 
> provide a proof of the revised protocol; they only showed that it 
> addressed the specific weakness they found.
>
> And, if we restrict SPEKE to finite field groups, it becomes the most 
> bandwidth intensive proposal listed (even more than J-PAKE), as well 
> as one of the more computationally expensive ones.  On the other hand, 
> it also straight-forward to implement and relies only on standard 
> operations (modular exponentiation, and modular squaring), which can 
> be run in constant time using standard techniques. It does not require 
> a special password to elliptic curve mapping function; it uses modular 
> squaring to achieve the same effect (because of the safe prime MODP 
> group it is in)..  It also makes the required validating checking 
> straight-forward (given that the protocol is safe even if the 
> adversary passes a quadratic nonresidue); this validity checking is 
> already in the proposed protocol.
>
> The other issue is that the protocol is defined only at a fairly high 
> level; any real definition will need to specify a number of things 
> (the prime p that we work in, the actual method to convert the 
> password into the value g, the format of the exchanged values N, M, 
> the format of the identifiers Ahat, Bhat, the H function used to 
> derive the shared secret); while these are mostly fairly 
> straight-forward, these will have to be done.
>
> CPACE
>
> Document reviewed:
>
> CPACE paper: https://eprint.iacr.org/2018/286 (note: during the 
> review, we received an updated version of the paper; nothing critical 
> for this review was changed in that update)
>
> The major issue is the security proof, which would appear to be 
> invalid.  It’s a simulation-based proof; but I don’t see how they 
> cover cases where the adversary doesn’t play by the rules the 
> simulator assumes. For example, in G2, they switch the standard 
> hash/mapping function with one where they know the discrete log (and 
> note that this does not change the observed distribution), and so 
> later assume that the simulator knows the discrete logs. However, the 
> adversary is not bound to using the standard hash/mapping function 
> with his accesses, and so the simulator might not know the discrete 
> log.  It is not clear how the simulator is supposed to proceed in such 
> a case, and hence the indistinguishability results from the various 
> simulators may be invalid.
>
> points received from the other side; however I believe that function 
> is underspecified.  They try to be more general (see the last 
> paragraph in section 3.4); however, it would appear unlikely that an 
> average implementor would be able to cover all cases.  I believe that 
> it would be cleaner if we mandated that we support only curves with 
> twist security (e.g. Curve25519 and Curve448), and that we exchange 
> only the X coordinate (and that the Verify(X) function is precisely 
> the check that hX is not the neutral element (where h is the cofactor 
> – specifically, the lcm of the cofactors of the curve and the twist).  
> check whether points are on the twist, as twisted points cannot yield 
> any additional information to the attacker.  The paper does mention 
> the possibility of using other curves (such as short Weierstrass 
> curves), I would suggest that we disallow those curves, as they would 
> require alternative validity checking (such as checking the received 
> x, y coordinates into the curve equation), and while this is not 
> difficult, it is a change, without (as far as I can see) any 
> compensating benefit.
>
> resulting point does not have any known relationship to any 
> preexisting points).  While primitives that implement such a mapping 
> to Elliptic Curve points are known, they are not commonly implemented, 
> and so this is something else that needs to be implemented (and made 
> constant time; a leakage there would allow an attacker the ability to 
> gain information about which dictionary entries are more or less likely).
>
> authentication step is a required part of CPACE.  That step is shown 
> in Figure 4; however, that lists the AuCPace protocol (which is not 
> reviewed here) which does the mutual authentication step as a pass 
> after the “CPace substep”); figure 5 (which is specific to CPace) does 
> not list it at all (on the other hand, it doesn’t actually list any 
> exchanged messages).
>
> On the other hand, except for the string to elliptic point mapping, 
> CPACE is one of the cheapest alternatives; it has the lowest total 
> bandwidth and the lowest computation.
>
> real definition will need to specify a number of things (the curves 
> that we work in, the format of the identifiers sid, Pi, Pj, the actual 
> hash and method to convert these identifiers and the password into the 
> value G, the format of the exchanged messages (Figure 4 implies that 
> they’re only the values Ya, Yb, while the more detailed Figure 5 
> doesn’t specify it at all).
>
> J-PAKE
>
> Documents reviewed:
>
> <https://eprint.iacr.org/2010/190.pdf>
>
> Proof: 
> https://www.normalesup.org/~fbenhamo/files/publications/SP_AbdBenMac15.pdf 
>
>
> See also: https://tools.ietf.org/html/rfc8235 
> <https://tools.ietf.org/html/rfc8235%206>
>
> Terminology note: NIZKP = “Noninteractive Zero Knowledge Proof”; in 
> this context, a message that you can generate if you know the value x 
> for a public g^x (and which someone receiving the message can verify), 
> and which gives no more information.  This primitive is fundamental to 
> how J-PAKE works.
>
> As for the security proof, it would appear to be valid; I have not 
> found a flaw in it.  Now, both the protocol and the proof are more 
> complex than the alternatives, and so there are more places for an 
> invalid assumption to occur.  On the other hand, the NIZKPs 
> significantly reduce the flexibility available to the attacker (unlike 
> other proposals, the adversary now cannot submit an arbitrary group 
> element during his attack; he either has to know the discrete log, or 
> copy the group element (and the NIZKP) from a previous exchange), and 
> hence there are fewer assumptions that need to be made in the 
> simulator’s model of the adversary.  In addition, the NIZKPs turn out 
> to be useful in making the simulator rather more robust.
>
> One drawback with J-PAKE is that it is defined as a two round 
> protocol; the draft notes (see section 4) that it could be implemented 
> as a 1.5 round protocol (and this transformation is safe).  However, 
> even with that optimization, it may be more difficult to fit within 
> existing protocols.  For example, TLS 1.3 assumes that cryptographical 
> keys are available to encrypt the server hello; with J-PAKE, the 
> shared secret would not be available until the second message from the 
> client.
>
> J-PAKE (even over an elliptic curve) uses rather more bandwidth and 
> more computation than other proposals that use elliptic curves (not as 
> much as SPEKE, but that’s because for this review we limited SPEKE to 
> MODP groups).  Using a MODP group, the bandwidth usage becomes 
> excessive; even if we use a 2048 bit Schnorr group (with a 256 bit 
> subgroup; this reduces the size of the NIZKPs), the response from the 
> server in 1.5 round mode would be over 1600 bytes, causing either 
> fragmentation or segmentation, which is likely to be considered 
> unacceptable (compared to the existing alternatives).
>
> In addition, while the J-PAKE draft is a start, something that 
> actually defines everything (the elliptic curve, the method of 
> converting the password (and other information) into the ‘s’ value, 
> the format of the messages and the details of the above validity 
> checking, the details of the NIZKP, including the hash used) would 
> eventually be needed.
>
> In addition, the draft refers to RFC8235 as a method to perform the 
> NIZPKs; the requirement to validate that all the points are actually 
> on the curve need to be high-lighted (and the actual procedure needs 
> to be spelled out; the comment ‘the public key validation incurs 
> almost negligible cost due to the cofactor being small’ indicates a 
> possible misunderstanding of the issue, because we also need to 
> protect against points that are not on the curve at all).
>
> J-PAKE relies on only standard operations (group operations, and 
> simple math modulo the group order), hence standard techniques for 
> achieving constant time suffice.  The only conditional branches are 
> those based on whether NIZKPs succeed or fail, and those do not need 
> to be masked.
>
> Also, not formally a part of this review, but as I went through the 
> RFCs (8236 and 8235), a potential improvement occurred to me.  The 
> NIZKP in 8235 allows the proof to reference an OtherInfo field; this 
> is a value used to specify the context (so that the proof is not valid 
> in any other context).  OtherInfo is currently unused in J-PAKE, 
> however suppose we were to insert (for example) all the currently seen 
> points in each proof as OtherInfo.  For example, the initial client 
> pass might have the values of (x1, x2) as the extra info in both of 
> its NIZKPs; the server response (assuming the 1.5 pass version) might 
> have (x1, x2, x3, x4, B) as its extra info, and the final client 
> response might use (x1, x2, x3, x4, A, B)..  What this would mean is 
> that the adversary has even less flexibility in his attack; he now 
> cannot extract values from previous exchanges and reuse them in new 
> ones (with the exception that he can exactly duplicate the initial 
> client pass); he could (for example) modify the server response from 
> an honest server, however he would have to select entirely fresh x3, 
> x4, B values for which he knows the appropriate discrete logs.  
> Because the adversary has fewer options, this means that the proof 
> could potentially be simplified (as there are fewer things that the 
> proof has to prove can’t happen), as well as giving a potentially 
> better end security bound (everything the proof disallows does cause a 
> small reduction in the provable security bound.  In fact, we might be 
> able to limit the possible adversary strategies sufficiently that it 
> would be practical to do a case analysis covering everything an 
> attacker can attempt (which would be less rigorous, but considerably 
> easier to understand).  In addition, this suggestion cannot hurt 
> security (the existing proof is still valid, as the NIZPKs still meet 
> the security assumptions), it would not increase bandwidth at all (the 
> data inserted into the OtherInfo field is already present in the 
> messages), and would only cause a tiny increase in the computation 
> time (the extra info is just included in a hash). Just a thought…
>
>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 10 Sep 2019 22:55:16 +0000

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Björn Haase
> Sent: Friday, September 06, 2019 2:35 PM
> To: [email-masked]
> Subject: Re: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE,
> CPACE, J-PAKE)
> 
> Dear Scott,
> 
> questions regarding CPace which I would like to answer. Secondly in a
> subsequent section, I would like to respond to your analysis.
> 
> to hear, that we believe that our proof holds. Still, in fact, we actually might
> agree on all essential aspects of your analysis!
> problems might come with the strongly idealizing assumptions regarding the
> concept of the random oracle that we did use in the proof.
> 
> I would appreciate your feedback regarding the point, wether our re-
> phrased version of your feedback that you will find below correctly captures
> your reasoning or not.
> 
> Yours,
> 
> Björn
> 
> 
>  >In addition, it is also not clear whether an explicit mutual authentication
> step is a  >required part of CPACE.  That step is shown in Figure 4; however,
> that lists the AuCPace protocol  >(which is not reviewed here) which does
> the mutual authentication step as a pass after the  >"CPace substep"); figure
> 5 (which is specific to CPace) does not list it at all  >(on the other hand, it
> doesn't actually list any exchanged messages).
> 
> It is common for simulation-based proofs in the UC framework to specify the
> protocol in form of an algorithm running on interactive Turing machines
> which exchange messages by "send" operations.
> and "CPace responder". As you see there, CPace is defined solely for implicit
> authentication.
> I.e. explicit key confirmation is out of the scope of both F_{pwKE} and CPace.
> 
> the ideal functionality does not provide any guarantees that might parties
> abort further communication in case that the authentication failed.
> 
> and CPace was actually only a side-aspect. As such the "protocol boundaries"
> might benefit from some additional text.
> 
> 
> actually might have consensus regarding the most relevant points.
> 
>  > Scott Fluhrer wrote:
> 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).
> 
>  > [...]
> 
>  >The major issue is the security proof [of CPace], which would appear to be
> invalid.
>  >It's a simulation-based proof; but I don't see how they cover cases where
> the adversary  >doesn't play by the rules the simulator assumes.
> 
> adversary's strategy. In the wording of the UC framework we show
> "simulability when facing dummy adversaries".
> Note that properly handling the UC dummy adversary was at the core of the
> "proof update" that you did mention.
> (BTW: Thank you Björn Tackmann, for your careful reading and advice and for
> providing your preliminary review of AuCPace that allowed us to fix this
> topic.).
> Note that the example that you gave also does not refer to a specific attack
> strategy of the adversary but to the properties of the hash function that she
> uses.
> 
> assumptions regarding the properties of the *cryptographic primitives* that
> we use as a building block in our protocol.
>  >For example, in G2, they switch the standard hash/mapping function with
> one where they  >know the discrete log (and note that this does not change
> the observed distribution),  >and so later assume that the simulator knows
> the discrete logs.
> 
> function with his accesses,  >and so the simulator might not know the
> discrete log.  It is not clear how the simulator is  >supposed to proceed in
> such a case, and hence the indistinguishability results from the  >various
> What we indeed do in G2 is that we replace the real-world hash function with
> a programable random oracle.
> 
> We program the hash value to chosen values that are indistinguishable from
> random values for the observing environment Z.
> 
> So regarding this part of your analysis we disagree in that we think that we
> did not actually make any assumption on "how the adverary is playing the
> game". Your main point, however, might rather an aspect on which we will
> agree.

Let me try to rephrase my objection: in the protocol, legitimate parties will always invoke Map2Point(H(something)) to generate a point; hence when dealing with legitimate parties, it is totally reasonable in G3 to replace H with something where you always know the dlog of the point generated.

However, with a PAKE, we can't limit the adversary to only using points of the form Map2Point(H(something)); they can pick anything (see my repeated pleas to "please do input checking", because inserting things which aren't points at all can really mess things up).  My concern was that if you assumed you always knew the discrete log, well, the adversary can forbid that.

Now, going over the proof again, I do see where you try to deal with this, I'd need to review this further.

On the other hand, I did manage to find a counterexample to Theorem 1 (as stated); the protocol is broken if:
	- We're on a curve where the DDH problem is easy
	- H2 is the identity function (or otherwise doesn't hide the value K); theorem 1 makes no assumptions on H2.

The attack is fairly straight-forward:
-	 The honest initiator transmits G^y (for password-dependent G, secret y)
-	The adversary responds with H (for an arbitrary point H)
-	The honest initiator computes H^y, and output the sk (which includes H^y).
-	The adversary somehow hears the sk (and thus gets H^y)

Then, the attacker goes through his dictionary, and for each password, he computes the corresponding G', and then checks if (G', G^y, H, H^y) is a Diffie-Hellman set; for the correct password, it will be.

Now, this attack makes quite improbable assumptions (e.g. that H2 is the identity); however as far as I can see, everything it does is pedantically within the assumptions of Theorem 1; and so there's something there that could use a bit of tightening up.  I haven't gone through the proof myself to track down where it fails in this case; I don't expect that to cause a major change in your proof...

> "The issue of the security proof of CPace is that the authors did base the
> analysis on the idealized assumption of availability of a programable random
> oracle (PRO). The proof requires the simulator to be given the power to
> program the output of the hash function to chosen values that could not be
> distinguished from random values. The simulator makes specific choices that
> give it access to secret exponents. This cannot happen in the real-world,
> because the hash-functions don't behave like random oracles. Without the
> RO-assumption it cannot be proven that real-world adversaries are given no
> more capabilities than what they were permitted in the ideal-world
> protocol."?
> 
> random oracles as idealization of hash functions is one of the two aspects
> which made us choose the 256-bit-security-level hash SHA512 in conjunction
> with the 128-bit-security-level primitives used elsewhere in our reference
> implementation AuCPace25519.
> We thought that it might be wise to be particularly conservative with respect
> to the choice of the hash, specifically due to the risks associated with the RO
> idealization.
>  > The specified CPACE protocol involves a Verify() function to validate points
> received from the  > other side; however I believe that function is
> underspecified.
> however, it would  > appear unlikely that an average implementor would be
> able to cover all cases.
> 
> I agree on this. We did fully specify how to run Verify() for x-coordinate-only
> implementations on curves with a secure twist. For any other case we only
> have defined the requirements for the Verify() primitive. As such, the paper
> is not sufficient for an implementation spec. but "only" a scientific paper
> presenting a proof with one specific reference implementation example.
> 
>  > I believe that it would be cleaner if we mandated that we support only
> curves with twist  > security (e.g. Curve25519 and Curve448), and that we
> exchange only the X coordinate  > (and that the Verify(X) function is precisely
> the check that hX is not the neutral element  > (where h is the cofactor -
> specifically, the lcm of the cofactors of the curve and the twist).
> 
> I agree that it would have been cleaner and simpler. Still, there might be use-
> cases where implementers might be forced to using other curves. Imagine
> for instance the case of american/french/german/chinese government
> applications which require their own favorite choice of curves. Also there
> might be legacy hardware-accellerators or CC/FIPS-certified software
> libraries which only cover some short-weierstrass curves. You might be
> loosing FIPS/CC approvals :-(.

Actually, X25519 is NIST approved (and CC follows FIPS in terms of the crypto primitives), and so FIPS/CC should be fine.

> somehwat more complex case of Short-Weierstrass curves. (Note that I also
> see the need for this requirement from a crypto-agility point of view).

In that case, if you transmit (x, y) coordinates (possibly compressed), you really need to check them against the curve equation (if they're not on the curve, they can be of any order); you really need to mandate this (as well as checking hP != 0).

> 
>  > Note that, unlike SPAKE-2, the validity checking does not have to check
> whether points are on the twist, 
> as twisted points cannot yield any
> additional information to the attacker.
>  > The paper does mention the possibility of using other curves (such as short
> Weierstrass curves),  > I would suggest that we disallow those curves, as they
> would require alternative validity checking  > (such as checking the received
> x, y coordinates into the curve equation),  > and while this is not difficult, it is
> a change, without (as far as I can see) any  > compensating benefit.
> 
> actually even increase the risk of implementation pitfalls. Still, I strongly
> believe that we should not strictly disallow this choice, specifically when
> considering secure element chips designed for specific short-weierstrass,
> curves only.

Fair enough.  Just make sure you specify everything...

> 
> As you noted for short-weierstrass curves, Verify() would boil down to what
> we do at various places today ("Verify that the point is on the right curve.")
> and doing this might be easily merged with a point decompression. So, for
> short-weierstrass, there might actually be no benefit of using the x-
> coordinate-only approach.

Well, it does save one byte of bandwidth :-)

>  > In addition, the protocol is defined only at a fairly high level; any real
> definition will need to  > specify a number of things (the curves that we work
> in, the format of the identifiers sid, Pi, Pj,  > the actual hash and method to
> convert these identifiers and the password into the value G, the  > format of
> the exchanged messages [...].
> 
> discussing the need of PAKE in real-world settings together with the proof
> and an optimized reference implementation example.
> As such it is yet not sufficiently specific as to allow for writing inter-operable
> implementations.

Still needs to be done (and reviewed; It's astonishing how many devils there are in the details)

---

From: Björn Haase <[email-masked]>
Date: Wed, 11 Sep 2019 08:33:09 +0000

Dear Scott,

thank you for your response. I will be probably answering in more detail tomorrow (am having lots of meetings today).

For now I'd like to respond to the most important point regarding your last post:

I completely agree with you that we indeed need to use hash functions for the place where the protocol spec. uses hash functions. We must not replace h_2 with an identity function. This would make the protocol insecure.

Actually we meant to have specified this assumption in the Theorem 1 by using the 
term "... securely realizes F_pwKE in the F_RO hybrid model ...". With the term F_RP hybrid model we meant that, all hash functions are replaced by random oracles, this includes of course also h_2. So we did never claim security in case that h_2 is the identity function.

I will be responding more specifically to the other aspects soon.

Yours,

Björn

P.S.: Again thank you for the time that you spend on this really tedious task.

Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware
Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: +49 7156 209 377 | Fax: +49 7156 209 221
[email-masked] |  www.conducta.endress.com 

Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.