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

From: "Hao, Feng" <[email-masked]>
Date: Fri, 6 Sep 2019 20:59:56 +0000

Dear Scott,

Many thanks for your comprehensive reviews! Much appreciated.

I would like to clarify a few points in your review regarding J-PAKE.

From: Cfrg <[email-masked]<mailto:[email-masked]>> on behalf of "Scott Fluhrer (sfluhrer)" <[email-masked]<mailto:[email-masked]>>
Date: Thursday, 5 September 2019 at 19:33
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE, CPACE, J-PAKE)

"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)."
[FH] Thanks for pointing this out. I agree that the bandwidth of J-PAKE is significant in MODP groups. To address it I recommend using ECC groups whenever possible, as done in the Thread. The use of ECC (e.g., P256) reduces that size to about 300 bytes.
"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)."
[FH] I would like to clarify that checking whether the public key is actually a point on the curve is one of the compulsory steps to perform “public key validation” in an ECC setting. I believe this is the general consensus in the community.

Fyi See: https://www.dcs.warwick.ac.uk/~fenghao/files/EllipticCurveJPAKEDemo.java

"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…"

[FH] Thanks for your suggestion. I don’t object anyone doing the above, which is exactly why I defined OtherInfo (optional) in the RFC, to provide the flexibility to include the transcript of the key exchange (if people want) into the hash so to restrict the attacker even further and make the proof tighter. However, I didn’t want to make it mandatory for two reasons. 1) I don’t consider this is strictly necessary for the security of J-PAKE; 2) if we do it, we will end up with a protocol specification that depends on whether the protocol will be implemented as 2 rounds or 1.5 round. It’s not neat, and makes things more complex. Between simplicity and complexity, I would err in favour of the former : )

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 6 Sep 2019 22:06:51 +0000

From: Hao, Feng <[email-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..."

[FH] Thanks for your suggestion. I don't object anyone doing the above, which is exactly why I defined OtherInfo (optional) in the RFC, to provide the flexibility to include the transcript of the key exchange (if people want) into the hash so to restrict the attacker even further and make the proof tighter. However, I didn't want to make it mandatory for two reasons. 1) I don't consider this is strictly necessary for the security of J-PAKE; 2) if we do it, we will end up with a protocol specification that depends on whether the protocol will be implemented as 2 rounds or 1.5 round. It's not neat, and makes things more complex. Between simplicity and complexity, I would err in favour of the former : )

Well, I just spent a disgusting amount of time slogging through four different simulation-based proofs of PAKE, and they were all pretty much clear as mud.   I did not find any problems with your proof, however I am not entirely convinced (because of the subtlety involved) that I didn't miss anything.
In contrast, with my idea, well, that severely limits the games that an attacker can play.  I suspect that we could simply list the various things that an adversary can try (e.g. keep the first message unchanged, replace the values in the second and third messages with values whose dlog he knows) and show that none of the attacks allows the adversary any unwarranted advantage.  Why would such a proof (which I have not worked out the details) be considered attractive?  Because it'd be clear that it covers everything an adversary can do, and between a proof which is opaque (and which might hide hidden flaws) and one which is obviously valid, I would err in favor of the latter. :)

Of course, as a compromise, you could have the responder's x3, x4 values have only (x3, x4) as the OtherInfo; that would make both the 2 pass and the 1.5 pass version identical.  It would allow the attacker more options (e.g. he could now leave x3 and x4 unchanged, but insert his own B value), but there might not be *that* many more cases...

---

From: "Hao, Feng" <[email-masked]>
Date: Sun, 8 Sep 2019 15:58:10 +0000

Well, I just spent a disgusting amount of time slogging through four different simulation-based proofs of PAKE, and they were all pretty much clear as mud.   I did not find any problems with your proof, however I am not entirely convinced (because of the subtlety involved) that I didn’t miss anything.
In contrast, with my idea, well, that severely limits the games that an attacker can play.  I suspect that we could simply list the various things that an adversary can try (e.g. keep the first message unchanged, replace the values in the second and third messages with values whose dlog he knows) and show that none of the attacks allows the adversary any unwarranted advantage.  Why would such a proof (which I have not worked out the details) be considered attractive?  Because it’d be clear that it covers everything an adversary can do, and between a proof which is opaque (and which might hide hidden flaws) and one which is obviously valid, I would err in favor of the latter. :)

Of course, as a compromise, you could have the responder’s x3, x4 values have only (x3, x4) as the OtherInfo; that would make both the 2 pass and the 1.5 pass version identical.  It would allow the attacker more options (e.g. he could now leave x3 and x4 unchanged, but insert his own B value), but there might not be *that* many more cases…

Thanks for the suggestion. However, I don’t think including those values would make any fundamental difference when we consider an active attacker. The attacker is better off to come up with his own g^x3 and g^x4 values so he has the advantage of knowing the secret keys. But then this is exactly what the ZKP is supposed to do – enforcing the attacker to follow the protocol specification. If you also have a read of the security proofs in the original J-PAKE paper [HR10], it should be clear that the security of J-PAKE is essentially reduced to the security of the ZKP, or more specifically Schnorr NIZK proof. As long as the sender demonstrates the knowledge of x when sending g^x, J-PAKE provably satisfies the four security requirements as specified in the paper. In the construction of Schnorr NIZK proof, we include the statement (I.e., in terms of three items g, g^v, g^x) and the user identity in the hash as mandatory. If you take a broader view to look at PAKE, not as an isolated problem, but an instance of a more general two/multi-party secure computation problem (on an equality function), you will find our construction of ZKP is in line with the best practice in the the field (although some MPC protocols don’t explicitly include the user identity in the hash for the Fiat-Shamir transformation, we include it as mandatory we believe that’s necessary; otherwise, the attacker might be able to replay the NIZP proof back to the sender so to introduce some unexpected correlation effect.)